New Results on the Minimum Amount of Useful Space
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 space, (ii) 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 space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong space, and, (v) there exist unary nonregular languages accepted by two-way one-counter automata using quantum and classical states with middle space and bounded error.