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.