Language-Theoretic Complexity of Disjunctive Sequences

Cristian Calude
Computer Science Department, The University of Auckland, Private Bag 92109, Auckland, New Zealand

Sheng Yu
Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7


A sequence over an alphabet $\Sigma$ is called disjunctive if it contains all possible finite strings over $\Sigma$ as its substrings. Disjunctive sequences have been recently studied in various contexts. They abound in both category and measure senses.

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 context-sensitive, but no language P(x) associated 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 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 \in \Sigma^{\omega}$ such that P(x) is context-free but not regular. If the set of all finite substrings of a sequence $x \in \Sigma^{\omega}$ 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.

Conference Home Page