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)).
Keywords
Cite this article
@article{cai-1111,
author = {Viliam Geffert and Norbert Popély},
title = {Refinement of the Alternating Space Hierarchy},
journal = {Computing and Informatics},
volume = {21},
number = {6},
pages = {607--616},
year = {2002},
issn = {1335-9150},
url = {https://cai.type.sk/content/2002/6/refinement-of-the-alternating-space-hierarchy/}
}
TY - JOUR AU - Viliam Geffert AU - Norbert Popély TI - Refinement of the Alternating Space Hierarchy JO - Computing and Informatics VL - 21 IS - 6 SP - 607 EP - 616 PY - 2002 SN - 1335-9150 UR - https://cai.type.sk/content/2002/6/refinement-of-the-alternating-space-hierarchy/ KW - Computational complexity KW - sublogarithmic space KW - alternation ER -
Geffert, V., & Popély, N. (2002). Refinement of the Alternating Space Hierarchy. Computing and Informatics, 21(6), 607–616. https://cai.type.sk/content/2002/6/refinement-of-the-alternating-space-hierarchy/