JUCS - Journal of Universal Computer Science 8(2): 348-362, doi: 10.3217/jucs-008-02-0348
How Large is the Set of Disjunctive Sequences?
expand article infoLudwig Staiger
‡ Martin-Luther-University Halle-Wittenberg, Wittenberg, Germany
Open Access
Abstract
We consider disjunctive sequences, that is, infinite sequences -words) having all finite words as infixes. It is shown that the set of all disjunctive sequences can be described in an easy way using recursive languages and, besides being a set of measure one, is a residual set in Cantor space. Moreover, we consider the subword complexity of sequences: here disjunctive sequences are shown to be sequences of maximal complexity. Along with disjunctive sequences we consider the set of real numbers having disjunctive expansions with respect to some bases and to all bases. The latter are called absolutely disjunctive real numbers. We show that the set of absolutely disjunctive reals is also a residual set and has representations in terms of recursive languages similar to the ones in case of disjunctive sequences. To this end we derive some fundamental properties of the functions translating a base r-expansion of a real [0, 1] into . 1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen.
Keywords
ω-languages, nowhere dense sets, entropy, subword complexity