Refinement of the Alternating Space Hierarchy
Viliam Geffert ; Norbert Popély
Computing and Informatics, Tome 28 (2012) no. 1, p. 607-616 / Harvested from Computing and Informatics
Text on Computing and Informatics
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)).
Publié le : 2012-01-26
Classification:  Computational complexity; sublogarithmic space; alternation 
@article{cai477,
     author = {Viliam Geffert and Norbert Pop\'ely},
     title = {Refinement of the Alternating Space Hierarchy},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     pages = { 607-616},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai477}
}

Viliam Geffert; Norbert Popély. Refinement of the Alternating Space Hierarchy. Computing and Informatics, Tome 28 (2012) no. 1, pp.  607-616. http://gdmltest.u-ga.fr/item/cai477/