How Large is the Set of Disjunctive Sequences?

Ludwig Staiger (Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg, Germany)

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 .

Keywords: entropy, nowhere dense sets, subword complexity, ω-languages

Categories: F.1.1, F.4.1