dc.contributor.author Foldes, Stephan dc.contributor.author Couceiro, Miguel HAL ID: 1498 dc.date.accessioned 2012-09-25T15:25:41Z dc.date.available 2012-09-25T15:25:41Z dc.date.issued 2007 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/10178 dc.language.iso en en dc.subject pseudo-Boolean functions en dc.subject Boolean functions en dc.subject field-valued functions of Boolean variables en dc.subject linear equations en dc.subject multilinear polynomial representations en dc.subject ring-valued functions en dc.subject function class definability en dc.subject relational constraints en dc.subject functional equa- tion en dc.subject stability en dc.subject class composition en dc.subject Function classes en dc.subject.ddc 512 en dc.title Functional equations, constraints, definability of function classes, and functions of Boolean variables en dc.type Article accepté pour publication ou publié dc.contributor.editoruniversityother TUT; dc.description.abstracten 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}. en 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. dc.relation.isversionofjnlname Acta Cybernetica dc.relation.isversionofjnlvol 18 en dc.relation.isversionofjnlissue 1 en dc.relation.isversionofjnldate 2007 dc.relation.isversionofjnlpages 61-75 en dc.relation.isversionofjnlpublisher Acta Cybernetica Szeged en dc.subject.ddclabel Algèbre en dc.relation.forthcoming non en dc.relation.forthcomingprint non en
﻿