Let $s_L(n)$ denote the number of words of length $n$ in $L$.

For context-free languages it is known that $s_L(n)$ is either polynomial or exponential. For context-sensitive languages this is probably not true and I would like to study counterexamples.

I am interested in an example of a context-sensitive language that has $s_L(n)=\Theta(r^{(n^\delta)})$ for a real $r>1$ and $\delta<1$ or $s_L(n)=\Theta(r^{(\log^c(n))})$ for $c>1$.


The language $$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$ is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\lfloor n^\delta\rfloor}$.

The language $$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor(\log n)^c\rfloor}0^{n-\lfloor(\log n)^c\rfloor}$$ is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\lfloor(\log n)^c\rfloor}$.

You can construct any number of examples like this. Basically, if $f\colon\mathbb N\to\mathbb N$ is any function such that given $n$ in binary, $f(n)$ (in binary) is computable in space $O(n)$ (which is exponential space in terms of the length of its input) and $f(n)\le2^n$, then there exist languages $L\in\mathrm{DSPACE}(n)\subseteq\mathrm{CSL}$ such that $s_L(n)=f(n)$, such as $$L=\bigcup_{n\in\mathbb N}\bigl\{w\in\{0,1\}^n:w<_\mathrm{Lex}\operatorname{bin}(f(n))\bigr\},$$ where $<_\mathrm{Lex}$ denotes lexicographic order, and $\operatorname{bin}(f(n))\in\{0,1\}^n$ is the binary expansion of $f(n)$.

In fact, it is easy to give an exact characterization along the same lines. Let me say that a nondeterministic TM computes a function $f\colon \mathbb N\to\mathbb N$ if for every input $x\in\mathbb N$ (in binary),

  • there exists a run of the machine that computes $f(x)$ (in binary), and

  • all runs either compute $f(x)$ or report a failure.

Then using the construction above and the Immerman–Szelepcsényi theorem, one can show that for any $f\colon\mathbb N\to\mathbb N$, the following are equivalent:

  • $f=s_L$ for some language $L\in\mathrm{CSL}$;

  • $f(n)$ is computable on a nondeterministic TM in space $O(n)$, including the size of the output.

(Note that base conversion can be done in linear space, hence it is immaterial whether we choose binary or any other base $b\ge2$.)


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.