[Solved]: Language with $\log\log n$ space complexity?

Problem Detail: 

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

Asked By : Roi Divon

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22676

 Ask a Question

 Download Related Notes/Documents