3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – coppro
    Aug 14 '14 at 8:31
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, do you know where I'd find this result? $\endgroup$
    – coppro
    Aug 14 '14 at 8:32
  • $\begingroup$ 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. $\endgroup$
    – Gro-Tsen
    Apr 24 '16 at 18:17
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @coppro Fun questions, in any case! $\endgroup$ Aug 16 '14 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.