Determinization of Min-Plus Weighted Automata is Decidable

Shaull Almagor; Guy Arbel; Sarai Sheinvald

doi:10.1137/1.9781611978971.11

SODA2026顶会

Determinization of Min-Plus Weighted Automata is Decidable

Shaull Almagor, Guy Arbel, Sarai Sheinvald

arXiv DOI 出版方

2026年份

1被引次数

1顶会引用

摘要

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.