GENERALIZED POST CORRESPONDENCE PROBLEM FOR MARKED MORPHISMS

DOI10.1142/S0218196700000376zbMath0971.68124MaRDI QIDQ2709980

Tero J.Harju, Mika Hirvensalo, Vesa Halava

Publication date: 17 April 2001

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

generalized post correspondence problem

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

Extension of the decidability of the marked PCP to instances with unique blocks, More decidable instances of Post's correspondence problem: beyond counting, Decision problems for semi-Thue systems with a few rules, Binary (generalized) Post Correspondence Problem, Binary equality sets are generated by two words

Cites Work

• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• A variant of a recursively unsolvable problem