Copyright | (c) Masahiro Sakai 2015 |
---|---|
License | BSD-style |
Maintainer | masahiro.sakai@gmail.com |
Stability | provisional |
Portability | non-portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
Extensions |
|
- [GurvichKhachiyan1999] Vladimir Gurvich and Leonid Khachiyan, On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions, Discrete Applied Mathematics, vol. 96-97, pp. 363-373, 1999. http://www.sciencedirect.com/science/article/pii/S0166218X99000992
Synopsis
- module ToySolver.Combinatorial.HittingSet.InterestingSets
- run :: forall m prob. IsProblem prob m => prob -> Options m -> m (Set IntSet, Set IntSet)
- findPrimeImplicateOrPrimeImplicant :: IntSet -> (IntSet -> Bool) -> Set IntSet -> Set IntSet -> Maybe ImplicateOrImplicant
- generateCNFAndDNF :: IntSet -> (IntSet -> Bool) -> Set IntSet -> Set IntSet -> (Set IntSet, Set IntSet)
- minimalHittingSets :: Set IntSet -> Set IntSet
- enumMinimalHittingSets :: Set IntSet -> [IntSet]
Problem definition
Main functionality
run :: forall m prob. 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: monotone boolean functions
findPrimeImplicateOrPrimeImplicant Source #
:: 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 |
-> Maybe ImplicateOrImplicant |
Find a new prime implicant or implicate.
Let f be a monotone boolean function over set of variables S. Let ∧_{I∈C} ∨_{i∈I} x_i and ∨_{I∈D} ∧_{i∈I} x_i be the irredundant CNF representation f and DNF representation of f respectively.
Given a subset C' ⊆ C and D' ⊆ D,
returnsfindPrimeImplicateOrPrimeImplicant
S f C' D'
Just (Left I)
where I ∈ C \ C',Just (Right I)
where J ∈ D \ D', orNothing
if C'=C and D'=D.
:: 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.