# 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

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)$.