The arity gap of order-preserving functions and extensions of pseudo-Boolean functions

DOI10.1016/j.dam.2011.07.024zbMath1246.06005arXiv1003.2192MaRDI QIDQ412326

Tamás Waldhauser, Miguel Couceiro, Erkko Lehtonen

Publication date: 4 May 2012

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

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

zbMATH Keywords

Lovász extension; Owen extension; pseudo-Boolean function; arity gap; order-preserving function

Mathematics Subject Classification ID

90C09: Boolean programming

06E30: Boolean functions

08A40: Operations and polynomials in algebraic structures, primal algebras

Related Items

ADDITIVE DECOMPOSABILITY OF FUNCTIONS OVER ABELIAN GROUPS, Hypomorphic Sperner systems and non-reconstructible functions, Parametrized arity gap

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decompositions of functions based on arity gap
• Descending chains and antichains of the unary, linear, and monotone subfunction relations
• On a quasi-ordering on Boolean functions
• Equivalence of operations with respect to discriminator clones
• Generalizations of Świerczkowski's lemma and the arity gap of finite functions
• A theory of fuzzy measures: Representations, the Choquet integral, and null sets
• The forbidden projections of unate functions
• Galois theory for minors of finite functions
• Boolean minors
• 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
• ON THE EFFECT OF VARIABLE IDENTIFICATION ON THE ESSENTIAL ARITY OF FUNCTIONS ON FINITE SETS
• Extensions of functions of 0-1 variables and applications to combinatorial optimization
• On the Number of Operations in a Clone
• On the lattice of equational classes of Boolean functions and its closed intervals
• Multilinear Extensions of Games