×

Decidability of the intercode property. (English) Zbl 0824.68061

Summary: A language \(L\) over an alphabet \(X\) is said to be an intercode of index \(m\) if \(L^{m + 1} \cap X^ + L^ mX^ + = \emptyset\). For any fixed index \(m\) it is obviously decidable whether a regular language is an intercode of index \(m\). On the other hand, it has been an open question whether it is decidable for a regular language if there is an index \(m\) such that the language is an intercode of that index \(m\). We answer this question in the affirmative.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite