A1 Refereed original research article in a scientific journal
Marked PCP is decidable
Authors: Halava V, Hirvensalo M, de Wolf R
Publisher: ELSEVIER SCIENCE BV
Publication year: 2001
Journal:: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 255
Issue: 1-2
First page : 193
Last page: 204
Number of pages: 12
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(99)00163-2
Abstract
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.