Galois theory for minors of finite functions (Q1613555): Difference between revisions

The motivating example for this work is given by sets of Boolean functions closed under taking minors. The theory of minors has been used to study threshold functions and their generalizations. This paper deals with \(n\)-adic \((k,l)\)-ary functions, that is, maps \(f:B_k^n\longrightarrow B_l\), where \(B_m=\{0,1,\dots,m-1\}\). An \(m\)-adic function \(g\) is called a minor of \(f\) if there is a map \(h:\{1,\dots,n\}\longrightarrow\{1,\dots,m\}\). A Galois connection is established between sets of functions closed under taking minors and certain pairs of relations, called constraints. The closure conditions on sets of constraints are explicitly determined. The present work is an extension of a paper by \textit{O. Ekin, S. Foldes, P. L. Hammer} and \textit{L. Hellerstein} [``Equational characterizations of Boolean function classes'', Discrete Math. 211, 27-51 (2000; Zbl 0947.06008)].