Binary (generalized) Post Correspondence Problem

DOI10.1016/S0304-3975(01)00157-8zbMath1023.03038OpenAlexW2002889841WikidataQ127674380 ScholiaQ127674380MaRDI QIDQ1605309

Mika Hirvensalo, Vesa Halava, Tero J.Harju

Publication date: 15 July 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00157-8

zbMATH Keywords

decidabilitybinary Post Correspondence Problemgeneralised Post Correspondence Problemmarked morphisms

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 (11)

Extension of the decidability of the marked PCP to instances with unique blocks ⋮ On the decidability of semigroup freeness ⋮ Undecidability of infinite post correspondence problem for instances of size 8 ⋮ Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time ⋮ On bi-infinite and conjugate post correspondence problems ⋮ Decidability of the binary infinite Post Correspondence Problem ⋮ BINARY MORPHISMS WITH STABLE SUFFIX COMPLEXITY ⋮ Post correspondence problem for short words ⋮ Binary equality words with two $b$'s ⋮ REDUCTION TREE OF THE BINARY GENERALIZED POST CORRESPONDENCE PROBLEM ⋮ Undecidability of infinite post correspondence problem for instances of Size 9

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• GENERALIZED POST CORRESPONDENCE PROBLEM FOR MARKED MORPHISMS
• Remarks on generalized Post Correspondence Problem
• A variant of a recursively unsolvable problem
• Marked PCP is decidable

This page was built for publication: Binary (generalized) Post Correspondence Problem