Super-stationary set, subword problem and the complexity

Let Ω ⊂ {0, 1}^N be a nonempty closed set with N = {0, 1, 2, ...}. For N = {N₀ < N₁ < N₂ < ⋯} ⊂ N and ω ∈ {0, 1}^N, define ω [N] ∈ {0, 1}^N by ω [N] (n) {colon equals} ω (N_n) (n ∈ N) and Ω [N] {colon equals} {ω [N] ∈ {0, 1}^N ; ω ∈ Ω} . We call Ω a super-stationary set if Ω [N] = Ω holds for any infinite subset N of N. Denoting Ω^′ the derived set (i.e. the set of accumulating points) of Ω and deg Ω = inf {d ; Ω^{(d + 1)} = 0{combining long solidus overlay}} with Ω⁽¹⁾ = Ω^′, Ω⁽²⁾ = (Ω^′)^′, ..., it is known [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)] that for any nonempty closed subset Ω of {0, 1}^N such that there exists an infinite subset N of N with deg Ω [N] < ∞, there exists an infinite subset M such that Ω [M] is a super-stationary set. Moreover, if deg Ω [N] = ∞ for any infinite subset N of N, then the maximal pattern complexity [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)] p_Ω^* (k) is 2^k (k = 1, 2, ...). Thus, the uniform complexity functions are realized by the super-stationary sets [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)]. We call ξ ∈ {0, 1}^* a super-subword of ω ∈ {0, 1}^N if there exists S = {s₁ < s₂ < ⋯ < s_k} with k = | ξ | such that ξ = ω [S] {colon equals} ω (s₁) ω (s₂) ⋯ ω (s_k). Let P (ξ) be the set of ω ∈ {0, 1}^N having no super-subword ξ. Denote Q (Ξ) = under(∪, ξ ∈ Ξ) P (ξ) and P (Ξ) = under(∩, ξ ∈ Ξ) P (ξ), where Ξ ⊂ {0, 1}^*. In this paper, we prove that the class of super-stationary sets other than {0, 1}^N coincides with the class of Q (Ξ) for nonempty finite sets Ξ ⊂ {0, 1}⁺. Moreover, it also coincides with the class of P (L (Ξ)) for nonempty finite sets Ξ ⊂ {0, 1}⁺, where L (Ξ) is the set of minimal covers of Ξ. Using these expressions, we can calculate the complexity of super-stationary sets and prove that the complexity function of a super-stationary set in k is either 2^k or a polynomial function of k for large k. We also discuss the word problems related to the super-subwords.