<p>In case you don't want to read the book, take the numbers written in binary from 1 to n, separated by a comma.</p>

CC BY-SA 3.0
2013-11-30T21:14:48.873Z
2013-11-30T21:14:48.873Z
domotorp
<p>Yes. I think the main reference is <a href="http://link.springer.com/book/10.1007/3-540-58355-6/page/1">Turing Machines with Sublogarithmic Space</a> by Szepietowski (1994). (Link to <a href="http://books.google.com/books?isbn=3540583556">books.google</a>)</p>

CC BY-SA 3.0
2013-11-30T20:59:41.727Z
2013-11-30T20:59:41.727Z
Abuzer Yakaryilmaz
<p>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.</p>

CC BY-SA 3.0
2013-11-30T19:33:54.790Z
Yes. You can check the book by Szepietowski (1994) http://link.springer.com/book/10.1007/3-540-58355-6/page/1
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-11-30T20:43:40.803Z
@AbuzerYakaryilmaz maybe make this an answer ?
Suresh Venkat
CC BY-SA 3.0
2013-11-30T21:01:12.920Z
@SureshVenkat: I did :)
Abuzer Yakaryilmaz
<cc.complexity-theory><space-complexity>
Nonregular Languages in Sublogarithmic Space
Lev Reyzin
# Nonregular Languages in Sublogarithmic Space

(Asked by: username_0 on 2013-11-30)

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.

**Tags:** cc.complexity-theory, space-complexity

> **Comments:**
> **username_1**: Yes. You can check the book by Szepietowski (1994) http://link.springer.com/book/10.1007/3-540-58355-6/page/1  
> **username_2**: @AbuzerYakaryilmaz maybe make this an answer ?  
> **username_1**: @SureshVenkat: I did :)  

---

## 2 answers

### Answer by username_1 on 2013-11-30. Score: 7 | Accepted answer

Yes. I think the main reference is [Turing Machines with Sublogarithmic Space](http://link.springer.com/book/10.1007/3-540-58355-6/page/1) by Szepietowski (1994). (Link to [books.google](http://books.google.com/books?isbn=3540583556))


---

### Answer by username_3 on 2013-11-30. Score: 2

In case you don't want to read the book, take the numbers written in binary from 1 to n, separated by a comma.


---

