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. :)

  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Aug 24, 2011 at 8:56
  • 3
    $\begingroup$ What is the point of claiming that your problems are “natural” or “interesting” 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. $\endgroup$ Aug 24, 2011 at 11:43
  • $\begingroup$ 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$)? $\endgroup$ Aug 24, 2011 at 12:37
  • $\begingroup$ @Tyson: $W=\{001, 010, 100, 011, 110, 101\}$ is one. $\endgroup$
    – Peng Zhang
    Aug 24, 2011 at 12:52
  • $\begingroup$ I just extensively edited your question (but it won't be visible until peer reviewed). Please check that I did not introduce any errors. $\endgroup$ Aug 24, 2011 at 14:05


Your Answer

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