Branching programs, BPs, (or, synonymously, binary decision diagrams, BDDs) are an important way, that became very popular in the previous decade, to represent Boolean functions. Their attractiveness stems from two facts: From a theoretical point of view, the study of branching programs contributes to the broader study of the complexity of Boolean functions, a field of immense importance in theoretical computer science and discrete mathematics. Second, branching programs are relevant for applied computer science since a number of important operations on Boolean functions can be performed efficiently when these are given as branching programs. These operations include for instance evaluation, synthesis, satisfiability test, equivalence test, or minimization. Thus, branching programs serve as a good data structure for Boolean functions.
Both these motivations for the study of BPs are followed in the book. After a one chapter introduction to the field, the first part of the book, consisting of eleven chapters, presents theoretical results. Different chapters treat different types of branching programs, such as (most prominently) OBDDs (ordered BDDs), read-once BDDs, randomized BDDs, and some more. The presented topics include efficient algorithms to manipulate BPs, upper bounds for the BDD-size of important problems (e.g., addition, multiplication, division, storage access) as well as lower bounds. The first part ends with a summary of theoretical results, containing a table of the time complexity of algorithms for operations on BDDs, a list of upper and lower bounds of a number of functions w.r.t. size for different types of BDDs, and two inclusion diagrams among complexity classes defined by OBDDs and free BDDs.
The second part of the book, consisting of three chapters, turns to applications of BDDs, including circuit verification, model checking, logic minimization and synthesis, etc.
Though certainly the book primarily serves as a monograph for researchers, the author also outlines how a theoretically inclined and how a practically oriented course might be taught based on the contents of the book. Also for this purpose, every chapter ends with a number of exercises, graded “E” (easy), “M” (middle), or “D” (difficult). Also helpful will be the URL of a page on the web containing solutions of exercises and a continuously updated list of errors and typos.
There are only very few books devoted to the topic of branching programs, and this alone would make the book a welcome contribution. But far more than that: The book has a remarkably broad scope and while presenting all the wonderful complexity results for branching programs that appeared in the past few years (the vast majority of papers in the bibliography were published very recently in the second half of the nineties of the previous century), the author does not disregard applications. The book will be very welcome by computer scientists and mathematicians who look for a comprehensive presentation of the theory of branching programs and want to get a quick overview of the possible applications.