Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring

DOI10.1016/j.tcs.2011.11.006zbMath1282.68123OpenAlexW1999013503MaRDI QIDQ764364

Daniel Kirsten

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

zbMATH Keywords

formal power seriestropical semiringweighted finite automatatwins property

Mathematics Subject Classification ID

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