A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Marked PCP is decidable
Tekijät: Halava V, Hirvensalo M, de Wolf R
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2001
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 255
Numero: 1-2
Aloitussivu: 193
Lopetussivu: 204
Sivujen määrä: 12
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(99)00163-2
Tiivistelmä
We show that the marked version of the Post Correspondence Problem, where the words on a list are required to differ in the first letter, is decidable. On the other hand, we prove that the PCP remains undecidable if we only require the words to differ in the first two letters. Thus we locate the decidability/undecidability-boundary between marked and 2-marked PCP. (C) 2001 Elsevier Science B.V. All rights reserved.
We show that the marked version of the Post Correspondence Problem, where the words on a list are required to differ in the first letter, is decidable. On the other hand, we prove that the PCP remains undecidable if we only require the words to differ in the first two letters. Thus we locate the decidability/undecidability-boundary between marked and 2-marked PCP. (C) 2001 Elsevier Science B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali