Publications > Artigos em Revistas Internacionais

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

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

Discrete Applied Mathematics, 160(4-5) (2012), 383-390

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.