- View PDF version of TR-98-08 (147109 bytes)
- View PostScript version of TR-98-08
- Save PostScript version of TR-98-08
- Save gzipped PostScript version of TR-98-08 (46072 bytes)

- 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 help@cs.ubc.ca.