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 equ...
详细信息
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-valuedfunctions of n variables are represented by multilinear polynomials in n indeterminates in B[X-1,...,X-n]. Functional equations are given to describe classes of field-valuedfunctions of a specified bounded degree. Classes of boolean and pseudo-booleanfunctions are covered as particular cases.
暂无评论