A1 Refereed original research article in a scientific journal
On post correspondence problem for letter monotonic languages
Authors: Halava V, Kari J, Matiyasevich Y
Publisher: ELSEVIER SCIENCE BV
Publication year: 2009
Journal:: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 410
Issue: 30-32
First page : 2957
Last page: 2960
Number of pages: 4
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2009.01.040
Abstract
We prove that for given morphisms g. h: {a(1), a(2), ..., a(n)} -> B*, it is decidable whether or not there exists a word w in the regular language a(1)*a(2)* ... a(n)* Such that g(w) = h(w). In other words, we prove that the Post Correspondence Problem is decidable if the Solutions are restricted to be from this special language. This yields a nice example of an undecidable problem in integral matrices which cannot be directly proved Undecidable using the traditional reduction from the Post Correspondence Problem. (C) 2009 Elsevier B.V. All rights reserved.
We prove that for given morphisms g. h: {a(1), a(2), ..., a(n)} -> B*, it is decidable whether or not there exists a word w in the regular language a(1)*a(2)* ... a(n)* Such that g(w) = h(w). In other words, we prove that the Post Correspondence Problem is decidable if the Solutions are restricted to be from this special language. This yields a nice example of an undecidable problem in integral matrices which cannot be directly proved Undecidable using the traditional reduction from the Post Correspondence Problem. (C) 2009 Elsevier B.V. All rights reserved.
UTU Research Portal