Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by deleting certain letters in $w'$.
The well-known "Higman's lemma" states that $\leq$ is a well partial order, meaning that any total order extending it is a well-order. Furthermore, the least upper bound $o(\Sigma^*,\leq)$ of the ordinals of such well-orderings is $\omega^{\omega^{n-1}}$ where $n:=\#L$ (and it is attained) by results of de Jongh and Parikh (“Well-Partial Orderings and Hierarchies”, Nederl. Akad. Wetensch. Proc. Ser. A 80 = Indag. Math. 39 (1977), 195–207, esp. thm. 3.11 & 2.13).
Now let $L\subseteq\Sigma^*$ be a rational (=regular) language (i.e., recognizable by a finite automaton, or inverse image of a subset of a finite monoid $M$ by a homomorphism of monoids $\Sigma^*\to M$). The set $L$ is still well partially ordered by $\leq$.
Question: How can we compute the ordinal $o(L,\leq)$ (the least upper bound of well-orderings of $L$ extending $\leq$) from a description of $L$ (by finite automaton, regular expression, or morphism of monoids)?
Comment 1: I expect this ordinal to have a close connection with the generating function or growth rate of $L$. So I could add a number of questions of related interest: is the ordinal determined by the generating function or vice versa? or can we at least bound one in terms of the other? (Sadly, neither the words "Higman" nor "ordinal" seem to appear in Flajolet & Sedgewick's Analytic Combinatorics.)
Comment 2: Maybe the problem can be made simpler by restricting ourselves to languages of the form $L(w_1,\ldots,w_r)$ defined as $\{w\in\Sigma^* : (\forall i)(w_i\not\leq w)\}$ (i.e., words not containing any of the $w_i$ as subword), which are of particular interest in this context: see de Jongh & Parikh's paper cited above. I think $o(L(w_1),\leq) = \omega^{\omega^{n-2} k}$ where $k := |w_1|$, but even this I'm not sure of.
