The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
arXiv:1003.2192 · doi:10.1016/j.dam.2011.07.024
Abstract
The aim of this paper is to classify order-preserving functions according to their arity gap. Noteworthy examples of order-preserving functions are so-called aggregation functions. We first explicitly classify the Lovász extensions of pseudo-Boolean functions according to their arity gap. Then we consider the class of order-preserving functions between partially ordered sets, and establish a similar explicit classification for this function class.
11 pages, material reorganized
References in corpus (5)
- Generalizations of Swierczkowski's lemma and the arity gap of finite functions
- Equivalence of operations with respect to discriminator clones
- On the lattice of equational classes of Boolean functions and its closed intervals
- Decompositions of functions based on arity gap
- On the effect of variable identification on the essential arity of functions