×

Undecidability in \(\omega\)-regular languages. (English) Zbl 1101.03031

Summary: In the infinite Post Correspondence Problem (PCP) an instance \((h,g)\) consists of two morphisms \(h\) and \(g\), and the problem is to determine whether or not there exists an infinite word \(\alpha\) such that \(h(\alpha) = g(\alpha)\). In the general case this problem was shown to be undecidable by K. Ruohonen [Elektron. Informationsverarbeitung Kybernetik 21, 579–595 (1985; Zbl 0604.68057)]. 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.

MSC:

03D05 Automata and formal grammars in connection with logical questions
03D35 Undecidability and degrees of sets of sentences
68Q45 Formal languages and automata

Citations:

Zbl 0604.68057
PDFBibTeX XMLCite