A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
Institut für Informatik, Postfach 10 09 20, 04009 Leipzig, Germany
We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri . The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.
Mathematics Subject Classification: 68Q45 / 68Q70 / 20M35
Key words: Weighted automata / tropical semiring / determinization.
© EDP Sciences, 2008