×

Primality types of instances of the Post correspondence problem. (English) Zbl 0744.68083

Summary: Whenever an instance of the post correspondence problem has a solution, it has infinitely many of them. There are different ways of defining solutions that are “simplest”. This paper initiates the study of three very natural definitions of “primitive” or “prime” solutions. A complete characterization of the resulting possibilities is obtained.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite