Language-Theoretic Complexity of Disjunctive Sequences

Cristian Calude
Computer Science Department, The University of Auckland, Private Bag 92109, Auckland, New Zealand
cristian@cs.auckland.ac.nz

Sheng Yu
Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7
syu@csd.uwo.ca

Abstract

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