###
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