2014/05/12 by Zuzana Bednárová, Viliam Geffert, Bednárová, Zuzana +5
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Physics (quant-ph) #cs.CC #cs.FL #quant-ph
paper · pdf · doi:10.48550/arxiv.1405.2892
21 pages. An extended and revised version with two new authors
arxiv created 2015/08/04 · arxiv updated 2015/08/05
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 loglog n space, (ii) loglog 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 loglog 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.