A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
The structure of infinite solutions of marked and binary post correspondence problems
Tekijät: Halava V, Harju T, Karhumaki J
Kustantaja: SPRINGER
Julkaisuvuosi: 2007
Lehti:: Theory of Computing Systems
Tietokannassa oleva lehden nimi: THEORY OF COMPUTING SYSTEMS
Lehden akronyymi: THEOR COMPUT SYST
Vuosikerta: 40
Numero: 1
Aloitussivu: 43
Lopetussivu: 54
Sivujen määrä: 12
ISSN: 1432-4350
DOI: https://doi.org/10.1007/s00224-005-1222-6
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali