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
[Question] How to reduce syntactic size of a formula #22
Comments
Maybe related to #12 ? |
Not as far as I can see, except I'm indeed using the QMC mentionned in that post. |
LogicNG simplifies some "easy" things on the fly, e.g. We implemented some industrial applications, where simplifying the formula was part of the problem. But there we hand-crafted some algorithms based on methods of LogicNG. E.g. what you always can do is compute backbones of your formula (literals that always hold) and propagate them through your formula. We have the But in general there is not "one way" to simplify a formula for all possible applications. Often domain knowledge or additional constraints can also help to simplify a formula. Another way would be, to transform the formula to a BDD, using e.g. the FORCE heuristics. Note that this is also not possible for each formula - BDD construction is also NP-hard. But in our experience, the FORCE heuristics yields pretty good results on real-life formulas. |
if you could provide a test formula of yours (if needed, anonymized with the |
Thanks for the answer; the formulas are part of a test set for the Model Checking Contest and unfortunately there is not much domain knowledge to grab here since they are mostly random (with some patterns, (a1 & a2 | a3 & a4 | ... ) & (b1 & b2 | b3 & b4 | ...) is pretty common). Given the randomness however, there is a lot of garbage that can and is simplified away by LogicNG. |
make sure we don't just wait forever here Better not run into too high complexity, some things are COSTLY, most useful results and smaller examples from Cardinality category should be doable in 1/2 second See logic-ng/LogicNG#22
thanks for the help I found some compromises I can work with, basically with some timeouts and limits to expansion size that is accepted, and trying different forms. |
Hi,
Thanks for making your package available, it's a nice piece of software.
I'm trying to minimize some boolean formulas, with the metric that resulting syntactic tree should have as few nodes as possible.
Part of the goal on my test set is the fact some atoms in formulas disappear, as they are asserted in both forms (a OR !a => true, a AND !a =>false). This is not immediately obvious, the formulas are pretty large, so I'm trying to use your package for this.
I've tried running MCQ, but the conversion to what looks like CNF makes some of my formulas blow up in size; this is not ideal.
I'm thinking of trying MCQ (which should always be better than CNF, right ?) then DNF and choosing the smallest, iff. it is syntactically smaller than my original formula.
And wrapping the whole thing so if some step/transformation blows up, just skip it and choose from remaining candidates.
But maybe there are better ways to do this ?
Thank you
The text was updated successfully, but these errors were encountered: