6
$\begingroup$

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

$\endgroup$
1
  • $\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
9
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.