On Post correspondence problem for letter monotonic languages

DOI10.1016/j.tcs.2009.01.040zbMath1173.68033OpenAlexW2028396267WikidataQ62045938 ScholiaQ62045938MaRDI QIDQ2271434

Vesa Halava, Jarkko Kari, Yu. V. Matiyasevich

Publication date: 7 August 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.01.040

zbMATH Keywords

decidabilityword equationPost correspondence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items

Polynomially ambiguous probabilistic automata on restricted languages, Polynomially Ambiguous Probabilistic Automata on Restricted Languages

Cites Work

• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• Unsolvability in 3 × 3 Matrices
• New Computational Paradigms
• A variant of a recursively unsolvable problem
• Unnamed Item
• Unnamed Item
• Unnamed Item