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

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

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

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

Cited in

(10)

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

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)