Nonregular Languages in Sublogarithmic Space Are there any known languages that require $o(\log n)$ space but are also not regular?  I'm looking for a problem "just below" undirected connectivity.
Yes. I think the main reference is Turing Machines with Sublogarithmic Space by Szepietowski (1994). (Link to books.google)