4
$\begingroup$

Let $\mathcal{S}$ be a collection of sets. A set straight-line program that enumerates $\mathcal{S}$ is a sequence of sets $B_1,\ldots,B_m$, such that

  • $\mathcal{S}\subseteq \{B_1,\ldots,B_m\}$.
  • For each $i$, either $|B_i|=1$ or $B_i = B_j\cup B_k$ for some $j,k<i$.

Have this kind of problem been studied before?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I haven't seen this exactly before, but people have studied circuits over sets of natural numbers, where the operations are $\cap,\cup,+,\times$ and complement, and each gate computes a set of natural numbers. Seems pretty related. See en.wikipedia.org/wiki/Circuits_over_sets_of_natural_numbers and refs therein. $\endgroup$
    – Joshua Grochow
    Commented Apr 11 at 14:41
  • 1
    $\begingroup$ ZDD can be seen as a restricted form of what you want to do (without unions and with an underlying order the elements should go in); OBDD too but the semantics is a bit farther from what you ask. With union, that would give non deterministic OBDD; I do not know whether non det ZDD have been introduced in the literature but that would not be too hard to define (just add $\vee$-gates corresponding to unions). That would give you interesting properties: you can compute size of the set computed by a ZDD, or approximate it with an FPRAS in the non-deterministic case, uniformly sample elements etc. $\endgroup$
    – holf
    Commented Apr 12 at 14:43

1 Answer 1

Reset to default
3
$\begingroup$

This problem is basically equivalent to the minimum AND-circuit problem.

They ask for a minimum circuit that only use AND gates, and it tries to compute a set of monomials. A monomial is computed by the circuit if one of the output of some gate is such monomial.

Arpe, Jan; Manthey, Bodo, Approximability of minimum AND-circuits, Algorithmica 53, No. 3, 337-357 (2009). ZBL1172.68061.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.