Copyright | (c) Masahiro Sakai 2016 |
---|---|
License | BSD-style |
Maintainer | masahiro.sakai@gmail.com |
Stability | provisional |
Portability | non-portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
Extensions |
|
"Dualize and Advance" algorithm for enumerating maximal interesting sets and minimal non-interesting sets.
- [GMKT1997] D. Gunopulos, H. Mannila, R. Khardon, and H. Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), in Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ser. PODS '97. 1997, pp. 209-216. http://almaden.ibm.com/cs/projects/iis/hdb/Publications/papers/pods97_trans.pdf
- [BaileyStuckey2015] J. Bailey and P. Stuckey, Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization," in Practical Aspects of Declarative Languages, pp. 174-186, 2005. http://ww2.cs.mu.oz.au/~pjs/papers/padl05.pdf
Problem definition
Main functionality
run :: forall prob m. IsProblem prob m => prob -> Options m -> m (Set IntSet, Set IntSet) Source #
Given a problem and an option, it computes maximal interesting sets and minimal uninteresting sets.
Applications: minimal hitting sets
:: IntSet | Set of variables V |
-> (IntSet -> Bool) | A monotone boolean function f from {0,1}^|V| ≅ P(V) to |
-> Set IntSet | Subset C' of prime implicates C of f |
-> Set IntSet | Subset D' of prime implicants D of f |
-> (Set IntSet, Set IntSet) |
Compute the irredundant CNF representation and DNF representation.
Let f be a monotone boolean function over set of variables S. This function returns C and D where ∧_{I∈C} ∨_{i∈I} x_i and ∨_{I∈D} ∧_{i∈I} x_i are the irredundant CNF representation f and DNF representation of f respectively.