  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(m^2n) 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 from a set to represent a given string is shown to be NP-hard.
Also, finding the smallest subset from a set to represent each string in the
original set is NP-hard. We establishes inapproximability results and
approximation algorithms for them. In addition, we prove that counting the
number of strings representable is #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 number is some power of 2. This difference
maybe help us understand the problem more profoundly.
