A1 Refereed original research article in a scientific journal
The structure of infinite solutions of marked and binary post correspondence problems
Authors: Halava V, Harju T, Karhumaki J
Publisher: SPRINGER
Publication year: 2007
Journal:: Theory of Computing Systems
Journal name in source: THEORY OF COMPUTING SYSTEMS
Journal acronym: THEOR COMPUT SYST
Volume: 40
Issue: 1
First page : 43
Last page: 54
Number of pages: 12
ISSN: 1432-4350
DOI: https://doi.org/10.1007/s00224-005-1222-6
Abstract
In the infinite Post Correspondence Problem an instance (h, g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word omega such that h(omega) = g(omega). This problem is undecidable in general, but it is known to be decidable for binary and marked instances. A morphism is binary if the domain alphabet is of size 2, and marked if each image of a letter begins with a different letter. We prove that the solutions of a marked instance form a set E-omega boolean OR E*(P boolean OR F), where P is a finite set of ultimately periodic words, E is a finite set of solutions of the PCP, and F is a finite set of morphic images of fixed points of DOL systems. We also establish the structure of infinite solutions of the binary PCP.
In the infinite Post Correspondence Problem an instance (h, g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word omega such that h(omega) = g(omega). This problem is undecidable in general, but it is known to be decidable for binary and marked instances. A morphism is binary if the domain alphabet is of size 2, and marked if each image of a letter begins with a different letter. We prove that the solutions of a marked instance form a set E-omega boolean OR E*(P boolean OR F), where P is a finite set of ultimately periodic words, E is a finite set of solutions of the PCP, and F is a finite set of morphic images of fixed points of DOL systems. We also establish the structure of infinite solutions of the binary PCP.
UTU Research Portal