A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Post Correspondence Problem for short words
Tekijät: Halava V, Harju T, Hirvensalo M, Karhumaki J
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2008
Lehti:: Information Processing Letters
Tietokannassa oleva lehden nimi: INFORMATION PROCESSING LETTERS
Lehden akronyymi: INFORM PROCESS LETT
Vuosikerta: 108
Numero: 3
Aloitussivu: 115
Lopetussivu: 118
Sivujen määrä: 4
ISSN: 0020-0190
DOI: https://doi.org/10.1016/j.ipl.2008.04.013
Tiivistelmä
We prove that the generalized Post Correspondence Problem is undecidable for instances where the lengths of the image words are at most 2 and the number of pairs of words is at most 30. The proof uses undecidability of the word problem of the Tzeitin semigroup. We also transform our constructions in order to achieve a proof for the undecidability of the (not generalized) Post Correspondence Problem with image words of length at most 2. (C) 2008 Elsevier B.V. All rights reserved.
We prove that the generalized Post Correspondence Problem is undecidable for instances where the lengths of the image words are at most 2 and the number of pairs of words is at most 30. The proof uses undecidability of the word problem of the Tzeitin semigroup. We also transform our constructions in order to achieve a proof for the undecidability of the (not generalized) Post Correspondence Problem with image words of length at most 2. (C) 2008 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali