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

Meinel, Christoph

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

MSC:

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

Keywords:

branching program; logarithmic space complexity; nonuniform computation