Add to ORKGWe 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))
Refined Turing machine space complexity classes are defined by limiting all three of the resources s...
AbstractOne of the most important questions in the theory of computational complexity is whether non...
AbstractIn this paper we show that shuffle languages are contained in one-way-NSPACE(logn) thus in P...
The complexity measure under consideration is SPACE x REVERSALS for Turing machines that are able to...
Languages accepted by alternating auxiliary pushdown automata using simultaneously a(n) alternations...
We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(lo...
AbstractWe consider variants of alternating auxiliary stack automata and characterize their computat...
AbstractThis paper investigates infinite hierarchies on alternation-depth and alternation-size of al...
AbstractWe show that, for an arbitrary function h(n) and each recursive function ℓ(n), that are sepa...
AbstractWhether or not there is a difference of the power among alternating Turing machines with a b...
AbstractThis paper investigates some aspects of the accepting powers of deterministic, nondeterminis...
AbstractThis paper introduces a simple, natural complexity measure for space bounded two-dimensional...
AbstractIt is known that, for one-tape nondeterministic Turing machines, S(n)-space and S(n)-reversa...
We apply inductive counting to nondeterministic branching programs and prove that complementation on...
We present very sharp separation results for Turing machine sublogarithmic space complexity classes ...
Refined Turing machine space complexity classes are defined by limiting all three of the resources s...
AbstractOne of the most important questions in the theory of computational complexity is whether non...
AbstractIn this paper we show that shuffle languages are contained in one-way-NSPACE(logn) thus in P...
The complexity measure under consideration is SPACE x REVERSALS for Turing machines that are able to...
Languages accepted by alternating auxiliary pushdown automata using simultaneously a(n) alternations...
We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(lo...
AbstractWe consider variants of alternating auxiliary stack automata and characterize their computat...
AbstractThis paper investigates infinite hierarchies on alternation-depth and alternation-size of al...
AbstractWe show that, for an arbitrary function h(n) and each recursive function ℓ(n), that are sepa...
AbstractWhether or not there is a difference of the power among alternating Turing machines with a b...
AbstractThis paper investigates some aspects of the accepting powers of deterministic, nondeterminis...
AbstractThis paper introduces a simple, natural complexity measure for space bounded two-dimensional...
AbstractIt is known that, for one-tape nondeterministic Turing machines, S(n)-space and S(n)-reversa...
We apply inductive counting to nondeterministic branching programs and prove that complementation on...
We present very sharp separation results for Turing machine sublogarithmic space complexity classes ...
Refined Turing machine space complexity classes are defined by limiting all three of the resources s...
AbstractOne of the most important questions in the theory of computational complexity is whether non...
AbstractIn this paper we show that shuffle languages are contained in one-way-NSPACE(logn) thus in P...