Functional equations, constraints, definability of function classes, and functions of Boolean variables

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...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Couceiro Miguel
Foldes Stephan
Testületi szerző: Kalmár Workshop on Logic in Computer Science (2003) (Szeged)
Dokumentumtípus: Cikk
Megjelent: 2007
Sorozat:Acta cybernetica 18 No. 1
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12804
Leíró adatok
Tartalmi kivonat: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.
Terjedelem/Fizikai jellemzők:61-75
ISSN:0324-721X