On Bi-infinite and Conjugate Post Correspondence Problems

2021/11/08 by Olivier Finkel, Vesa Halava, Finkel, Olivier +5
Computer Science · #03D35 #03D40 #03D55 #68R01 #Advanced Algebra and Logic #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Logic, programming, and type systems

paper · pdf · doi:10.48550/arxiv.2111.04484

openalex publication_date 2021/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study two modifications of the Post Correspondence Problem (PCP), namely 1) the bi-infinite version, where it is asked whether there exists a bi-infinite word such that two given morphisms agree on it, and 2) the conjugate version, where we require the images of a solution for two given morphisms are conjugates of each other. For the bi-infinite PCP we show that it is in the class Σ₂⁰ of the arithmetical hierarchy and for the conjugate PCP we give an undecidability proof by reducing it to the word problem for a special type of semi-Thue systems.

Related

• Threefold Post Correspondence System
• (Generalized) Post Correspondence Problem and semi-Thue systems
• Another proof of undecidability for the correspondence decision problem - Had I been Emil Post
• The Post correspondence problem in groups
• Dynamical Systems of Correspondences on the Projective Line II: Degrees of Multiplier Maps