Inductive counting for width-restricted branching programs

DOI10.1006/INCO.1996.0084MaRDI QIDQ675225zbMATH OpenOpenAlexFDO

Authors Carsten Damm, Markus Holzer

Publication date 6 March 1997

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/a8a6317ce33416f8eb527977b57089a88a1a951d

zbMATH Keywords

inductive counting technique

Mathematics Subject Classification ID

Recommendations

• Inductive counting below LOGSPACE
• Two Applications of Inductive Counting for Complementation Problems
• scientific article; zbMATH DE number 4047115
• The power of nondeterminism in polynomial-size bounded-width branching programs
• Using inductive counting to simulate nondeterministic computation

Cited in

(7)

• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Inductive counting below LOGSPACE
• A variant of inductive counting
• Bridging across the \(\log(n)\) space frontier
• Alternating space is closed under complement and other simulations for sublogarithmic space
• Multi-head finite automata: Data-independent versus data-dependent computations
• Two Applications of Inductive Counting for Complementation Problems

This page was built for publication: Inductive counting for width-restricted branching programs

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