The equality problem for rational series with multiplicities in the tropical semiring is undecidable

DOI10.1007/3-540-55719-9_67zbMath1425.68213OpenAlexW1497067119MaRDI QIDQ5204310

Daniel Krob

Publication date: 4 December 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55719-9_67

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Semirings (16Y60)

Related Items

Some consequences of a Fatou property of the tropical semiring ⋮ Unnamed Item ⋮ Elements of tropical linear algebra ⋮ Rational and Recognisable Power Series ⋮ A contribution to the determinization of max-plus automata ⋮ Arctic Termination ...Below Zero ⋮ The per-character cost of repairing word languages ⋮ Copyless cost-register automata: structure, expressiveness, and closure properties ⋮ The algebraic equivalent of AFL theory ⋮ Quantitative simulations by matrices ⋮ Comparison of max-plus automata and joint spectral radius of tropical matrices ⋮ Unnamed Item

Cites Work

• On the decidability of some problems about rational subsets of free partially commutative monoids
• Rational relations and rational series
• A Reduction of Homogeneous Diophantine Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item