𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Another generalization of Higman's well quasi order result on Σ∗

✍ Scribed by David Haussler


Book ID
103055941
Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
413 KB
Volume
57
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis


We present another generalization of Higman's result ([2]) that the subsequence embedding relationship on a finitely generated free monoid is a well quasi order. Our result is analogous to the generalization of Higman's result given in in the following manner. In the quasi orders we consider, we are given a finite set S of non-null words from ~* and we demand that x t • • • xk+ t is less than or equal to xta 1 •. • XkakJCk+ 1 for any words xl,..., xk+xeI* and any single word a t • .. a k ~ S, where ai~ ~Z, 1 ~<i<~k. The least quasi order obtained in this fashion is denoted ~<s-In contrast to the notion of subword unavoidability used in [1], S is said to be subsequence unavoidable (in ~*) if and only if there exists a k 0 such that any word longer than k o has a (nonempty) subsequence of letters (not necessarily contiguous) which form a word in S. We show that ~<s is a well quasi order on ~* if and only if S is subsequence unavoidable in ~*. As an application of this result, we show that the iterated shuffle ([1], [7], [8]) of a finite set S with itself is a regular language if and only if S is subsequence unavoidable.


📜 SIMILAR VOLUMES