Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton

DOI10.1016/j.tcs.2004.02.049zbMath1071.68035arXiv0709.4117OpenAlexW1993033486MaRDI QIDQ703577

Sylvain Lombardy, Christophe Prieur, Jean Mairesse, Ines Klimann

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0709.4117

zbMATH Keywords

Automaton with multiplicitiesFinite ambiguityMax-plus semiringSequentialityUnambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (36)

DETERMINATIONS OF WEIGHTED FINITE AUTOMATA OVER COMMUTATIVE IDEMPOTENT MF-SEMIRINGS ⋮ Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids ⋮ Unnamed Item ⋮ Determinization of timed Petri nets behaviors ⋮ Permutability of matrices over bipotent semirings ⋮ On the Disambiguation of Weighted Automata ⋮ Polynomially ambiguous unary weighted automata over fields ⋮ Ambiguity Hierarchies for Weighted Tree Automata ⋮ Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata ⋮ A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata ⋮ Unnamed Item ⋮ Limited Non-determinism Hierarchy of Counter Automata ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Sequential? ⋮ Component simulation-based substitutivity managing QoS and composition issues ⋮ Unnamed Item ⋮ Decidable weighted expressions with Presburger combinators ⋮ Unnamed Item ⋮ Supervisory control of (max,+) automata: extensions towards applications ⋮ On Determinism and Unambiguity of Weighted Two-Way Automata ⋮ Series which are both max-plus and min-plus rational are unambiguous ⋮ Unnamed Item ⋮ Finite sequentiality of unambiguous max-plus tree automata ⋮ On Finite and Polynomial Ambiguity of Weighted Tree Automata ⋮ 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 ⋮ Disambiguation of weighted tree automata ⋮ Finite ambiguity and finite sequentiality in weighted automata over fields ⋮ A robust class of linear recurrence sequences ⋮ New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems ⋮ Compositions of (max,+) automata ⋮ Ambiguity hierarchies for weighted tree 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
• Algorithms for determining relative star height and star height
• On the degree of ambiguity of finite automata
• Sur les rélations rationnelles entre monoides libres
• Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
• A construction on finite automata that has remained hidden
• A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring
• Finite-valued distance automata
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Economy of description for single-valued transducers
• On the Determinization of Weighted Finite Automata
• On the definition of a family of automata
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• Dynamics of synchronized parallel systems
• Modeling and analysis of timed Petri nets using heaps of pieces
• DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
• Performance evaluation of (max,+) automata

This page was built for publication: Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton