Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

DOI10.4230/LIPIcs.STACS.2009.1850zbMath1236.68172OpenAlexW1735667100MaRDI QIDQ5390010

Daniel Kirsten, Sylvain Lombardy

Publication date: 24 April 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_640e.html

zbMATH Keywords

finite semigroupsdeterminizationmin-plus automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (25)

Unnamed Item ⋮ Multi-Valued Reasoning about Reactive Systems ⋮ When are emptiness and containment decidable for probabilistic automata? ⋮ Rigorous approximated determinization of weighted automata ⋮ On the Disambiguation of Weighted Automata ⋮ Polynomially ambiguous unary weighted automata over fields ⋮ Bideterministic weighted automata ⋮ Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata ⋮ Degree of Sequentiality of Weighted Automata ⋮ Limited Non-determinism Hierarchy of Counter Automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finite sequentiality of unambiguous max-plus tree automata ⋮ Determinisability of unary weighted automata over the rational numbers ⋮ Factorization Forests ⋮ How to Tackle Integer Weighted Automata Positivity ⋮ Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring ⋮ Max-plus automata ⋮ Unambiguity in Automata Theory ⋮ Unnamed Item ⋮ Finite ambiguity and finite sequentiality in weighted automata over fields ⋮ Weak Cost Register Automata are Still Powerful ⋮ A robust class of linear recurrence sequences ⋮ New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems ⋮ A disambiguation algorithm for weighted automata

This page was built for publication: Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata