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

DOI10.1051/ita:2008017zbMath1155.68042OpenAlexW2000587532MaRDI 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

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (20)

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

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

This page was built for publication: A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata