Sublinear Space Real-Time Turing Machines Cannot Count
Stefan D. Bruda · 2011
We show that sub linear-space bounded real-time, deterministic or nondeterministic Turing machines are equivalent to finite automata. Non-regular real-time definable languages (and also quasi-real-time languages, their nondeterministic extension) can thus only be accepted with linear or super linear work space.