<p>Let $W = \{s_1, s_2, \ldots, s_n\}$ be a set of $m$-length binary strings and let $\land$ and $\lor$ be the binary operators of bitwise AND and OR. A <em>bitwise formula</em> $\phi$ is composed of operands in $A \subseteq W$, operators in $ \{(,),\land, \lor\}$, and computes a $m$-length binary string $x = \phi$. Then we say that $x$ can be expressed by $W$.</p>

<p>We say a set $W$ is <em>expressive complete</em> if for any $x \in W$, $x$ can be expressed by a bitwise formula using operands in $W \setminus \{x\}$.</p>

<blockquote>
  <p><strong>Question:</strong> Given $W$, determine the <strong>minimum</strong> number $n$ of $m$-length binary strings that need to be added to $W$ to make it expressive complete.</p>
</blockquote>

<p><strong>Example 1:</strong> Let $m = 2$ and $W = \{01, 10\}$. Then then both 00 and 11 need to be added to $W$ to make it expressive complete. Thus, $n = 2$.</p>

<p><strong>Example 2:</strong> Let $m = 3$ and $W = \{001, 010, 100, 011, 110, 101\}$. $W$ is already expressive complete, so $n = 0$.</p>

<p><strong>A Trivial Upperbound:</strong> $2m$ is an upperbound, because for vector space $\{0,1\}^m$, $\{ 0...01, 0...010,..., 10...0\}$ is a base and $\{1...10, 1...101,...,01...1\}$ is also a base. After adding these two bases to $W$, $W$ is certainly expressive complete.</p>

<p><strong>Related result (might be helpful for the question) proved:</strong>
$x$ could be expressed from $A\subseteq W$ if and only if $\bigwedge_{i \in \mathsf{Zero}(x)} {t_i} = x$. Where $\mathsf{Zero}(x)$ is the set of 0 valued indicies of $x$. And $t_i$ is the $\lor$ opreated on all the binary strings in $A$ whose $i^{th}$ bit is 0.</p>

<p>Thank you very much for your comments and answers. :)</p>

CC BY-SA 3.0
2011-08-24T08:56:18.833Z
side note: I think it is usually better to first have some idea about why some problem is interesting and worth spending time and then start proving results about it, not vice versa. You are essentially asking others to provide motivation for your work, and I found that quite unusual.
Kaveh
CC BY-SA 3.0
2011-08-24T11:43:13.803Z
What is the point of claiming that your problems are “natural” or “[interesting](http://cstheory.stackexchange.com/questions/7878/an-interesting-variant-of-maximum-matching-problem)” without backing up your claim?  I am not saying they aren’t, but I think that you can be a little modest about interestingness of your problems, especially if your questions do not contain evidences why the problems are natural/interesting.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-24T12:37:29.223Z
Can you give an example of an expressive complete set $W$ that is not trivial (i.e. does not contain all the strings of length $m$)?
Tyson Williams
CC BY-SA 3.0
2011-08-24T12:52:00.867Z
@Tyson: $W=\{001, 010, 100, 011, 110, 101\}$ is one.
Peng Zhang
CC BY-SA 3.0
2011-08-24T14:05:59.313Z
I just extensively edited your question (but it won't be visible until peer reviewed). Please check that I did not introduce any errors.
Tyson Williams
CC BY-SA 3.0
2011-08-25T07:44:33.243Z
@Peng: Is there an actual question here? Did you just pose a question and then answer it yourself?
mhum
CC BY-SA 3.0
2011-08-25T08:08:05.640Z
@mhum:Yes, there is. The result proved is a related result, not the answer for the Qestion. Thank you for you care.
Peng Zhang
CC BY-SA 3.0
2011-08-25T08:23:31.063Z
finding a base for a finite lattice feels related.
Kaveh
CC BY-SA 3.0
2011-08-25T13:42:46.970Z
@Kaveh: If we take the binary string as vector, then add two different basis of $\{0,1\}^m$ is enough. But what's the minimum sized additional vector set?
Peng Zhang
CC BY-SA 3.0
2011-08-25T14:54:20.567Z
@Peng: Ah. I see. I misread.
mhum
CC BY-SA 3.0
2011-08-27T13:17:18.730Z
For your new trivial upperbound, you should say that the two bases are disjoint.
Tyson Williams
CC BY-SA 3.0
2011-08-27T13:28:02.757Z
@Tyson: Yes. The two bases actually are corresponding negation of each other.
Peng Zhang
<cc.complexity-theory><ds.algorithms><co.combinatorics>
Problem with bitwise AND/OR on binary strings
Peng Zhang
# Problem with bitwise AND/OR on binary strings

(Asked by: username_0 on 2011-08-24)

Let $W = \{s\_1, s\_2, \ldots, s\_n\}$ be a set of $m$-length binary strings and let $\land$ and $\lor$ be the binary operators of bitwise AND and OR. A *bitwise formula* $\phi$ is composed of operands in $A \subseteq W$, operators in $ \{(,),\land, \lor\}$, and computes a $m$-length binary string $x = \phi$. Then we say that $x$ can be expressed by $W$.

We say a set $W$ is *expressive complete* if for any $x \in W$, $x$ can be expressed by a bitwise formula using operands in $W \setminus \{x\}$.

> **Question:** Given $W$, determine the **minimum** number $n$ of $m$-length binary strings that need to be added to $W$ to make it expressive complete.

**Example 1:** Let $m = 2$ and $W = \{01, 10\}$. Then then both 00 and 11 need to be added to $W$ to make it expressive complete. Thus, $n = 2$.

**Example 2:** Let $m = 3$ and $W = \{001, 010, 100, 011, 110, 101\}$. $W$ is already expressive complete, so $n = 0$.

**A Trivial Upperbound:** $2m$ is an upperbound, because for vector space $\{0,1\}^m$, $\{ 0...01, 0...010,..., 10...0\}$ is a base and $\{1...10, 1...101,...,01...1\}$ is also a base. After adding these two bases to $W$, $W$ is certainly expressive complete.

**Related result (might be helpful for the question) proved:**
$x$ could be expressed from $A\subseteq W$ if and only if $\bigwedge\_{i \in \mathsf{Zero}(x)} {t\_i} = x$. Where $\mathsf{Zero}(x)$ is the set of 0 valued indicies of $x$. And $t\_i$ is the $\lor$ opreated on all the binary strings in $A$ whose $i^{th}$ bit is 0.

Thank you very much for your comments and answers. :)

**Tags:** cc.complexity-theory, ds.algorithms, co.combinatorics

> **Comments:**
> **username_1**: side note: I think it is usually better to first have some idea about why some problem is interesting and worth spending time and then start proving results about it, not vice versa. You are essentially asking others to provide motivation for your work, and I found that quite unusual.  
> **username_2**: What is the point of claiming that your problems are “natural” or “[interesting](http://cstheory.stackexchange.com/questions/7878/an-interesting-variant-of-maximum-matching-problem)” without backing up your claim?  I am not saying they aren’t, but I think that you can be a little modest about interestingness of your problems, especially if your questions do not contain evidences why the problems are natural/interesting.  
> **username_3**: Can you give an example of an expressive complete set $W$ that is not trivial (i.e. does not contain all the strings of length $m$)?  
> **username_0**: @Tyson: $W=\{001, 010, 100, 011, 110, 101\}$ is one.  
> **username_3**: I just extensively edited your question (but it won't be visible until peer reviewed). Please check that I did not introduce any errors.  
> **username_4**: @Peng: Is there an actual question here? Did you just pose a question and then answer it yourself?  
> **username_0**: @username_4:Yes, there is. The result proved is a related result, not the answer for the Qestion. Thank you for you care.  
> **username_1**: finding a base for a finite lattice feels related.  
> **username_0**: @username_1: If we take the binary string as vector, then add two different basis of $\{0,1\}^m$ is enough. But what's the minimum sized additional vector set?  
> **username_4**: @Peng: Ah. I see. I misread.  
> **username_3**: For your new trivial upperbound, you should say that the two bases are disjoint.  
> **username_0**: @Tyson: Yes. The two bases actually are corresponding negation of each other.  

---

## 0 answers

