Decidability and undecidability of marked PCP

DOI10.1007/3-540-49116-3_19MaRDI QIDQ4251052zbMATH OpenFDO

Authors Vesa Halava, Mika Hirvensalo, Ronald de Wolf

Publication date 17 June 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/1230

zbMATH Keywords

decidability/undecidability-boundarymarked Post Correspondence Problem

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Formal languages and automata (68Q45)

Recommendations

• Marked PCP is decidable
• scientific article; zbMATH DE number 1522564
• Some new results on Post correspondence problem and its modifications
• Extension of the decidability of the marked PCP to instances with unique blocks

Cited in

(7)

• Decidability of behavioural equivalence in unary PCF
• Extension of the decidability of the marked PCP to instances with unique blocks
• Generalized Post correspondence problem for marked morphisms
• Some new results on Post correspondence problem and its modifications
• scientific article; zbMATH DE number 1522564 (Why is no real title available?)
• Marked PCP is decidable
• Finitary PCF is not decidable

This page was built for publication: Decidability and undecidability of marked PCP

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