On simplest possible solutions for Post Correspondence Problems

DOI10.1007/BF01210595zbMath0790.68057OpenAlexW2073505157MaRDI QIDQ1323352

Arto Salomaa, Alexandru Mateescu

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) Undecidability and degrees of sets of sentences (03D35) Thue and Post systems, etc. (03D03)

Related Items (max. 100)

Flatwords and Post Correspondence Problem ⋮ Strongly prime PCP words ⋮ Post correspondence problem: Words possible as primitive solutions

Cites Work

• Unnamed Item
• Unnamed Item
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• PCP-prime words and primality types
• A variant of a recursively unsolvable problem

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