Implicit set manipulation: theory and practice
David Berque · 1992
Many important problems in Discrete Mathematics deal with collections of sets described with the help of common mathematical expressions like 2$\sp S$ (the power set of S). Such expressions can be difficult to manipulate manually, thus suggesting the potential usefulness of software tools that perform these manipulations. Even when $\vert S\vert$ is moderately small (say $\vert S\vert \approx$ 50), 2$\sp S$ will be large enough to prohibit it from being explicitly stored in a computer's memory. If a software tool for manipulating such sets is to be useful, it must be capable of storing implicit representations of these sets. Further, such a system must support algorithms that perform standard set operations (e.g., union, intersection) and compute standard set functions (e.g., testing membership, computing cardinality) on these implicit representations. Previous set manipulation systems have failed to balance the competing needs that arise from the demands of implicit set manipulation. For example, it is difficult to design a data structure for representing implicitly defined sets that simultaneously meets the following requirements: (1) the data structure must store a wide enough range of sets to make the system a useful tool, (2) the data structure must allow the standard set operations to be performed efficiently, and (3) the data structure must enable the standard set functions to be computed without explicitly enumerating the underlying sets. This thesis presents our work in designing data structures and algorithms that balance tradeoffs such as the ones described above. We demonstrate that, by paying attention to these tradeoffs, it is possible to achieve a balance that makes implicit set manipulation a reasonable goal. In addition to presenting our algorithms and data structures in a theoretical framework, we present the SetPlayer system which we developed as a realization of our design. We demonstrate that although some of the problems SetPlayer deals with are #P-complete, interactive solutions are often possible for problems of a moderate size. In addition, we introduce techniques by which SetPlayer can monitor the progress made toward solving a particular problem. Thus, in those cases where an interactive solution is not possible, the user may be informed at an early stage of the computation.