Two lower bounds on computational complexity of infinite words

Abstract

The most of the previous work on the complexity of infinite words has measured the complexity as descriptional one, i. e. an infinite word w had a “small” complexity if it was generated by a morphism or another simple machinery, and w has been considered to be “complex” if one needs to use more complex devices (gsm's) to generate it. In [5] the study of the computational complexity of infinite word generation and of its relation to the descriptional characterizations mentioned above was started. The complexity classes GSPACE(f) = {infinite words generated in space f(n)} are defined there, and some fundamental mechanisms for infinite word generation are related to them. It is also proved there, that there is no hierarchy between GSPACE(O(1)) and GSPACE(log₂ n). Here, GSPACE(f) ⊂ GSPACE(g) for g(n)≥f(n)≥log₂ n, f(n)=o(g(n)) is proved. The main result of this paper is a new lower bound on the computational complexity of infinite word generation: real-time, binary working alphabet, and o(n/(log n)² space is insufficient to generate a concrete infinite word over two-letter alphabet.

This author was partially supported by the Slovak Scientific Grant Agency Grant No. 95/5305/277.