| Authors |
|
| Publication date |
2001
|
| Journal |
Theoretical Computer Science
|
| Volume | Issue number |
255 | 1-2
|
| Pages (from-to) |
193-204
|
| Number of pages |
12
|
| Organisations |
-
Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
|
| 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.
|
| Document type |
Article
|
| Language |
English
|
| Published at |
https://doi.org/10.1016/S0304-3975(99)00163-2
|
|
Permalink to this page
|