What complexity implications are there from not being in a abstract family of languages?

Question

A classic result is that a if a language is not regular its decision problem requires more than constant memory (i.e. $\Omega(\log \log n)$).

I am wondering if there are similar results for other classes of language (e.g. context-free or tree-adjoining). Specifically results of the form

If a language is not a $X$, then it must have space/time complexity $\omega(f)$ (or $\Omega(f)$)

where $X$ is some abstract family of languages language. Naturally I don't care about trivial results like "If a language is not $\mathrm{DSPACE}\left(n^2\right)$ then it's $\omega(n^2)$". I'm particularly interested when $X$ is between regular and context-sensitive.

I had a look for myself, and I was of course able to find tons of results that being a particular class of formal language implies the existence of an algorithm of a certain complexity, but none more of the form like the above.

• Emil Jeřábek: Well, ignoring the difference between "all sufficiently large" and "infinitely many", and taking the contrapositive, the results you seek just say "$\def\ds{{\sf DSPACE}}\ds(f)\let\ss\subseteq\ss X$ (resp. $\ds(o(f))\ss X$)". I am not aware of any such results besides well known relationships such as $\ds(f)\ss{\sf DTIME}(2^{O(f)}),ドル $\ds(f)\ss{\sf ATIME}(f^2),ドル $\ds(f)\ss{\sf NSPACE}(f),ドル $\ds(n)\ss{\sf CSL}$.
• Emil Jeřábek: There are certainly no known interesting "gap results" analogous to the gap between space $O(1)$ and space $\log\log n$ that you mention. (There is Blum's speed-up theorem, but this exploits an unnatural artificially constructed function $f,ドル which IIRC will also be fast growing.) The space hierarchy theorem ensures that there are no such gaps between ${\sf DSPACE}(f)$ and ${\sf DSPACE}(g)$ for space-constructible functions $f,g$.
• Emil Jeřábek: To point it out explicitly, the difference between "all sufficiently large" and "infinitely many" does matter here. In particular, the classical result you mention actually says that ${\sf DSPACE}(o(\log\log n))={\sf REG}$. This only means that a nonregular language requires space $\ge c\log\log n$ for infinitely many $n,ドル which is weaker than $\Omega(\log\log n)$. The language I gave in a comment to D.W.'s answer is a counterexample to your statement: it is not regular (or even CSL), but it is decidable in space $f(n)$ for a certain function $f$ such that $f(n)=O(1)$ for all odd $n$.
• Sriotchilism O'Zaic: @EmilJeřábek $\Omega(\log\log n)$ worst-case space complexity is how I feel I have most often seen the result stated. I think it is correct if you are implicitly defining "worst-case" to be the most space used for any input of size $i \leq n$. In other words, taking the worst case over balls of increasing size rather than spheres. I hadn't really thought about this technicality before and it's a good point. Thank you.
• Emil Jeřábek: I haven’t seen the result formulated that way (at least not in reputable sources), and I don’t see why it shoud be true even you define space complexity so that it takes into account words not just of length $n,ドル but of length $\le n$ (which is certainly nonstandard). The usual proof counting crossing sequences such as in wisdom.weizmann.ac.il/~oded/PS/CC/l4.ps does not give this stronger conclusion.

Answer 1

A language $L$ is context-sensitive iff it is in $NSPACE(O(n))$.

Therefore, if a language is not context-sensitive, it must have non-deterministic space complexity $\omega(n)$. It follows that if a language is not context-sensitive, it must also have deterministic space complexity $\omega(n)$.

• Emil Jeřábek: ... for infinitely many $n,ドル not necessarily for all $n$. E.g., consider an EXPSPACE language suitably padded so that all words have even length, while keeping all odd-length words outside the language.