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

DOI10.1016/J.TCS.2004.02.049zbMATH Open1071.68035arXiv0709.4117OpenAlexW1993033486MaRDI QIDQ703577FDOQ703577

Authors: Ines Klimann, Sylvain Lombardy, Jean Mairesse, Christophe Prieur 

Publication date: 11 January 2005

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

Abstract: Finite automata with weights in the max-plus semiring are considered. The main result is: it is decidable in an effective way whether a series that is recognized by a finitely ambiguous max-plus automaton is unambiguous, or is sequential. A collection of examples is given to illustrate the hierarchy of max-plus series with respect to ambiguity.

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

Recommendations

• scientific article; zbMATH DE number 2040921
• scientific article; zbMATH DE number 7559164
• Finite sequentiality of unambiguous max-plus tree automata
• Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
• Which finitely ambiguous automata recognize finitely sequential functions? (extended abstract)

zbMATH Keywords

Automaton with multiplicitiesFinite ambiguityMax-plus semiringSequentialityUnambiguity

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the determinization of weighted finite automata
• On the definition of a family of automata
• Title not available (Why is that?)
• Modeling and analysis of timed Petri nets using heaps of pieces
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• Title not available (Why is that?)
• Title not available (Why is that?)
• Performance evaluation of (max,+) automata
• Title not available (Why is that?)
• Sur les rélations rationnelles entre monoides libres
• Title not available (Why is that?)
• Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
• Algorithms for determining relative star height and star height
• On the degree of ambiguity of finite automata
• 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
• Dynamics of synchronized parallel systems
• DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA

Cited In (44)

• Determinations of weighted finite automata over commutative idempotent MF-semirings
• On determinism and unambiguity of weighted two-way automata
• Unambiguous automata denoting finitely sequential functions
• A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
• Limited non-determinism hierarchy of counter automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to Tackle Integer Weighted Automata Positivity
• Polynomially ambiguous unary weighted automata over fields
• Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata
• Component simulation-based substitutivity managing QoS and composition issues
• Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
• Title not available (Why is that?)
• Multiple context-free tree grammars: lexicalization and characterization
• New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems
• Finitely ambiguous and finitely sequential weighted automata over fields
• Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
• A robust class of linear recurrence sequences
• Determinization of timed Petri nets behaviors
• Finite sequentiality of finitely ambiguous max-plus tree automata
• Permutability of matrices over bipotent semirings
• Which finitely ambiguous automata recognize finitely sequential functions? (extended abstract)
• Title not available (Why is that?)
• Pumping lemmas for weighted automata
• On delay and regret determinization of max-plus automata
• A disambiguation algorithm for weighted automata
• Finite sequentiality of unambiguous max-plus tree automata
• Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
• Title not available (Why is that?)
• Ambiguity Hierarchies for Weighted Tree Automata
• On the disambiguation of weighted automata
• A contribution to the determinization of max-plus automata
• Series which are both max-plus and min-plus rational are unambiguous
• Unambiguity in automata theory
• Decidable weighted expressions with Presburger combinators
• Max-plus automata
• On finite and polynomial ambiguity of weighted tree automata
• Supervisory control of (max,+) automata: extensions towards applications
• Compositions of (max,+) automata
• Ambiguity hierarchies for weighted tree automata
• Sequential?
• Disambiguation of weighted tree automata
• Finite ambiguity and finite sequentiality in weighted automata over fields

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703577)