TY - JOUR
AU - Miguel Couceiro
AU - Stephan Foldes
PY - 2007/01/01
Y2 - 2024/03/04
TI - Functional equations, constraints, definability of function classes, and functions of Boolean variables
JF - Acta Cybernetica
JA - Acta Cybern
VL - 18
IS - 1
SE - Regular articles
DO -
UR - https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3706
AB - The paper deals with classes of functions of several variables defined on an arbitrary set A and taking values in a possibly different set B. Definability of function classes by functional equations is shown to be equivalent to definability by relational constraints, generalizing a fact established by Pippenger in the case A = B = {0,1}. Conditions for a class of functions to be definable by constraints of a particular type are given in terms of stability under certain functional compositions. This leads to a correspondence between functional equations with particular algebraic syntax and relational constraints with certain invariance properties with respect to clones of operations on a given set. When A = {0,1} and B is a commutative ring, such B-valued functions of n variables are represented by multilinear polynomials in n indeterminates in B[X1,..., Xn], Functional equations are given to describe classes of field-valued functions of a specified bounded degree. Classes of Boolean and pseudo-Boolean functions are covered as particular cases.
ER -