科研之友
微信
新浪微博
Facebook
分享链接
摘要
For a nonempty closed subset Omega of {0, 1}(Sigma), where Sigma is a countably infinite set. let p(Omega) (S) := #pi(S)Omega be the complexity function depending on the nonempty finite sets S subset of Sigma, where # denotes the number of elements in a set and pi(s) : {0, 1}(Sigma) -> {0, 1}(S) is the projection. Define the maximal pattern complexity function p(Omega)* (k) := sup(s:#s=k) p(Omega)(S) as a function of k = 1, 2,.... We call Omega a uniform set if p(Omega) (S) depends only on #S = k, and the complexity function p(Omega)(k) := p(Omega)(S) as a function of k = 1, 2.... is called the uniform complexity function of Omega. Of course, we have p(Omega) (k) = p(Omega)*(k) in this case. Such uniform sets appear, for example, as the partitions generated by congruent sets in a space with optimal positionings, or they appear as the restrictions of a symbolic system to optimal windows. Let Omega' be the derived set (i.e. the set of accumulating points) of Omega and deg Omega := inf{d; Omega((d 1)) = 0} with Omega((1)) = Omega', Omega((2)) = (Omega')',.... We prove that for any nonempty closed subset Omega of (0, 1)(N), where N = {0, 1, 2....}, such that deg(Omega o rho) < infinity for some injection rho : N -> N, there exists an increasing injection phi : N -> N such that Omega o phi o psi = Omega o phi for any increasing injection psi : N -> N. Such a set Omega o phi is called a super-stationary set. Moreover, if deg(Omega o rho) = infinity for any injection rho : N -> N, then p(Omega)*(k) = 2(k) (k = 1, 2,...) holds. A uniform set Omega subset of {0, 1}(Sigma) is said to have a primitive factor [Omega o phi] if there exists an injection phi : N -> Sigma such that Omega o phi is a super-stationary set, where [Omega o phi] is the isomorphic class containing Omega o phi. Then, any uniform set has at least one primitive factor, and hence, any uniform complexity function is realized by the uniform complexity function of a super-stationary set. It follows that the uniform complexity function p(Omega)(k) is either 2(k) for any k or a polynomial function of k for large k.
- 出版日期2009-6-28
