Undecidability of infinite post correspondence problem for instances of Size 9

DOI10.1051/ITA:2006039MaRDI QIDQ3423136zbMATH OpenOpenAlexFDO

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, https://eudml.org/doc/92820

zbMATH Keywords

Post correspondence problemundecidability

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• scientific article; zbMATH DE number 2087488 (Why is no real title available?)
• 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)

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

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)