Show simple item record

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

dc.contributor.authorFoldes, Stephan
dc.contributor.authorCouceiro, Miguel
HAL ID: 1498
dc.date.accessioned2012-09-25T15:25:41Z
dc.date.available2012-09-25T15:25:41Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/10178
dc.language.isoenen
dc.subjectpseudo-Boolean functionsen
dc.subjectBoolean functionsen
dc.subjectfield-valued functions of Boolean variablesen
dc.subjectlinear equationsen
dc.subjectmultilinear polynomial representationsen
dc.subjectring-valued functionsen
dc.subjectfunction class definabilityen
dc.subjectrelational constraintsen
dc.subjectfunctional equa- tionen
dc.subjectstabilityen
dc.subjectclass compositionen
dc.subjectFunction classesen
dc.subject.ddc512en
dc.titleFunctional equations, constraints, definability of function classes, and functions of Boolean variablesen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherTUT;
dc.description.abstractenThe 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.en
dc.relation.isversionofjnlnameActa Cybernetica
dc.relation.isversionofjnlvol18en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2007
dc.relation.isversionofjnlpages61-75en
dc.relation.isversionofjnlpublisherActa Cybernetica Szegeden
dc.subject.ddclabelAlgèbreen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


Files in this item

Thumbnail
Name:
Couceiro_2007_ActaCybernetica.pdf
Size:
184.3Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record