Unification in Boolean rings, or algebras, has recently attracted considerable interest both for its theoretical merits, since it is unitary, and for its practical relevance for manipulating hardware descriptions, for example in BiJttner & Simonis (1986). The aim of this paper is to give a comprehensive survey over the techniques and results in the field as far as it has evolved to date. However most of the results have been around for a long time; some of them going back to Boole himself (Bode, 1847). A very good source for ranch of the mathematics underlying unificat;ion in Boolean rings is Rudeanu (1974). The most important result is that Boolean unification is unitary, that is either an equation has no solution or there is a single most general unifier (in the sequeh mgu). We present two different unification algorithms, one due to Boole and the other to LSwenheim. The paper is structured as follows. In section we present only the very basic facts about Boolean rings, just enough to explain the unification algorithms presented in section . However the algorithms presented in section axe parameterized on procedures for simplifying Boolean terms and finding solutions to Boolean equations. In order to solve these two problems section invokes a bit of structure theory of Boolean algebras. This enables us in sections and to derive solutions to the two remaining subproblems of simplification and of finding particular solutions. Section provides a rough complexity analysis of the presented algorithms. It turns out that both unification methods have the same complexity which is exponential in the number of constants and variables. Section explains how the results obtained in terms of a particular set of operators (the ring operations + and *) may be transferred to a different set of operators. So far we only dealt with terms over the ring operations a.nd arbitrary constants. In section we extend unification to inchde free terms with variables as well. The resulting set of formulae are basically those of the unquantified predicate calcuhs. It is shown that unification in this theory is finitaxy. This extension is used in section to obtain semi-decision procedure for the first erder predicate calculus. *This research was carried out at t, he University of Manchester, ~The author acknowledges partial support of the United Kingdom SERC under graxxt GR8:tT18D. 275
REF studies unification in Boolean rings.
Boolean unification - The story so far
J. Symb. Comput.
J. Symb. Comput.
Mathematics Computer Science