Determinization of Min-Plus Weighted Automata is Decidable
Shaull Almagor, Guy Arbel, Sarai Sheinvald
2026Year
1Citations
1Top-tier citations
Abstract
We show that the determinization problem for min-plus (tropical) weighted automata is decidable, thus resolving this long-standing open problem. In doing so, we develop a new toolbox for analyzing and reasoning about the run-structure of nondeterministic automata.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Cited by top-tier papers1
Ask how each one uses itBuilds on3
- Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fieldsJason P. Bell, Daniel SmertnigLICS 2023 · 6 citations
- Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted AutomataIsmaël Jecker, Filip Mazowiecki, David PurserLICS 2024 · 4 citations
- The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)Laure Daviaud, David PurserLICS 2023 · 1 citation
Related papers
- SMT-Based Active Learning of Weighted AutomataTiago Ferreira, Kevin Batz, Alexandra SilvaCAV 2026
- Orbit-Finite-Dimensional Vector Spaces and Weighted Register AutomataMikolaj Bojanczyk, Bartek Klin, Joshua MoermanLICS 2021 · 5 citations
- Energy Büchi ProblemsSven Dziadek, Uli Fahrenberg, Philipp Schlehuber-CaissierFM 2023 · 1 citation
- Upper Bound for the Determinization of Emerson-Lei Automata: A One-Fin ApproachRunzhe Ma, Cong Tian, Wensheng Wang, Zhenhua DuanCAV 2026
- Register Automata with Extrema Constraints, and an Application to Two-Variable LogicSzymon Torunczyk, Thomas ZeumeLICS 2020 · 2 citations
