A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Undecidability in omega-regular languages
Tekijät: Halava V, Harju T, Karhumaki J
Kustantaja: IOS PRESS
Julkaisuvuosi: 2006
Lehti:: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: FUNDAMENTA INFORMATICAE
Lehden akronyymi: FUND INFORM
Vuosikerta: 73
Numero: 1-2
Aloitussivu: 119
Lopetussivu: 125
Sivujen määrä: 7
ISSN: 0169-2968
Tiivistelmä
In the infinite Post Correspondence Problem an instance (h, g) consists of two morphisms h and 9, and the problem is to determine whether or not there exists an infinite word a such that h(alpha) = g(alpha). In the general case this problem was shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of omega-languages of the form R-omega where R is a given regular language.
In the infinite Post Correspondence Problem an instance (h, g) consists of two morphisms h and 9, and the problem is to determine whether or not there exists an infinite word a such that h(alpha) = g(alpha). In the general case this problem was shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of omega-languages of the form R-omega where R is a given regular language.
Turun yliopiston Tutkimustietojärjestelmän portaali