Technical Reports

The ICICS/CS Reading Room

UBC CS TR-98-08 Summary

Galois Theory for Minors of Finite Functions, May 28, 1998 Nicholas Pippenger, i+15 pages

Galois Theory for Minors of Finite Functions Nicholas Pippenger A Boolean function f is a minor of a Boolean function g if f is obtained from g by substituting an argument of f, the complement of an argument of f, or a Boolean constant for each argument of g. The theory of minors has been used to study threshold functions (also known as linearly separable functions) and their generalization to functions of bounded order (where the degree of the separating polynomial is bounded, but may be greater than one). We construct a Galois theory for sets of Boolean functions closed under taking minors, as well as for a number of generalizations of this situation. In this Galois theory we take as the dual objects certain pairs of relations that we call ``constraints'', and we explicitly determine the closure conditions on sets of constraints.

If you have any questions or comments regarding this page please send mail to