Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
From MaRDI portal
(Redirected from Publication:703577)
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.
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)
Cites work
- scientific article; zbMATH DE number 3932372 (Why is no real title available?)
- scientific article; zbMATH DE number 4002104 (Why is no real title available?)
- scientific article; zbMATH DE number 4072419 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 41838 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 1163641 (Why is no real title available?)
- scientific article; zbMATH DE number 2040319 (Why is no real title available?)
- A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring
- A construction on finite automata that has remained hidden
- Algorithms for determining relative star height and star height
- DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
- Dynamics of synchronized parallel systems
- Economy of description for single-valued transducers
- Finite-valued distance automata
- Modeling and analysis of timed Petri nets using heaps of pieces
- On the definition of a family of automata
- On the degree of ambiguity of finite automata
- On the determinization of weighted finite automata
- Performance evaluation of (max,+) automata
- Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
- Sur les rélations rationnelles entre monoides libres
- THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
- Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
Cited in
(43)- Pumping lemmas for weighted automata
- Disambiguation of weighted tree automata
- Finite ambiguity and finite sequentiality in weighted automata over fields
- On the disambiguation of weighted automata
- A disambiguation algorithm for weighted automata
- On delay and regret determinization of max-plus automata
- A contribution to the determinization of max-plus automata
- New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems
- scientific article; zbMATH DE number 7561720 (Why is no real title available?)
- A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
- Which finitely ambiguous automata recognize finitely sequential functions? (extended abstract)
- How to Tackle Integer Weighted Automata Positivity
- Sequential?
- Component simulation-based substitutivity managing QoS and composition issues
- Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
- A robust class of linear recurrence sequences
- scientific article; zbMATH DE number 2040921 (Why is no real title available?)
- scientific article; zbMATH DE number 7559164 (Why is no real title available?)
- scientific article; zbMATH DE number 7204387 (Why is no real title available?)
- Finite sequentiality of finitely ambiguous max-plus tree automata
- On determinism and unambiguity of weighted two-way automata
- Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
- Permutability of matrices over bipotent semirings
- Unambiguous automata denoting finitely sequential functions
- Polynomially ambiguous unary weighted automata over fields
- Determinations of weighted finite automata over commutative idempotent MF-semirings
- Ambiguity Hierarchies for Weighted Tree Automata
- Series which are both max-plus and min-plus rational are unambiguous
- scientific article; zbMATH DE number 7471710 (Why is no real title available?)
- Finitely ambiguous and finitely sequential weighted automata over fields
- Multiple context-free tree grammars: lexicalization and characterization
- Determinization of timed Petri nets behaviors
- Max-plus automata
- Unambiguity in automata theory
- Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata
- On finite and polynomial ambiguity of weighted tree automata
- Supervisory control of (max,+) automata: extensions towards applications
- Ambiguity hierarchies for weighted tree automata
- Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
- Limited non-determinism hierarchy of counter automata
- Finite sequentiality of unambiguous max-plus tree automata
- scientific article; zbMATH DE number 7407779 (Why is no real title available?)
- Compositions of (max,+) automata
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)
