| Issue |
RAIRO-Theor. Inf. Appl.
Volume 42, Number 3, July-September 2008
JM'06
|
|
|---|---|---|
| Page(s) | 553 - 581 | |
| DOI | https://doi.org/10.1051/ita:2008017 | |
| Published online | 03 June 2008 | |
A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
Universität Leipzig,
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 [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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.