On simplest possible solutions for Post Correspondence Problems

DOI10.1007/BF01210595MaRDI QIDQ1323352zbMATH OpenOpenAlexFDO

Authors Alexandru Mateescu, Arto Salomaa

Publication date 10 May 1994

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01210595

zbMATH Keywords

post correspondence problemprimality typesundecidability proofs

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Undecidability and degrees of sets of sentences (03D35) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 10092
• PCP-prime words and primality types
• Post correspondence problem: words possible as primitive solutions
• On F-prime solutions of the Post correspondence problem
• scientific article; zbMATH DE number 1860694

Cites work

• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• A variant of a recursively unsolvable problem
• scientific article; zbMATH DE number 3767068 (Why is no real title available?)
• scientific article; zbMATH DE number 10092 (Why is no real title available?)
• PCP-prime words and primality types

Cited in

(12)

• Flatwords and Post Correspondence Problem
• The Post correspondence problem over a unary alphabet
• Strongly prime PCP words
• scientific article; zbMATH DE number 4037835 (Why is no real title available?)
• scientific article; zbMATH DE number 1759685 (Why is no real title available?)
• Remarks on generalized Post Correspondence Problem
• Post correspondence problem: words possible as primitive solutions
• scientific article; zbMATH DE number 10092 (Why is no real title available?)
• scientific article; zbMATH DE number 1860694 (Why is no real title available?)
• PCP-prime words and primality types
• On some variants of Post's correspondence problem
• More decidable instances of Post's correspondence problem: beyond counting

This page was built for publication: On simplest possible solutions for Post Correspondence Problems

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