| Summary: | In this paper we address the problem of generating all elements obtained by
the saturation of an initial set by some operations. More precisely, we prove
that we can generate the closure of a boolean relation (a set of boolean
vectors) by polymorphisms with a polynomial delay. Therefore we can compute
with polynomial delay the closure of a family of sets by any set of "set
operations": union, intersection, symmetric difference, subsets, supersets
$\dots$). To do so, we study the $Membership_{\mathcal{F}}$ problem: for a set
of operations $\mathcal{F}$, decide whether an element belongs to the closure
by $\mathcal{F}$ of a family of elements. In the boolean case, we prove that
$Membership_{\mathcal{F}}$ is in P for any set of boolean operations
$\mathcal{F}$. When the input vectors are over a domain larger than two
elements, we prove that the generic enumeration method fails, since
$Membership_{\mathcal{F}}$ is NP-hard for some $\mathcal{F}$. We also study the
problem of generating minimal or maximal elements of closures and prove that
some of them are related to well known enumeration problems such as the
enumeration of the circuits of a matroid or the enumeration of maximal
independent sets of a hypergraph. This article improves on previous works of
the same authors.
|
|---|