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

  • $\begingroup$ think this can be constructed via the space hierarchy thm? also does anyone have a ref on the $\Omega(\log \log n)$ thm? $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.