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
Get full access to this article
View all access options for this article.