1
$\begingroup$

Given a set of $n$ binary strings of length $m$, how many binary strings at least should we add to the set to make sure that the binary "AND" and "OR" operators are closed on the set? The output of the problem is the number of binary strings needed to add.

For example, given the set {001, 010, 110}, we should at least add {000, 011, 111} to the set to make both "AND" and "OR" operators closed. So the output is 3.

Is there any good algorithm or idea related to the problem? Thanks a lot.

In addition, is there a good way to test whether a given binary string can be got by "AND" and "OR" from a given set of binary strings?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

This might not answer your question, but gives some idea of what to expect. There is a set of $2m$ strings of length $2^m$ whose closure under AND and OR is the set of all binary string of length $2^m$ of size $2^{2^m}$. This can be seen as follows:

We start with $m=1$. Consider the two strings 01 and 10.
These generate (by taking the closure under AND and OR) a set of four strings, namely all binary strings of length $2$.
Given a set $\{a_1,\dots,a_{2m}\}$ of strings of length $2^m$ of size $2m$ generating all binary strings of length $2^m$. For $1\leq i\leq 2m$ let $b_i=a_ia_i$.
Let $b_{2m+1}$ be $2^m$ 0's followed by $2^m$ 1's and let $b_{2m+2}$ be $2^m$ 1's followed by $2^m$ 0's. It is easily checked that $\{b_1,\dots,b_{2m+2}\}$ generates all binary strings of lenth $2^{2^m}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Don't you get already everything by just applying OR to the strings with exactly one 1-entry? $\endgroup$
    – Thomas Kalinowski
    Commented May 21, 2011 at 5:43
  • $\begingroup$ That is indeed true, except for the string that is constantly zero. What I wanted to say was something else. See the edited answer. $\endgroup$
    – Stefan Geschke
    Commented May 21, 2011 at 19:52
2
$\begingroup$

I think, the closure problem decomposes: You can first apply AND to pairs of strings until you get nothing new, and then you start applying OR until nothing new is generated.

And for the testing problem the following should work: for each 1-entry of the given string, apply AND to the collection of all strings from your set, that have a 1 at this position. It is necessary and sufficient that the set of 1-entries of the result is always contained in the set of 1-entries of the tested string.

For me it's easier to think of the strings as subsets of $\{1,2,\ldots,m\}$. Then AND is intersection, OR becomes union and the above method yields the collection of all sets that can be written as a union of intersections of the original sets, i.e. in the form $$\bigcup_{i=1}^t\bigcap_{j=1}^{r_i}A_{ij}\qquad\text{with }A_{ij}\in\mathcal A\text{ for all }(i,j)$$ where $\mathcal A$ is the collection of sets from which we start. Clearly the result is union-closed. To see that it's also intersection-closed, we note that $$\left(\bigcup_{i=1}^t\bigcap_{j=1}^{r_i}A_{ij}\right)\cap\left(\bigcup_{k=1}^{t'}\bigcap_{l=1}^{s_k}B_{kl}\right)=\bigcup_{i=1}^t\bigcup_{k=1}^{t'}\bigcap_{j=1}^{r_i}\bigcap_{l=1}^{s_k}A_{ij}\cap B_{kl}.$$

And the testing works as follows. Let $X$ be the set to be tested, and assume that every element of $X$ appears in at least one $A\in\mathcal A$ (otherwise $X$ is obviously not representable). We form the set $$Y=\bigcup_{x\in X}\bigcap_{A\in\mathcal A\,:\,x\in A}A.$$ Then $Y$ is the smallest representable set containing $X$, and $X$ is representable iff $X=Y$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Why are these statements true? Is there any reference? $\endgroup$
    – Igor Rivin
    Commented May 22, 2011 at 3:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .