Inductive counting below logspace

DOI10.1007/3-540-58338-6_74zbMath1494.68089OpenAlexW1506210129MaRDI QIDQ5096885

Markus Holzer, Carsten Damm

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58338-6_74

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Unnamed Item
• Turing machines that take advice
• The method of forced enumeration for nondeterministic automata
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• The alternation hierarchy for sublogarithmic space is infinite
• Nondeterministic Space is Closed under Complementation
• Two Applications of Inductive Counting for Complementation Problems
• Alternation
• A hierarchy that does not collapse : alternations in low level space

This page was built for publication: Inductive counting below logspace