A variant of inductive counting
From MaRDI portal
Publication:1566745
DOI10.1016/S0304-3975(99)00338-2zbMath0939.68050OpenAlexW2044713592MaRDI QIDQ1566745
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00338-2
Cites Work
- Inductive counting for width-restricted branching programs
- The method of forced enumeration for nondeterministic automata
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- Using inductive counting to simulate nondeterministic computation
- Bridging across the \(\log(n)\) space frontier
- The alternation hierarchy for sublogarithmic space is infinite
- Turing machines with sublogarithmic space
- Relationships between nondeterministic and deterministic tape complexities
- Strong optimal lower bounds for Turing machines that accept nonregular languages
- Nondeterministic Space is Closed under Complementation
- Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
- A hierarchy that does not collapse : alternations in low level space
- The Sublogarithmic Alternating Space World
