Post correspondence problem: words possible as primitive solutions

DOI10.1007/3-540-60084-1_63MaRDI QIDQ4645167zbMATH OpenOpenAlexFDO

Authors Marjo Lipponen

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_63

zbMATH Keywords

binary alphabetfinite typeprime solutionprimitive word

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• PCP-prime words and primality types
• scientific article; zbMATH DE number 10092
• On simplest possible solutions for Post Correspondence Problems
• 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 3710436 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 572102 (Why is no real title available?)
• scientific article; zbMATH DE number 604881 (Why is no real title available?)
• scientific article; zbMATH DE number 10092 (Why is no real title available?)
• On simplest possible solutions for Post Correspondence Problems
• PCP-prime words and primality types
• The equation \(a_ M=b^ Nc^ P\) in a free group

Cited in

(14)

• On simplest possible solutions for Post Correspondence Problems
• Flatwords and Post Correspondence Problem
• P, NP, and the Post correspondence problem
• Strongly prime PCP words
• Sets of primitive words given by fixed points of mappings
• Decision problems concerning prime words and languages of the Post Correspondence Problems
• Reduction tree of the binary generalized post correspondence problem
• On Vaughan Pratt's crossword problem
• Post correspondence problem with partially commutative alphabets
• scientific article; zbMATH DE number 4037835 (Why is no real title available?)
• scientific article; zbMATH DE number 1759685 (Why is no real title available?)
• scientific article; zbMATH DE number 10092 (Why is no real title available?)
• PCP-prime words and primality types
• On F-prime solutions of the Post correspondence problem

This page was built for publication: Post correspondence problem: words possible as primitive solutions

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