Refinement of the Alternating Space Hierarchy
Keywords:Computational complexity, sublogarithmic space, alternation
AbstractWe refine the alternating space hierarchy by separating the classes break sgak spa(s(n)) and piak spa(s(n)) from deak spa(s(n)) as well as from break deak+1 spa(s(n)), for each s(n)in Omega(łlgn) cap o(łgn), and k geq 2. We also present unary (tally) sets separating sga2 spa(s(n)) and pia2 spa(s(n)) from break dea2 spa(s(n)) as well as from dea3 spa(s(n)).
Download data is not yet available.
How to Cite
Geffert, V., & Popély, N. (2012). Refinement of the Alternating Space Hierarchy. COMPUTING AND INFORMATICS, 21(6), 607–616. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/477