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

Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel

Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2012), The arity gap of order-preserving functions and extensions of pseudo-Boolean functions, Discrete Applied Mathematics, 160, 4-5, p. 383-390. http://dx.doi.org/10.1016/j.dam.2011.07.024

Type

Article accepté pour publication ou publié

External document link

http://arxiv.org/abs/1003.2192

Date

2012

Journal name

Discrete Applied Mathematics

Volume

160

Number

4-5

Publisher

Elsevier

Pages

383-390

Abstract (EN)

The aim of this paper is to classify order-preserving functions according to their arity gap. Noteworthy examples of order-preserving functions are the 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.

Subjects / Keywords

Arity gap; order-preserving function; aggregation function; Owen extension; Lovász extension