New proof for the undecidability of the circular PCP

DOI10.1007/s00236-013-0183-5zbMath1359.03033OpenAlexW2088935605MaRDI QIDQ378203

Vesa Halava, Tero J.Harju

Publication date: 11 November 2013

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-013-0183-5

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Thue and Post systems, etc. (03D03)

Related Items (2)

On bi-infinite and conjugate post correspondence problems ⋮ On the \(n\)-permutation Post correspondence problem

Cites Work

• On some variants of Post's correspondence problem
• Decision problems for semi-Thue systems with a few rules
• Word problem for deterministic and reversible semi-Thue systems
• Recursive Unsolvability of a problem of Thue
• A variant of a recursively unsolvable problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New proof for the undecidability of the circular PCP