Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve Bdd export to BooleanExpression #3

Open
daemontus opened this issue Feb 7, 2020 · 0 comments
Open

Improve Bdd export to BooleanExpression #3

daemontus opened this issue Feb 7, 2020 · 0 comments
Labels
enhancement New feature or request
Milestone

Comments

@daemontus
Copy link
Member

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 with x & ... and later skip x completely (this can be also done for each smaller Bdd in each expansion step). Technically, we are looking for a variable ordering that minimises the number of nodes in this specific Bdd.
  • 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 skip b completely.
@daemontus daemontus added the enhancement New feature or request label Feb 7, 2020
@daemontus daemontus changed the title Improve Bdd export to boolean expression Improve Bdd export to BooleanExpression Feb 7, 2020
@daemontus daemontus added this to the 1.0.0 milestone Aug 30, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant