Inductive counting for width-restricted branching programs

DOI10.1006/INCO.1996.0084zbMATH Open0872.68037OpenAlexW2014483498MaRDI QIDQ675225FDOQ675225

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

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

zbMATH Keywords

inductive counting technique

Mathematics Subject Classification ID

Cited In (6)

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

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)