A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On post correspondence problem for letter monotonic languages
Tekijät: Halava V, Kari J, Matiyasevich Y
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2009
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 410
Numero: 30-32
Aloitussivu: 2957
Lopetussivu: 2960
Sivujen määrä: 4
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2009.01.040
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali