A4 Refereed article in a conference publication
Decidability and undecidability of marked PCP
Authors: Halava V, Hirvensalo M, de Wolf R
Editors: C. Meinel, S. Tison
Publication year: 1999
Journal:: Lecture Notes in Computer Science
Book title : STACS'99
Journal name in source: STACS'99 - 16TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE
Journal acronym: LECT NOTES COMPUT SC
Volume: 1563
First page : 207
Last page: 216
Number of pages: 10
ISBN: 3-540-65691-X
ISSN: 0302-9743
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, 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.
UTU Research Portal