WELL QUASI-ORDERS AND REGULAR LANGUAGES

An extension of Myhill's theorem of automata theory, due to Ehrenfeuch t et al. [4] 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 o n S. In this paper we prove that a similar extension of Nerode's theor em is not possible by showing that there exist non-regular languages o n 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 subset of or equal to S closed with respect to a right-monoton e well quasi-order becomes recognizable. We prove the following main p roposition: A subset X of S is recognizable if and only if X is closed with respect to two well quasi-orders less than or equal to(1) and le ss than or equal to(2) which are right-monotone and left-monotone, res pectively. Some corollaries and applications are given. Moreover, we c onsider the family 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 F is closed under rational operations, intersection, i nverse morphisms and direct non-erasing morphisms. This implies that F is closed under faithful rational transductions. Finally we prove tha t the languages in F satisfy a suitable 'pumping' lemma and that F con tains languages which are not recursively enumerable.