Refinement of the Alternating Space Hierarchy.
Viliam Geffert, Norbert Popély · 2002
We refine the alternating space hierarchy by separating the classes Σ κ -SPACE(s(n)) and Π κ -SPACE(s(n)) from Δ κ -SPACE(s(n)) as well as from Δ κ+1 -SPACE(s(n)), for each s(n) E Ω(log log n) ∩ o(log n), and κ ≥ 2. We also present unary (tally) sets separating Σ 2 -SPACE(s(n)) and H 2 -SPACE(s(n)) from Δ 2 -SPACE(s(n)) as well as from Δ 3 -SPACE(s(n)).