Extension of the decidability of the marked PCP to instances with unique blocks

DOI10.1016/J.TCS.2007.03.024MaRDI QIDQ2373757zbMATH OpenOpenAlexFDO

Authors Vesa Halava, Tero Harju, Juhani Karhumäki, Michel Latteux

Publication date 16 July 2007

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

Full work available at URL https://doi.org/10.1016/j.tcs.2007.03.024

zbMATH Keywords

decidabilityinfinite Post correspondence problemmarked morphismPost correspondence problemunique blockunique continuation

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• scientific article; zbMATH DE number 1304321
• Marked PCP is decidable
• scientific article; zbMATH DE number 1522564
• Generalized Post correspondence problem for marked morphisms
• scientific article; zbMATH DE number 2051181

Cites work

• A variant of a recursively unsolvable problem
• Binary (generalized) Post Correspondence Problem
• Decidability of the binary infinite Post Correspondence Problem
• Decision problems for semi-Thue systems with a few rules
• Generalized Post correspondence problem for marked morphisms
• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• scientific article; zbMATH DE number 1958322 (Why is no real title available?)
• scientific article; zbMATH DE number 2087488 (Why is no real title available?)
• scientific article; zbMATH DE number 3305031 (Why is no real title available?)
• Marked PCP is decidable
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• The structure of infinite solutions of marked and binary Post correspondence problems
• Undecidability of infinite post correspondence problem for instances of Size 9

Cited in

(5)

• Reduction tree of the binary generalized post correspondence problem
• scientific article; zbMATH DE number 1304321 (Why is no real title available?)
• scientific article; zbMATH DE number 1860694 (Why is no real title available?)
• More decidable instances of Post's correspondence problem: beyond counting
• The unambiguity of segmented morphisms

This page was built for publication: Extension of the decidability of the marked PCP to instances with unique blocks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373757)