On post correspondence problem for letter monotonic languages

: Halava V, Kari J, Matiyasevich Y

Publisher: ELSEVIER SCIENCE BV

: 2009

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 410

: 30-32

: 2957

: 2960

: 4

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2009.01.040

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.