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.
- Commutative one-counter languages are regular
- Finiteness and iteration conditions for semigroups
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 3179521 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 45433 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- On regularity of context-free languages
- Ordering by Divisibility in Abstract Algebras
- Some applications of a theorem of Shirshov to language theory
- The theory of well-quasi-ordering: a frequently discovered concept
- On the regularity of languages on a binary alphabet generated by copying systems
- On well quasi orders of free monoids
- On well quasiordering of finite languages
- On the generalization of Higman and Kruskal's theorems to regular languages and rational trees
- Well-quasi-orders and regular \(\omega\)-languages
- Well quasi ordering finite posets and formal languages
- On classes of regular languages related to monotone WQOs
- Stefano Varricchio (1960-2008)
- WQO is decidable for factorial languages
- Regular solutions of language inequalities and well quasi-orders
- Well quasi-orders, unavoidable sets, and derivation systems
- Well Quasi-orders in Formal Language Theory
- scientific article; zbMATH DE number 7559411 (Why is no real title available?)
- Regular tree languages and quasi orders
- Automata, Languages and Programming
- Operations preserving recognizable languages.
- FORQ-Based Language Inclusion Formal Testing
- Antichains algorithms for the inclusion problem between \(\omega\)-VPL
- Language inclusion algorithms as complete abstract interpretations
- Well quasi-orders and context-free grammars
- On regularity of context-free languages
- Well quasi-orders generated by a word-shuffle rewriting
This page was built for publication: Well quasi-orders and regular languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1338899)
