[fcholf]

Interesting to see it posted on HN. My favourite book on the subject is Branching Programs and Binary Decision Diagrams by Ingo Wegener: https://doi.org/10.1137/1.9780898719789.

There have been recent exciting developments of the same underlying idea for more complicated data structures (consisting in syntactic restrictions of Boolean circuits) with applications to other domains in computer science. This is known as "knowledge compilation" where the original goal is to transform a knowledge base offline to represent it to a more tractable data structure efficiently supporting "online" queries such as model counting and conditioning.

See for example some of the knowledge compilers listed here http://beyondnp.org/pages/solvers/knowledge-compilers/ for Boolean functions, applications to databases with so called factorized databases https://fdbresearch.github.io/index.html.

[dragontamer]

The main issue with that book is that it talks about BDDs in general, as opposed to the most common ROBDD that people are probably interested in.

Its a lot of 'spinning up' to start from branching programs and working your way to ROBDDs. In many ways, ROBDDs are easier than a lot of the stuff discussed earlier in the book.

So the layout probably should be reworked. But otherwise, the info is all there, and its good that the book hits "rock bottom" so to speak, with regards to theory.

[sitkack]

What do you both think of "The Calculus of Computation" by Bradley and Manna?

https://link.springer.com/book/10.1007/978-3-540-74113-8

Slides for the book are here, https://web.stanford.edu/class/cs156/slides/Technion/