On the dual Post correspondence problem

DOI10.1142/S012905411440022XMaRDI QIDQ5247173zbMATH OpenFDO

Authors Joel D. Day, Daniel Reidenbach, Johannes Schneider

Publication date 23 April 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S012905411440022X

zbMATH Keywords

ambiguity of morphismsdual Post correspondence problemequality setsmorphismsperiodicity forcing setsword equations

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15)

Recommendations

• On the dual Post correspondence problem
• Periodicity forcing words
• Periodicity forcing words
• On some variants of Post's correspondence problem
• Remarks on generalized Post Correspondence Problem

Cites work

• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• A variant of a recursively unsolvable problem
• Equality languages and fixed point languages
• Intricacies of simple word equations: an example
• Large Simple Binary Equality Words
• Morphically primitive words
• On the dual Post correspondence problem
• P, NP, and the Post correspondence problem
• Periodicity forcing words
• UNAMBIGUOUS MORPHIC IMAGES OF STRINGS
• Weakly unambiguous morphisms

Cited in

(8)

• Periodicity forcing words
• Post correspondence problem with partially commutative alphabets
• scientific article; zbMATH DE number 4037835 (Why is no real title available?)
• Remarks on generalized Post Correspondence Problem
• Binary equality words with two b's.
• scientific article; zbMATH DE number 1860694 (Why is no real title available?)
• Periodicity forcing words
• On the dual Post correspondence problem

This page was built for publication: On the dual Post correspondence problem

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