Implicit characterization of sublogarithmic space

Question

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.

Answer 1

In general, sublogarithmic classes are not robust i.e. the class of problems is not invariant under the machine model chosen. This is partly because, in general, closure properties do not hold for such classes. In particular, Immerman-Szelencsenyi theorem (closure under complementation) and Savitch's theorem (closure under non-determinism) doesn't necessarily hold for sublogarithmic classes.

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.