Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
From MaRDI portal
Publication:764364
DOI10.1016/j.tcs.2011.11.006zbMath1282.68123OpenAlexW1999013503MaRDI QIDQ764364
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.11.006
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On the Disambiguation of Weighted Automata ⋮ Degree of Sequentiality of Weighted Automata ⋮ Unnamed Item ⋮ Finite sequentiality of unambiguous max-plus tree automata ⋮ Ideal basis in constructions defined by directed graphs ⋮ A disambiguation algorithm for weighted automata
Cites Work
- Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
- Handbook of weighted automata
- 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
- Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
- Communication complexity method for measuring nondeterminism in finite automata
- New results on the star problem in trace monoids
- On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra
- Regular path queries under approximate semantics
- A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
- THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
- Modeling and analysis of timed Petri nets using heaps of pieces
- Weighted Automata Algorithms
- Distance desert automata and the star height problem
- Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
