A1 Refereed original research article in a scientific journal

Marked PCP is decidable




AuthorsHalava V, Hirvensalo M, de Wolf R

PublisherELSEVIER SCIENCE BV

Publication year2001

Journal:Theoretical Computer Science

Journal name in sourceTHEORETICAL COMPUTER SCIENCE

Journal acronymTHEOR COMPUT SCI

Volume255

Issue1-2

First page 193

Last page204

Number of pages12

ISSN0304-3975

DOIhttps://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.



Last updated on 2025-13-10 at 14:26