Post correspondence problem for short words

DOI10.1016/j.ipl.2008.04.013zbMath1191.68305OpenAlexW1978961500MaRDI QIDQ975420

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

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.04.013

zbMATH Keywords

undecidabilitypost correspondence problemtheory of computationgeneralized post correspondence problemshort wordsTzeitin semigroup

Mathematics Subject Classification ID

Related Items (4)

Decidability Questions for Insertion Systems and Related Models ⋮ Unnamed Item ⋮ Post Correspondence Problem and Small Dimensional Matrices ⋮ Complexity of Restricted Variants of Skolem and Related Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Binary (generalized) Post Correspondence Problem
• Remarks on generalized Post Correspondence Problem
• A variant of a recursively unsolvable problem

This page was built for publication: Post correspondence problem for short words