A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Decidability and undecidability of marked PCP
Tekijät: Halava V, Hirvensalo M, de Wolf R
Toimittaja: C. Meinel, S. Tison
Julkaisuvuosi: 1999
Lehti:: Lecture Notes in Computer Science
Kokoomateoksen nimi: STACS'99
Tietokannassa oleva lehden nimi: STACS'99 - 16TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 1563
Aloitussivu: 207
Lopetussivu: 216
Sivujen määrä: 10
ISBN: 3-540-65691-X
ISSN: 0302-9743
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, 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 a-marked PCP.
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, 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 a-marked PCP.
Turun yliopiston Tutkimustietojärjestelmän portaali