Mateescu, Alexandru; Salomaa, Arto PCP-prime words and primality types. (English) Zbl 0770.68082 RAIRO, Inform. Théor. Appl. 27, No. 1, 57-70 (1993). Summary: We investigate “simplest”, “primitive” or “prime” solutions of instances of the Post Correspondence Problem, PCP. We take also the opposite view point by studying words that can describe such a prime solution, for some instance of PCP. Cited in 4 Documents MSC: 68Q45 Formal languages and automata Keywords:Post Correspondence Problem PDFBibTeX XMLCite \textit{A. Mateescu} and \textit{A. Salomaa}, RAIRO, Inform. Théor. Appl. 27, No. 1, 57--70 (1993; Zbl 0770.68082) Full Text: DOI EuDML References: [1] 1. K. CULIK II and A. SALOMAA, Test Sets and Checking Words for Homomorphism Equivalence, J. Comput. System Sci., 1980, 20, pp. 379-395. Zbl0451.68046 MR584866 · Zbl 0451.68046 [2] 2. R. C. LYNDON and M. P. SCHUTZENBERGER, The Equation aM = bN cP in Free Group, Michigan Math. J. 1962, 9, pp. 289-298. Zbl0106.02204 MR162838 · Zbl 0106.02204 [3] 3. E. POST, A Variant of a Recursively Unsolvable Problem, Bull. Amer. Math. Soc., 1946, 52, pp. 264-268. Zbl0063.06329 MR15343 · Zbl 0063.06329 [4] 4. A. SALOMAA, Jewels of Formal Language Theory, Comput. Sci. Press, 1981. Zbl0487.68064 MR618124 · Zbl 0487.68064 [5] 5. A. SALOMAA, K. SALOMAA and SHENG YU, Primality types of instances of the Post Correspondent Problem, E.A.T.C.S. Bulletin, 1991, 44. Zbl0744.68083 · Zbl 0744.68083 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.