7
$\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, 2014 at 15:20

2 Answers 2

11
$\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$ I have pondered for a while but i still don't get your explanation, for me i don't see how to have anything but a log(n) counter $\endgroup$
    – ULechine
    Jul 13, 2023 at 14:59
  • $\begingroup$ The input of length $n$ is composed of strings of length roughly $\log n$ separated by dollar signs, hence it suffices to count up to roughly $\log\log n$. $\endgroup$ Jul 29, 2023 at 14:42
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 and acknowledge you have read our privacy policy.

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