Inductive Counting for Width-Restricted Branching Programs

As an application of the inductive counting technique to a circuit-like model, we prove that complementation on nondeterministic branching programs can be done without increasing the width excessively. A consequence of this result is that the class of languages recognized by a generalization of nonuniform finite automata to nonconstant space is closed under complement.

Authors

• Carsten Damm
• Markus Holzer

Keywords

No keywords are indexed for this paper.