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