• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail

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

Foldes, Stephan; Couceiro, Miguel (2007), Functional equations, constraints, definability of function classes, and functions of Boolean variables, Acta Cybernetica, 18, 1, p. 61-75

Voir/Ouvrir
Couceiro_2007_ActaCybernetica.pdf (184.3Kb)
Type
Article accepté pour publication ou publié
Date
2007
Nom de la revue
Acta Cybernetica
Volume
18
Numéro
1
Éditeur
Acta Cybernetica Szeged
Pages
61-75
Métadonnées
Afficher la notice complète
Auteur(s)
Foldes, Stephan
Couceiro, Miguel
Résumé (EN)
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.
Mots-clés
pseudo-Boolean functions; Boolean functions; field-valued functions of Boolean variables; linear equations; multilinear polynomial representations; ring-valued functions; function class definability; relational constraints; functional equa- tion; stability; class composition; Function classes

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Definability of Boolean function classes by linear equations over GF(2) 
    Foldes, Stephan; Couceiro, Miguel (2004) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    On closed sets of relational constraints and classes of functions closed under variable substitutions 
    Foldes, Stephan; Couceiro, Miguel (2005) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Composition of Post classes and normal forms of Boolean functions 
    Lehtonen, Erkko; Foldes, Stephan; Couceiro, Miguel (2006) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Term definable classes of Boolean functions and frame definability in modal logic 
    Kivelä, Jari; Hella, Lauri; Couceiro, Miguel (2008) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Function classes and relational constraints stable under compositions with clones, 
    Foldes, Stephan; Couceiro, Miguel (2009) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo