Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:finite-model_finders [2008/03/13 13:13] vkuncak |
sav08:finite-model_finders [2010/02/23 12:05] vkuncak |
||
---|---|---|---|
Line 16: | Line 16: | ||
* generalize SAT algorithms to search for finite domains and not just propositional ones (SEM) | * generalize SAT algorithms to search for finite domains and not just propositional ones (SEM) | ||
* encoding into SAT (popular recently because SAT solvers are good): MACE, Paradox, KodKod (used in Alloy) | * encoding into SAT (popular recently because SAT solvers are good): MACE, Paradox, KodKod (used in Alloy) | ||
+ | |||
+ | Issues when encoding into SAT: | ||
+ | * detecting sharing to minimizing size of propositional formula | ||
+ | * symmetry breaking - larger formula with fewer instances | ||
+ | * sort inference - smaller range of variables | ||
+ | * incremental search for different sizes of the domain - reusing work in SAT solver | ||
Symmetry breaking among issues of encoding into SAT. | Symmetry breaking among issues of encoding into SAT. | ||
Line 21: | Line 27: | ||
===== References ===== | ===== References ===== | ||
+ | * [[http://www4.in.tum.de/~blanchet/nitpick.html|Nitpick]] | ||
* [[http://web.mit.edu/~emina/www/kodkod.html]] | * [[http://web.mit.edu/~emina/www/kodkod.html]] | ||
* [[http://www.cs.chalmers.se/~koen/folkung/]] | * [[http://www.cs.chalmers.se/~koen/folkung/]] | ||
* [[http://alloy.mit.edu]] | * [[http://alloy.mit.edu]] | ||