Decidability of the binary infinite Post Correspondence Problem

DOI10.1016/S0166-218X(03)00330-5zbMath1023.03039MaRDI QIDQ1408462

Vesa Halava, Tero J.Harju, Juhani Karhumäki

Publication date: 22 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

decidabilityinfinite wordbinary instancebinary Post Correspondence Probleminfinite solutions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40)

Related Items (3)

Extension of the decidability of the marked PCP to instances with unique blocks ⋮ On bi-infinite and conjugate post correspondence problems ⋮ Undecidability of infinite post correspondence problem for instances of Size 9

Cites Work

• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Binary (generalized) Post Correspondence Problem
• Binary equality sets are generated by two words
• A variant of a recursively unsolvable problem
• Marked PCP is decidable
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Decidability of the binary infinite Post Correspondence Problem