Modified branching programs and their computational power (Q1187665)

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.