<p>This problem is basically equivalent to the <strong>minimum AND-circuit problem</strong>.</p>
<p>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.</p>
<p><em>Arpe, Jan; Manthey, Bodo</em>, <a href="https://doi.org/10.1007/s00453-007-9039-0" rel="nofollow noreferrer"><strong>Approximability of minimum AND-circuits</strong></a>, Algorithmica 53, No. 3, 337-357 (2009). <a href="https://zbmath.org/?q=an:1172.68061" rel="nofollow noreferrer">ZBL1172.68061</a>.</p>

CC BY-SA 4.0
2024-04-13T04:20:04.123Z
2024-04-13T04:20:04.123Z
Chao Xu
<p>Let <span class="math-container">$\mathcal{S}$</span> be a collection of sets. A set straight-line program that enumerates <span class="math-container">$\mathcal{S}$</span> is a sequence of sets <span class="math-container">$B_1,\ldots,B_m$</span>, such that</p>
<ul>
<li><span class="math-container">$\mathcal{S}\subseteq \{B_1,\ldots,B_m\}$</span>.</li>
<li>For each <span class="math-container">$i$</span>, either <span class="math-container">$|B_i|=1$</span> or <span class="math-container">$B_i = B_j\cup B_k$</span> for some <span class="math-container">$j,k&lt;i$</span>.</li>
</ul>
<p>Have this kind of problem been studied before?</p>

CC BY-SA 4.0
2024-04-11T14:41:21.557Z
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 https://en.wikipedia.org/wiki/Circuits_over_sets_of_natural_numbers and refs therein.
Joshua Grochow
CC BY-SA 4.0
2024-04-12T14:43:43.360Z
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.
holf
<reference-request>
Straight-line program for sets
Chao Xu
# Straight-line program for sets

(Asked by: username_0 on 2024-04-11)

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.

Have this kind of problem been studied before?

**Tags:** reference-request
> **Comments:**
> **username_1**: 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 https://en.wikipedia.org/wiki/Circuits_over_sets_of_natural_numbers and refs therein.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_0 on 2024-04-13. Score: 3 | Accepted answer

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**](https://doi.org/10.1007/s00453-007-9039-0), Algorithmica 53, No. 3, 337-357 (2009). [ZBL1172.68061](https://zbmath.org/?q=an:1172.68061).


---

