A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
New proof for the undecidability of the circular PCP
Tekijät: Vesa Halava, Tero Harju
Kustantaja: SPRINGER
Julkaisuvuosi: 2013
Journal: Acta Informatica
Tietokannassa oleva lehden nimi: ACTA INFORMATICA
Lehden akronyymi: ACTA INFORM
Numero sarjassa: 5-6
Vuosikerta: 50
Numero: 5-6
Aloitussivu: 331
Lopetussivu: 341
Sivujen määrä: 11
ISSN: 0001-5903
eISSN: 1432-0525
DOI: https://doi.org/10.1007/s00236-013-0183-5
Verkko-osoite: http://link.springer.com/journal/236/50/5/page/1
Tiivistelmä
We give simpler proof for the undecidability of the circular Post Correspondence Problem that was originally proved undecidable by Ruohonen (Acta Informatica 19:357-367, 1983). The key feature of our proof is the undecidability of the word problem of special semi-Thue systems where derivations are deterministic and reversible for words containing a single occurrence of a letter from a given set.
We give simpler proof for the undecidability of the circular Post Correspondence Problem that was originally proved undecidable by Ruohonen (Acta Informatica 19:357-367, 1983). The key feature of our proof is the undecidability of the word problem of special semi-Thue systems where derivations are deterministic and reversible for words containing a single occurrence of a letter from a given set.
Turun yliopiston Tutkimustietojärjestelmän portaali