On post correspondence problem for letter monotonic languages
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.
post correspondence problem decidability word equation