Refinement of the Alternating Space Hierarchy

Abstract

We 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)).