Document RAIRO-Theor. Inf. Appl. 42, 553-581 (2008)
DOI: 10.1051/ita:2008017
A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
Daniel KirstenUniversität Leipzig, Institut für Informatik, Postfach 10 09 20, 04009 Leipzig, Germany
Published online: 3 June 2008
Abstract
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 [29].
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