# Implicit characterization of sublogarithmic space

Let $$SUBLOG = DSPACE(o(\log(n)) \setminus DSPACE(O(1))$$ be the set of languages decidable with less than logarithmic space, but more than a constant amount of space, on a multi-tape Turing machine with a read-only input tape.

We have good implicit characterizations of constant space, i.e. regular languages, such as regular expressions or finite-state machines. Likewise, many circuit classes or larger space/time classes have good implicit characterizations: constant-depth circuit classes have logical representations using quantifier types that correspond to the gates, while $$L$$ and $$P$$ have characterizations due to Jones and Bellantoni/Cook respectively as restricted programming languages.

Are there any good known implicit characterizations / descriptive complexity approaches to sublogarithmic space (specifically any subclasses of $$SUBLOG$$)? I know the lack of robustness of sublogarithmic space makes such a characterization unlikely, so I'd be happy even with partial results in this direction.

• I think this reflects upon the distinction between implicit and descriptive complexity. The approach in implicit complexity is to take each datum (e.g. a string) as a single point, whereas in descriptive complexity a string is regarded as a finite structure. In practice, this means descriptive complexity is better at capturing small classes, though I'm not sure about sublogarithmic space. Commented Sep 15, 2023 at 16:03
• That said, I wonder whether there's a characterization of SUBLOG in terms of Neil Jones' cons-free programs Commented Sep 15, 2023 at 16:06
• isn't that just empty set? Commented May 12 at 2:21

However, one can consider sublogarithmic circuit classes like uniform $$AC_0$$ and $$NC_1$$. These have nice descriptive complexity descriptions: $$AC_0=FO(+,\times)$$ and for $$NC_1$$ see here. In terms of implicit complexity, I am aware of this work that attempts a characterisation using proof nets.
On a different note, there is a nice characterisation of $$L$$ (and $$NL$$ respectively) by $$k$$-pebble deterministic (non-deterministic respectively) automata. Maybe, there are some natural restrictions out there of these to capture sublogarithmic classes.
• But sublogarithmic space classes are known to be closed under complement, see "Halting Space-Bounded Computations" by Sipser. And a lack of (known) closure under nondeterminism doesn't really seem important in this case -- after all, $P$ and $L$ are not known to be closed under nondeterminism, but there are many implicit characterizations of both classes.