ToySolver.Combinatorial.HittingSet.GurvichKhachiyan1999

References:

• [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

Problem definition

module ToySolver.Combinatorial.HittingSet.InterestingSets

Main functionality

run :: forall m prob. IsProblem prob m => prob -> Options m -> m (Set IntSet, Set IntSet)

Given a problem and an option, it computes maximal interesting sets and minimal uninteresting sets.

Applications: monotone boolean functions

findPrimeImplicateOrPrimeImplicant

Arguments

:: IntSet

Set of variables V

-> (IntSet -> Bool)

A monotone boolean function f from {0,1}^|V| ≅ P(V) to Bool

-> 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, findPrimeImplicateOrPrimeImplicant S f C' D' returns

• Just (Left I) where I ∈ C \ C',
• Just (Right I) where J ∈ D \ D', or
• Nothing if C'=C and D'=D.

generateCNFAndDNF

Arguments

:: IntSet

Set of variables V

-> (IntSet -> Bool)

A monotone boolean function f from {0,1}^|V| ≅ P(V) to Bool

-> 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.

Applicaitons: minimal hitting sets

minimalHittingSets :: Set IntSet -> Set IntSet

enumMinimalHittingSets :: Set IntSet -> [IntSet]