What complexity implications are there from not being in an abstract family of languages?
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. Naturally I don't care about trivial results like "If a language is not $\mathrm{DSPACE}\left(n^2\right)$ then it requires $\omega(n^2)$ space". I am 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.

0 comment threads