New proof for the undecidability of the circular PCP

DOI10.1007/S00236-013-0183-5zbMATH Open1359.03033OpenAlexW2088935605MaRDI QIDQ378203FDOQ378203

Authors: Vesa Halava, Tero Harju 

Publication date: 11 November 2013

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-013-0183-5

Recommendations

• Deterministic semi-Thue systems and variants of Post correspondence problem
• On the \(n\)-permutation Post correspondence problem
• On some variants of Post's correspondence problem
• Publication:4729772
• Binary (generalized) Post Correspondence Problem

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Undecidability and degrees of sets of sentences (03D35)

Cites Work

• A variant of a recursively unsolvable problem
• Decision problems for semi-Thue systems with a few rules
• Recursive unsolvability of a problem of Thue
• Word problem for deterministic and reversible semi-Thue systems
• Title not available (Why is that?)
• Noneffective regularity of equality languages and bounded delay morphisms
• Title not available (Why is that?)
• Title not available (Why is that?)
• On some variants of Post's correspondence problem

Cited In (5)

• Deterministic semi-Thue systems and variants of Post correspondence problem
• On bi-infinite and conjugate post correspondence problems
• On the steps of Emil Post: from normal systems to the correspondence decision problem
• Title not available (Why is that?)
• On the \(n\)-permutation Post correspondence problem

This page was built for publication: New proof for the undecidability of the circular PCP

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