Marked PCP is decidable

DOI10.1016/S0304-3975(99)00163-2zbMath0974.68097WikidataQ56095060 ScholiaQ56095060MaRDI QIDQ5941069

Vesa Halava, Mika Hirvensalo, Ronald de Wolf

Publication date: 20 August 2001

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

zbMATH Keywords

decidabilitymarked morphismpost correspondence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

Extension of the decidability of the marked PCP to instances with unique blocks ⋮ String assembling systems: comparison to sticker systems and decidability ⋮ Post's correspondence problem: from computer science to algebra ⋮ Decidability of the binary infinite Post Correspondence Problem ⋮ Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting) ⋮ More decidable instances of Post's correspondence problem: beyond counting ⋮ TREE AUTOMATA WITH GLOBAL CONSTRAINTS ⋮ Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems ⋮ Binary (generalized) Post Correspondence Problem

Cites Work

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

This page was built for publication: Marked PCP is decidable