# Are there any results on well-quasi-ordering of languages?

There are a number of papers that I can find about well-quasi-orders in formal lnaguage theory, by Kunc, de Luca, D'Alessandro, and Varricchio, among others. I am interested, however, in well-quasi ordering results on languages themselves---that is, on subsets of $A^*$ rather than on $A^*$ directly.

Does anyone know of any work in this area? An example of the kind of question I would like to find an answer to is as follows:

Let $A$ be a (possibly infinite) alphabet well-quasi-ordered by $\preceq$. Given $v = v_1 v_2 \dotsc v_n \in A^*$ and $w = w_1 w_2 \dotsc w_m \in A^*$, we say that $v \stackrel{\mathrm W}{\preceq} w$ if $n = m$ and $v_i \preceq w_i$ for $1 \le i \le n$. We then say that, for $L_1, L_2 \subseteq A^*$, $L_1 \stackrel{\mathrm L}{\preceq} L_2$ if and only if for each $v \in L_1$, there is $w \in L_2$ such that $v \stackrel{\mathrm W}{\preceq} w$.

Does $\stackrel{\mathrm L}{\preceq}$ well-quasi-order the prefix-closed regular languages over $A^*$?

EDIT: Changed to prefix-closed as there's a trivial counterexample on all regular languages.

Does $\stackrel{\mathrm L}{\preceq}$ well-quasi-order the regular languages over $A^*$?

No, let $L_n$ contain all strings of length $n$, then the $L_n$ form an infinite antichain. So $\stackrel{\mathrm L}{\preceq}$ is not a wqo.

• Yeah, my bad. I wrote it down wrong, serves me right. Meant to ask about the prefix-closed regular languages, where there isn't such a trivial counterexample. Aug 14 '14 at 8:31

You could use the following general result. Given a well quasi-order $\leqslant$ on a set $E$, the quasi-order on $\mathcal{P}(E)$ defined by $X \leqslant Y$ if and only if for each element $x \in X$, there is an element $y \in Y$ such that $x \leqslant y$, is also a well quasi-order. This applies in particular to $E = A^*$ and so you can obtain plenty of well quasi-orders on the set of languages of $A^*$ in this way.

• Thanks, do you know where I'd find this result? Aug 14 '14 at 8:32
• I think this is wrong in general: it is precisely the difference between the "well-quasi-order" (wqo) and the "better-quasi-order" (bqo) properties (see, e.g., arXiv:math/0601119 by Pouzet and Sauer) that bqo passes from $E$ to $\mathcal{P}(E)$ whereas wqo in general does not. However, $A^*$ is indeed bqo by a result of Nash-Williams (somewhere in his 1963–1968 papers) so I agree with the conclusion. Apr 24 '16 at 18:17

Does $\stackrel{\mathrm L}{\preceq}$ well-quasi-order the prefix-closed regular languages over $A^*$?

No, let $L_n$ be the set of all prefixes of $0^n10^\infty$. Then the $L_n$ are prefix-closed, regular, and form an infinite antichain. For instance, $L_0$ contains $1000$ and $L_1$ contains $0100$, and these are incomparable words.

• @coppro Fun questions, in any case! Aug 16 '14 at 0:04