Abstract: Let be a nonempty closed set with . For and , define by and We call a super-stationary set if holds for any infinite subset of . Denoting the derived set (i.e. the set of accumulating points) of and 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 such that there exists an infinite subset of with , there exists an infinite subset such that is a super-stationary set. Moreover, if for any infinite subset of , then the maximal pattern complexity [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)] is . 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 a super-subword of if there exists with such that . Let be the set of having no super-subword . Denote where . In this paper, we prove that the class of super-stationary sets other than coincides with the class of for nonempty finite sets . Moreover, it also coincides with the class of for nonempty finite sets , where 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 is either or a polynomial function of for large . We also discuss the word problems related to the super-subwords. [Copyright &y& Elsevier]