order type bounds

[AliaumeL]

It looks like a downwards closed subset $L$ for the infix relation that is well-quasi-ordered (for the same relation) has an order type of at most $\omega^3$.

[AliaumeL]

In the case of a language $L$ that is closed under concatenations I think we have a way to prove that the width is at most $\omega$. The idea is to prove that given a fixed word $u$ the collection of words that are incomparable to it is finite.

If $u = \varepsilon$ it is trivial. Otherwise, assume by contradiction that there exists an infinite set of elements incomparable to $u$. Because the language $L$ is well-quasi-ordered, one can build an infinite increasing sequence $(v_i)$ from this set. Let us define $w_i = u vi u$, which belongs to $L$ by stability under concatenation. Extracting this sequence suitably so that $\mathrm{len}(v{i+1}) > 2 \mathrm{len}(w_i)$, we conclude that $w_i$ is a bad sequence. Indeed, if $w_i$ is a factor of $w_j$, then $u$ must be a factor of $v_j$, which is absurd.

As a consequence, the ordinal width of $L$ is at most $\omega$.

A reason why this might be of use is the following one: when $L$ is assumed to be downwards closed and well-quasi-ordered, it is a finite union of ideals, which are downwards closed subsets $I$ with the property that for any two words $u,v \in I$ there exists $w \in I$ such that both $u$ and $v$ are factors of $w$. This can be seen as a weak form of concatenation. The main issue with this construction is that one cannot control the "order" in which this concatenation appears, which I believe was already one problem in the study of amalgamation systems (hence the "strong" concatenative amalgamation).

Note that in fact a language $L$ that is WQO and closed under concatenation is likely to be super simple. Also, this proof scheme will not work for the ideal $L = a^*b^*$ where there are an infinite number of elements incomparable to $a$.

[strangeglyph]

Closure under concatenation is quite strong as a condition. Especially once you also add closure under infix, in which case you get left with a single language that satisfies both conditions -- Σ*

[AliaumeL]

Yes, but I was not using closure under infixes ^^. I now have a reasonable proof idea below.

Let $L$ be an infix order ideal (closed under infixes, and directed) that is well-quasi-ordered. Consider $u \in L$, our goal is to prove that $L_{\bot u}$, the set of all words in $L$ that are incomparable with $u$ has finite width. That this bounds the width of $L$ to at most $\omega$, as per our conjecture.

We are going to prove a stronger statement: $L{\bot u}$ is well-quasi-ordered for the prefix relation or the suffix relation. Because of our earlier results on prefixes and suffixes, this will prove that $L{\bot u}$ has finite width for one of those two relations, and in particular, an even smaller (finite) width for the infix relation.

The idea is as follows: to any element $v \in L_{\bot u}$, we associate a word $\mu(v) \in L$ that is of minimal size, and contains both $u$ and $v$ as infixes. Because $u$ is incomparable with $v$, this means that those infixes are not included one in another. Let us now consider a sequence $(vi)$ of elements in $L{\bot u}$.

Because $\mu(v_i)$ has minimal size and $L$ is closed under infixes, $\mu(v_i)$ either starts with $u$, or starts with $v_i$ (but not both, because there is no overlap). Without loss of generality, let us assume that it always starts with $u$. Let us write $d_i$ the distance between the first letter of $u$ and the first letter of $v_i$ in $\mu(v_i)$.

Claim 1. The distance $d_i$ is bounded.

Using this claim, one can extract further the sequence $(v_i)$ to assume that the distance is constant, and extract once more to assume that the word between the first position of $u$ and the first position of $v_i$ in $\mu(v_i)$ is constant. In particular, we have a word $w$ such that $\mu(v_i) = wv_i$ for all $i \in \mathbb{N}$. Let us now use the fact that $L$ is well-quasi-ordered for infixes to conclude that $w v_i$ is an infix of $w v_j$ for some $i < j$. Because of the presence of $u$ at the start of both words (that cannot be found in $v_i$ nor $v_j$) and the minimality constraint, we conclude that $w v_i$ is in fact a prefix of $w v_j$. Hence, $v_i$ is a prefix of $v_j$.

We have proven that $L_{\bot u}$ is well-quasi-ordered for the prefix relation, hence concluded. Note that if we assumed that $\mu(v_i)$ ended with $u$, we would have concluded similarly but for the infix relation.

The claim that the distance is bounded should follow from the construction of $\mu$, but I cannot seem to obtain that easily.