Another generalization of Higman's well quasi order result on \(\Sigma ^*\) (Q1069312): Difference between revisions

We present another generalization of \textit{G. Higman}'s result [Proc. Lond. Math. Soc., III. Ser. 2, 326-336 (1952; Zbl 0047.034)] 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 by \textit{A. Ehrenfeucht}, \textit{D. Haussler} and \textit{G. Rosenberg} [Theor. Comput. Sci. 27, 311-332 (1983; Zbl 0553.68044)] in the following manner. In the quasi orders we consider, we are given a finite set S of non-null words from \(\Sigma^*\) and we demand that \(x_ 1\ldots x_{k+1}\) is less than or equal to \(x_ 1a_ 1\ldots x_ ka_ kx_{k+1}\) for any words \(x_ 1\ldots x_{k+1}\in \Sigma^*\) and any single word \(a_ 1\ldots a_ k\in S\), where \(a_ i\in \Sigma\), \(1\leq i\leq k\). The least quasi order obtained in this fashion is denoted \(\lesssim_ S\). In contrast to the notion of subword unavoidability used by \textit{A. Ehrenfeucht}, \textit{D. Haussler} and \textit{G. Rosenberg} [loc. cit.], S is said to be subsequence unavoidable (in \(\Sigma^*)\) if and only if there exists a \(k_ 0\) such that any word longer than \(k_ 0\) has a (nonempty) subsequence of letters (not necessarily contiguous) which form a word in S. We show that \(\lesssim_ S\) is a well quasi order on \(\Sigma^*\) if and only if S is subsequence unavoidable in \(\Sigma^*\). As an application of this result, we show that the iterated shuffle of a finite set S with itself is a regular language if and only if S is subsequence unavoidable.