Galois Theory for Minors of Finite Functions
Document Type
Article
Department
Mathematics (HMC)
Publication Date
2002
Abstract
The motivating example for our work is given by sets of Boolean functions closed under taking minors. 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.
Rights Information
© 2002 Elsevier Ltd.
Terms of Use & License Information
DOI
10.1016/S0012-365X(01)00297-7
Recommended Citation
Nicholas Pippenger, Galois theory for minors of finite functions, Discrete Mathematics, Volume 254, Issues 1–3, 10 June 2002, Pages 405-419, ISSN 0012-365X, 10.1016/S0012-365X(01)00297-7. (http://www.sciencedirect.com/science/article/pii/S0012365X01002977)
