Threefold Post Correspondence System

2013/09/03 by Sandor Vagvolgyi, Vagvolgyi, Sandor
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO

paper · pdf · doi:10.48550/arxiv.1309.0633

arxiv created 2013/09/03 · arxiv updated 2013/09/04

Abstract

We introduce the concept of a threefold Post correspondence system (3PCS for short) and we consider it as an instance of the threefold Post correspondence problem. With each 3PCS, we associate three Post correspondence systems, i.e., three instances of the Post correspondence problem. We conjecture that for each 3PCS, the question of the threefold Post correspondence problem or for some associated Post correspondence system the question of the Post correspondence problem is decidable.

Related

• Another proof of undecidability for the correspondence decision problem - Had I been Emil Post
• On Bi-infinite and Conjugate Post Correspondence Problems
• (Generalized) Post Correspondence Problem and semi-Thue systems
• Maximality of correspondence representations
• Undecidability in binary tag systems and the Post correspondence problem for four pairs of words