Computing on binary strings

Many problems in Computer Science can be abstracted to the following question: given a set of objects and rules respectively, which new objects can be produced? In the paper, we consider a succinct version of the question: given a set of binary strings and several operations like conjunction and disjunction  , which new binary strings can be generated? Although it is a fundamental problem, to the best of our knowledge, the problem hasn't been studied yet. In this paper, an O(m2n)O(m2n) algorithm is presented to determine whether a string s is representable by a set W, where n is the number of strings in W and each string has the same length m  . However, looking for the minimum subset to represent a given string is shown to be NPNP-hard. Also, finding the smallest subset to represent each string in the original set is NPNP-hard. We establish tight inapproximability results and approximation algorithms for these NPNP-hard problems. In addition, we prove that counting the number of representable strings is #P#P-complete. We then explore how the problems change when the operator negation is available. For example, if the operator negation can be used, the counting problem is as simple as some power of 2. This difference may help us to better understand the problem.