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

Utilise (counter-)model counts for stable models #37

Closed
ellmau opened this issue Mar 21, 2022 · 0 comments · Fixed by #38
Closed

Utilise (counter-)model counts for stable models #37

ellmau opened this issue Mar 21, 2022 · 0 comments · Fixed by #38
Labels
enhancement New feature or request library This issue or pull request is related to the library

Comments

@ellmau
Copy link
Owner

ellmau commented Mar 21, 2022

Is your feature request related to a problem? Please describe.
The currently implemented naive approach to lazily evaluated and filtered iterators over all possible two-valued interpretations is not smart and performant enough.

Describe the solution you'd like
Using the counts of (counter-)models might allow one to reduce the search space, by following these steps:

  • choose the smallest count of still undecided statements
  • follow the paths to the count-defined outcome (i.e. model vs counter-model)
    • Filter impossible interpretations on the fly (e.g. model-path for the statement is followed implies that only hi-child nodes of the said statement need to be followed)
  • restrict the other acceptance conditions according to partial interpretation based on the path
  • repeat till all statements are set
  • check for stability
  • when all paths are explored, the statement-variable of the bdd can be set to the inverse truth-value without further checking.

Describe alternatives you've considered

  • A limit, where the approach is substituted by a brute-force approach
  • A similar approach with facet-counts
@ellmau ellmau added enhancement New feature or request library This issue or pull request is related to the library labels Mar 21, 2022
@ellmau ellmau added this to the Release on crates.io milestone Mar 21, 2022
@ellmau ellmau added this to ADF-OBDD Mar 21, 2022
@ellmau ellmau moved this to Todo in ADF-OBDD Mar 21, 2022
@ellmau ellmau linked a pull request Mar 22, 2022 that will close this issue
18 tasks
Repository owner moved this from Todo to Done in ADF-OBDD Mar 23, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request library This issue or pull request is related to the library
Projects
Status: Done
Development

Successfully merging a pull request may close this issue.

1 participant