Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$.

What is known about $s_{L}(n)$?

Note that it is known that $s_{L}(n)$ is either polynomial, or grows exponentially if $L$ is a context-free language.

  • 2
    $\begingroup$ Possible duplicate of cstheory.stackexchange.com/questions/42190/…. $\endgroup$
    – domotorp
    Nov 23, 2019 at 7:01
  • 1
    $\begingroup$ A simple note: for every (total) function $f(n)$ that can be computed by a LBA with unary input, you can make $s_L(n) = f(n)$ (just check $x < f(n)$) $\endgroup$ Nov 25, 2019 at 7:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.