Improve Bdd export to BooleanExpression
Opened this issue · 0 comments
daemontus commented
Currently, export to BooleanExpression
from Bdd
is a trivial graph traversal algorithm. There is a lot of extra techniques that can improve this algorithm:
- If we know all valid paths have
x
set to true, we can start the formula withx & ...
and later skipx
completely (this can be also done for each smallerBdd
in each expansion step). Technically, we are looking for a variable ordering that minimises the number of nodes in this specificBdd
. - We can try to find implication/equivalence pairs. That is, if
a <=> b
on all paths, we can put this as a condition at the beginning and then skipb
completely.