# Language with $\log\log n$ space complexity?

We know that every non-regular language can be recognized with $\Omega (\log\log n)$ space complexity.

I'm looking for an example of a language which is $\Theta (\log\log n)$ space complexity (if such exists).

• think this can be constructed via the space hierarchy thm? also does anyone have a ref on the $\Omega(\log \log n)$ thm?
– vzn
Mar 16 '14 at 15:20

I found the answer below in lecture notes of Muli Safra.

Consider the language consisting of the following strings: \begin{align*} & 0 \ 1 \ \\ & 00 \ 01 \ 10 \ 11 \ \\ & 000 \ 001 \ 010 \ 011 \ 100 \ 101 \ 110 \ 111 \ \\ &\ldots \end{align*} This language can be recognized in space $O(\log\log n)$. For each $m$ which is smaller than the width of the first block, we check that the $m$ least significant bits form a counter modulo $m$ starting at $0$ and ending at $2^m-1$. We stop when $m$ is the width of the first block.

Since this language clearly isn't regular, it requires space $\log\log n$ (see for example these lecture notes by Hansen). We conclude that the language requires space $\Theta(\log\log n)$.

There is an interesting language that is $$\Theta({loglog(n)})$$, I found it in the free google book preview of the book "Turing Machines with Sublogarithmic Space", Here is the language:

$$C = \{a^n|F(n)\text{ is a power of 2}\}$$

$$F(n)=\min\{i|i\text{ does not divide n}\}$$ It is $$\Theta(\log\log(n))$$ because of the following construction of an accepting Turing machine $$M$$:

On an input $$w=a^n$$, $$M$$ computes $$F(n)$$ in binary and check if it is power of 2.

To compute $$F(n)$$, $$M$$ writes natural numbers in Binary format one by one up to the moment it finds that the number does not divide $$n$$ on its tape.

To check if a number written in binary on its tape divides $$n$$, it suffices to use a modulo $$k$$ counter on the tape and go from one end of the input to the other, counting $$a$$ symbols.

$$F(n) \le c*\log(n)$$( the proof is included in the book as lemma 4.1.2(d)) thus the space needed for storing the binary representation of $$F(n)$$ is $$O(\log \log (n))$$ and it is easy to check whether a number written in Binary format is a power of two or not, so the language $$C$$ is space bounded by $$O(\log \log (n))$$.

Other interesting property of this language is that it is not a regular language and the proof using pumping lemma is also included in the book. Any language needing strictly asymptotically less space(i.e languagues that space bounded $$o(\log \log n)$$) are regular.