On simplest possible solutions for Post Correspondence Problems

DOI10.1007/BF01210595zbMATH Open0790.68057OpenAlexW2073505157MaRDI QIDQ1323352FDOQ1323352

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

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

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)

Cites Work

• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• A variant of a recursively unsolvable problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• PCP-prime words and primality types

Cited In (10)

• Title not available (Why is that?)
• More decidable instances of Post's correspondence problem: beyond counting
• Title not available (Why is that?)
• Title not available (Why is that?)
• Flatwords and Post Correspondence Problem
• The Post correspondence problem over a unary alphabet
• Post correspondence problem: words possible as primitive solutions
• Remarks on generalized Post Correspondence Problem
• Strongly prime PCP words
• On some variants of Post's 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)