Undecidability in ω-Regular Languages

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Halava, Vesa | Harju, Tero | Karhumäki, Juhani

Affiliations: Department of Mathematics and TUCS – Turku Centre for Computer Science, University of Turku FIN-20014 Turku, Finland. E-mails: vesa.halava@utu.fi; harju@utu.fi; karhumak@cs.utu.fi

Abstract: In the infinite Post Correspondence Probleman instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word α such that h(α)=g(α). In the general case this problemwas 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 ω-languages of the form R^{ω} where R is a given regular language.

Keywords: Post Correspondence Problem, infinite word, semi-Thue system, regular language, undecidability

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 119-125, 2006