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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.