Hacker News Reader

Since (B|Z)DDs are basically just fancy DAGs, I wonder what the relationship between them and other automata is like? Like can some of these techniques be applied with regexps to make something truly monstrous?

View on HN

Generalize BDDs to multiway decision diagrams: instead of binary trees on 0 and 1, make n-ary trees on a bigger alphabet. (You probably want to represent the nodes sparsely, not |alphabet| pointers in every node.)

This can directly represent a regex with | operators but not Kleene star. The DD canonicalization automatically makes this structure share suffixes, but not prefixes.

Reduced Ordered BDDs coincide with the minimal DFAs that accept the language of bit vectors encoding the boolean assignments that satisfy the modeled predicate. That is, this holds if the BDD has not had the "skip test if both outcomes less to the same sub-bdd" optimization applied, which anyway only reduces its size by a constant factor.

Reply on news.ycombinator.com