A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata

DOI10.1051/ita:2008017zbMath1155.68042MaRDI QIDQ3526417

Daniel Kirsten

Publication date: 25 September 2008

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92888

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q70: Algebraic theory of languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Unnamed Item, Unnamed Item, Determinization of timed Petri nets behaviors, Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring, Finite sequentiality of unambiguous max-plus tree automata, Behaviour equivalent max-plus automata for timed Petri nets under open-loop race-policy semantics, What's decidable about weighted automata?, Max-plus automata, A contribution to the determinization of max-plus automata, Compositions of (max,+) automata, A disambiguation algorithm for weighted automata, Initial-state detectability and initial-state opacity of unambiguous weighted automata, Supervisory control of (max,+) automata: extensions towards applications, On Finite and Polynomial Ambiguity of Weighted Tree Automata, On the Disambiguation of Weighted Automata, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• Improved limitedness theorems on finite automata with distance functions
• Factorization forests of finite height
• Algorithms for determining relative star height and star height
• Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
• Parametrized recurrent systems for image generation
• Finite-valued distance automata
• New upper bounds to the limitedness of distance automata
• Communication complexity method for measuring nondeterminism in finite automata
• The limitedness problem on distance automata: Hashiguchi's method revisited
• On factorization forests of finite height
• New results on the star problem in trace monoids
• On the Determinization of Weighted Finite Automata
• Distance automata having large finite distance or finite ambiguity
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• On semigroups of matrices over the tropical semiring
• DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
• Distance desert automata and the star height problem