Undecidability of infinite post correspondence problem for instances of Size 9

DOI10.1051/ITA:2006039zbMATH Open1114.03035OpenAlexW2172004614MaRDI QIDQ3423136FDOQ3423136

Authors Vesa Halava, Tero Harju

Publication date 20 February 2007

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2006__40_4_551_0

zbMATH Keywords

undecidabilityPost correspondence problem

Mathematics Subject Classification ID

Combinatorics on words (68R15) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• Undecidability of infinite Post correspondence problem for instances of size 8
• scientific article; zbMATH DE number 2051181
• Decidability of the binary infinite Post Correspondence Problem
• The exact complexity of the infinite Post Correspondence Problem
• A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem
• An undecidable problem in correspondence theory
• Highly Undecidable Problems For Infinite Computations
• More decidable instances of Post's correspondence problem: beyond counting
• Infinite versions of some problems from finite complexity theory
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words

Cites work

• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• scientific article; zbMATH DE number 2087488 (Why is no real title available?)
• A variant of a recursively unsolvable problem
• Binary (generalized) Post Correspondence Problem
• Decidability of the binary infinite Post Correspondence Problem
• Decision problems for semi-Thue systems with a few rules
• Remarks on generalized Post Correspondence Problem
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Undecidable problems for probabilistic automata of fixed dimension

Cited in

(16)

• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
• Porous invariants
• Integer weighted automata on infinite words
• scientific article; zbMATH DE number 2051181 (Why is no real title available?)
• Post correspondence problem for short words
• Weighted automata on infinite words in the context of attacker-defender games
• Post Correspondence Problem and Small Dimensional Matrices
• On the Monniaux problem in abstract interpretation
• The exact complexity of the infinite Post Correspondence Problem
• Integer Weighted Automata on Infinite Words
• Undecidability of infinite Post correspondence problem for instances of size 8
• Porous invariants for linear systems
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• Extension of the decidability of the marked PCP to instances with unique blocks
• Weighted automata on infinite words in the context of attacker-defender games

This page was built for publication: Undecidability of infinite post correspondence problem for instances of Size 9

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3423136)