科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let Omega subset of {0, 1}(N) be a nonempty closed set with N = {0, 1, 2,...,}. For N = {N(0) < N(1) < N(2) < ...} subset of N and omega is an element of {0, 1}(N), define omega[N] is an element of {0, 1}(N) by omega[N](n) := omega(N(n)) (n is an element of N) and Omega[N] := {omega[N] is an element of {0, 1}(N); omega is an element of Omega}. We call Omega a super-stationary set if Omega[N] = Omega holds for any infinite subset N of N. Denoting Omega'; the derived set (i.e. the set of accumulating points) of Omega and deg Omega = inf {d: Omega((d+1)) = empty set} with Omega((1)) = Omega';, Omega((2)) = (Omega';)';,..., 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 Omega of {0, 1}(N) such that there exists an infinite subset N of N with deg Omega[N] < infinity, there exists an infinite subset M such that Omega[M] is a super-stationary set. Moreover, if deg Omega[N] < infinity for any infinite subset X of K then the maximal pattern complexity IT. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)] p(Omega)*(k) is 2(k) (k = 1, 2,...). Thus, the uniform complexity functions are realized by the super-stationary sets IT. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)]. We call xi is an element of {0, 1}* a super-subword of omega is an element of {0, 1}(N) if there exists S = {s(1) < s(2) < ... < s(k)) with k = |xi| such that xi = omega|S| := omega(s(1))omega(s(2))... omega(s(k)). Let P(xi) be the set of omega is an element of {0, 1}(N) having no super-subword xi. Denote Q(Xi) = boolean OR(xi is an element of Xi) P(xi) and P(Xi) = boolean AND(xi is an element of Xi) P(xi), where Xi subset of {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(Xi) for nonempty finite sets Xi subset of {0, 1}(+). Moreover, it also coincides with the class of P(L(Xi)) for nonempty finite sets Xi subset of {0, 1}(+), where L(Xi) is the set of minimal covers of Xi. 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.
