Language-theoretic complexity of disjunctive sequences

✍ Scribed by Cristian Calude; Yu Sheng

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 438 KB
• Volume: 80
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00061-9

✦ Synopsis

A sequence over an alphabet Z is called disjunctirr if it contains all possible finite strings over .Z 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) does not have an infinite context-free subset. This result reinforces, in a way, Chaitin's thesis (1969) according to which pwfcct 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 E 2"" such that P(x) is context-free but not regular. If S(X), the set of all finite substrings of a sequence x E I"', 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. 62 1997 Elsevier Science B.V.