Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
Daniel Kirsten, Sylvain Lombardy · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
This paper solves the unambiguity and the sequentiality problem for polynomially ambiguous min-plus automata. This result is proved through a decidable algebraic characterization involving so-called metatransitions and an application of results from the structure theory of finite semigroups. It is noteworthy that the equivalence problem is known to be undecidable for polynomially ambiguous automata.