Inductive counting below LOGSPACE

DOI10.1007/3-540-58338-6_74MaRDI QIDQ5096885zbMATH OpenOpenAlexFDO

Authors Carsten Damm, Markus Holzer

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

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

Recommendations

• Inductive counting for width-restricted branching programs
• Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
• Two Applications of Inductive Counting for Complementation Problems
• A variant of inductive counting
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

Cites work

• A hierarchy that does not collapse : alternations in low level space
• Alternation
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• scientific article; zbMATH DE number 512811 (Why is no real title available?)
• scientific article; zbMATH DE number 3999297 (Why is no real title available?)
• Nondeterministic Space is Closed under Complementation
• The alternation hierarchy for sublogarithmic space is infinite
• The method of forced enumeration for nondeterministic automata
• Turing machines that take advice
• Two Applications of Inductive Counting for Complementation Problems

Cited in

(5)

• Using inductive counting to simulate nondeterministic computation
• A variant of inductive counting
• Two Applications of Inductive Counting for Complementation Problems
• scientific article; zbMATH DE number 18628 (Why is no real title available?)
• Inductive counting for width-restricted branching programs

This page was built for publication: Inductive counting below LOGSPACE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096885)