On the \(n\)-permutation Post correspondence problem

DOI10.1016/j.tcs.2015.07.021zbMath1338.03074OpenAlexW863451849MaRDI QIDQ496055

Vesa Halava, Mari Ernvall, Tero J.Harju

Publication date: 16 September 2015

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

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

zbMATH Keywords

word problemdeterministicsemi-Thue systemcyclic derivationpermutation Post correspondence problem

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)

Related Items (1)

On bi-infinite and conjugate post correspondence problems

Cites Work

• New proof for the undecidability of the circular PCP
• 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: On the \(n\)-permutation Post correspondence problem