Modified branching programs and their computational power. (English) Zbl 0669.68042

Lecture Notes in Computer Science, 370. Berlin etc.: Springer-Verlag. VI, 132 p. DM 28.00 (1989).
This book gives a concise treatment of results concerning the nonuniform computation model of branching programs. Branching programs generalize the concept of decision trees, but are less powerful than Boolean circuits. The relationships to the uniform Turing machine model are explored and exact characterizations, as well as lower and upper bounds, are presented. Among others, the modifications studied in this book consist of read-once-only, nondeterministic, bounded-width, and \(\omega\)- branching programs, and combinations thereof.
Reviewer: U.Schöning


68Q45 Formal languages and automata
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68Q25 Analysis of algorithms and problem complexity