Abstract:
A sequence over an alphabet ∑ is called disjunctive [13] if it contains all possible finite strings
over ∑ as its substrings. Disjunctive sequences have been recently studied in various contexts, e.g.
[12, 9]. They abound in both category and measure senses [5].
In this paper we measure the complexity of a sequence x by the complexity of the language
P(x) consisting of all prefixes of x. The languages P(x) associated to disjunctive sequences can be
arbitrarily complex. We show that for some disjunctive numbers x the language P(x) is contextsensitive,
but no language P(x) associate to a disjunctive number can be context-free. We also show
that computing a disjunctive number x by rationals corresponding to an infinite subset of P(x) does
not decrease the complexity of the procedure, i.e. if x is disjunctive, then P(x) contains no infinite
context-free language. This result reinforces, in a way, Chaitin's thesis [6] according to which perfect
sets, i.e. sets for which there is no way to compute infinitely many of its members essentially better
(simpler/quicker) than computing the whole set, do exist. Finally we prove the existence of the
following language-theoretic complexity gap: There is no x Є ∑ω such that P(x) is context-free but
not regular. If the set of all finite substrings of a sequence x Є ∑ω is slender, then the set of all
prefixes of x is regular, that is P(x) is regular if and only if S(x) is slender. The proofs essentially
use some recent results concerning the complexity of languages containing a bounded number of
strings of each length [15, 14, 11, 16].