  We present several new results on minimal space requirements to recognize a
nonregular language: (i) realtime nondeterministic Turing machines can
recognize a nonregular unary language within weak $\log\log n$ space, (ii)
$\log\log n$ is a tight space lower bound for accepting general nonregular
languages on weak realtime pushdown automata, (iii) there exist unary
nonregular languages accepted by realtime alternating one-counter automata
within weak $\log n$ space, (iv) there exist nonregular languages accepted by
two-way deterministic pushdown automata within strong $\log\log n$ space, and,
(v) there exist unary nonregular languages accepted by two-way one-counter
automata using quantum and classical states with middle $\log n$ space and
bounded error.
