Generalizations of Świerczkowski's lemma and the arity gap of finite functions

DOI10.1016/j.disc.2009.04.009zbMath1200.08001arXiv0712.1753OpenAlexW2040487904WikidataQ124845843 ScholiaQ124845843MaRDI QIDQ1045078

Erkko Lehtonen, Miguel Couceiro

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0712.1753

zbMATH Keywords

Boolean functionarity gapessential variablefinitary functionsemiprojectionvariable identification minorvariable substitution

Mathematics Subject Classification ID

Boolean functions (06E30) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (12)

Parametrized arity gap ⋮ Join-irreducible Boolean functions ⋮ Totally symmetric functions are reconstructible from identification minors ⋮ The arity gap of order-preserving functions and extensions of pseudo-Boolean functions ⋮ Decompositions of functions based on arity gap ⋮ Hesitant fuzzy linguistic ordered weighted distance operators for group decision making ⋮ RECONSTRUCTING MULTISETS OVER COMMUTATIVE GROUPOIDS AND AFFINE FUNCTIONS OVER NONASSOCIATIVE SEMIRINGS ⋮ Variants of Essential Arity for Partial Functions ⋮ ADDITIVE DECOMPOSABILITY OF FUNCTIONS OVER ABELIAN GROUPS ⋮ Majors of functions ⋮ A complete classification of equational classes of threshold functions included in clones ⋮ Set-reconstructibility of Post classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descending chains and antichains of the unary, linear, and monotone subfunction relations
• On a quasi-ordering on Boolean functions
• Small clones and the projection property
• Equivalence of operations with respect to discriminator clones
• An elementary approach to polynomial interpolation in universal algebras
• A projection property
• The forbidden projections of unate functions
• Galois theory for minors of finite functions
• Boolean minors
• A survey of minimal clones
• Essential arities of term operations in finite algebras
• Equational characterizations of Boolean function classes
• Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
• Minimal clones -- a minicourse
• ON THE EFFECT OF VARIABLE IDENTIFICATION ON THE ESSENTIAL ARITY OF FUNCTIONS ON FINITE SETS
• On the Number of Operations in a Clone
• On the lattice of equational classes of Boolean functions and its closed intervals
• Algebras which are independently generated by every n elements

This page was built for publication: Generalizations of Świerczkowski's lemma and the arity gap of finite functions