patternModerate
Language with $\log\log n$ space complexity?
Viewed 0 times
spacelogwithlanguagecomplexity
Problem
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).
(\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).
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#22676, answer score: 11
Revisions (0)
No revisions yet.