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 '19 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 '19 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.