Well quasi-orders and regular languages (Q1338899)

An extension of Myhill's theorem of automata theory, due to \textit{A. Ehrenfeucht}, \textit{D. Haussler} and \textit{G. Rozenberg} [Theoret. Comput. Sci., 27, 311-332 (1983; Zbl 0553.68044)] shows that a subset \(X\) of a semigroup \(S\) is recognizable if and only if \(X\) is closed with respect to a monotone well quasi-order on \(S\). In this paper we prove that a similar extension of Nerode's theorem is not possible by showing that there exist nonregular languages on a binary alphabet which are closed with respect to a right-monotone well quasi-order. We give then some additional conditions under which a set \(X \subseteq S\) closed with respect to a right-monotone well quasi-order becomes recognizable. We prove the following main proposition: A subset \(X\) of \(S\) is recognizable if and only if \(X\) is closed with respect to two well quasi-orders \(\leq_ 1\) and \(\leq_ 2\) which are right-monotone and left-monotone, respectively. Some corollaries and applications are given. Moreover, we consider the family \({\mathcal F}\) of all languages which are closed with respect to a right-monotone well quasi-order on a finitely generated free monoid. We prove that \({\mathcal F}\) is closed under rational operations, intersection, inverse morphisms and direct non-erasing morphisms. This implies that \({\mathcal F}\) is closed under faithful rational transductions. Finally we prove that the languges in \({\mathcal F}\) satisfy a suitable `pumping' lemma and that \({\mathcal F}\) contains languages which are not recursively enumerable.