Salomaa, Arto; Salomaa, Kai; Yu, Sheng Primality types of instances of the Post correspondence problem. (English) Zbl 0744.68083 Bull. EATCS 44, 226-241 (1991). 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. Cited in 5 Documents MSC: 68Q45 Formal languages and automata Keywords:primality; Post correspondence problem PDFBibTeX XMLCite \textit{A. Salomaa} et al., Bull. EATCS 44, 226--241 (1991; Zbl 0744.68083)