On bi-infinite and conjugate post correspondence problems

DOI10.1051/ita/2023008arXiv2111.04484OpenAlexW4297277501MaRDI QIDQ6186538

Tero J.Harju, Olivier Finkel, Esa Sahla, Vesa Halava

Publication date: 2 February 2024

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

Full work available at URL: https://arxiv.org/abs/2111.04484

zbMATH Keywords

undecidabilitypost correspondence problembi-infinite wordsconjugate words

Mathematics Subject Classification ID

General topics of discrete mathematics in relation to computer science (68R01) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Hierarchies of computability and definability (03D55)

Cites Work

• Unnamed Item
• New proof for the undecidability of the circular PCP
• On the \(n\)-permutation Post correspondence problem
• On some variants of Post's correspondence problem
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Decidability of the binary infinite Post Correspondence Problem
• Binary (generalized) Post Correspondence Problem
• The exact complexity of the infinite Post Correspondence Problem
• 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
• A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem
• A variant of a recursively unsolvable problem

This page was built for publication: On bi-infinite and conjugate post correspondence problems