A complete classification of equational classes of threshold functions included in clones

in RAIRO: Recherche Opérationnelle (2015), 49(1), 3966

Parametrized arity gap

in Order: A Journal on the Theory of Ordered Sets and its Applications (2013), 30(2), 557-572

We propose a parametrized version of arity gap. The parametrized arity gap gap(f,l) of a function f: Aⁿ → B measures the minimum decrease in the number of essential variables of f when l consecutive ... [more ▼]

We propose a parametrized version of arity gap. The parametrized arity gap gap(f,l) of a function f: Aⁿ → B measures the minimum decrease in the number of essential variables of f when l consecutive identifications of pairs of essential variables are performed. We determine gap(f,l) for an arbitrary function f and a positive integer l. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions. [less ▲]

Additive decomposability of functions over abelian groups

in International Journal of Algebra and Computation (2013), 23(3), 643-662

Abelian groups are classified by the existence of certain additive decompositions of group-valued functions of several variables.

Locally monotone Boolean and pseudo-Boolean functions

in Discrete Applied Mathematics (2012), 160(12), 1651-1660

We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on ... [more ▼]

We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on tuples which differ in less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are shown to be tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions are shown to have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden "sections", i.e., functions which can be obtained by substituting constants for variables. This description is made explicit in the special case when p=2. [less ▲]

Intersections of Finitely Generated Maximal Partial Clones

in Journal of Multiple-Valued Logic and Soft Computing (2012), 19(1-3), 85-94

Let A be a finite non-singleton set. For A ={0, 1} we show that the set of all self-dual monotonic partial functions is a not finitely generated partial clone on {0, 1} and that it contains a family of ... [more ▼]

Let A be a finite non-singleton set. For A ={0, 1} we show that the set of all self-dual monotonic partial functions is a not finitely generated partial clone on {0, 1} and that it contains a family of partial subclones of continuum cardinality. Moreover, for |A| ≥ 3, we show that there are pairs of finitely generated maximal partial clones whose intersection is a not finitely generated partial clone on A. [less ▲]

General Interpolation by Polynomial Functions of Distributive Lattices

in 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (2012)

Gap vs. pag

in 42nd IEEE International Symposium on Multiple-Valued Logic (ISMVL 2012) (2012)

We propose a parametrized version of arity gap. The parametrized arity gap gap(f,l) of a function f: Aⁿ→B measures the minimum decrease in the number of essential variables of f when l consecutive ... [more ▼]

We propose a parametrized version of arity gap. The parametrized arity gap gap(f,l) of a function f: Aⁿ→B measures the minimum decrease in the number of essential variables of f when l consecutive identifications of pairs of essential variables are performed. We determine gap(f,l) for an arbitrary function f and a positive integer l. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions. [less ▲]

Hierarchies of local monotonicities and lattice derivatives for Boolean and pseudo-Boolean functions

in Miller, D. Michael; Gaudet, Vincent C. (Eds.) 42nd IEEE International Symposium on Multiple-Valued Logic, ISMVL 2012, Victoria, BC, Canada, May 14-16, 2012 (2012)

In this paper we report recent results in [1] concerning local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if each ... [more ▼]

In this paper we report recent results in [1] concerning local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if each of its partial derivatives keeps the same sign on tuples which differ on less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden “sections”, i.e., functions which can be obtained by substituting variables for constants. This description is made explicit in the special case when p=2. [less ▲]

Decompositions of functions based on arity gap

in Discrete Mathematics (2012), 312(2), 238-247

We study the arity gap of functions of several variables defined on an arbitrary set A and valued in another set B. The arity gap of such a function is the minimum decrease in the number of essential ... [more ▼]

We study the arity gap of functions of several variables defined on an arbitrary set A and valued in another set B. The arity gap of such a function is the minimum decrease in the number of essential variables when variables are identified. We establish a complete classification of functions according to their arity gap, extending existing results for finite functions. This classification is refined when the codomain B has a group structure, by providing unique decomposition into sums of functions of a prescribed form. As an application of the unique decompositions, in the case of finite sets we count, for each n and p, the number of n-ary functions that depend on all of their variables and have arity gap p. [less ▲]

Quasi-Lovász extensions and their symmetric counterparts

in Greco, S.; Bouchon-Meunier, B.; Coletti, G. (Eds.) et al Advances on Computational Intelligence, Part IV, 14th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU 2012, Catania, Italy, July 9-13, 2012, Proceedings, Part IV (2012)

We introduce the concept of quasi-Lov\'asz extension as being a mapping $f\colon I^n\to\R$ defined over a nonempty real interval $I$ containing the origin, and which can be factorized as $f(x_1,\ldots,x_n ... [more ▼]

We introduce the concept of quasi-Lov\'asz extension as being a mapping $f\colon I^n\to\R$ defined over a nonempty real interval $I$ containing the origin, and which can be factorized as $f(x_1,\ldots,x_n)=L(\varphi(x_1),\ldots,\varphi(x_n))$, where $L$ is the Lov\'asz extension of a pseudo-Boolean function $\psi\colon\{0,1\}^n\to\R$ (i.e., the function $L\colon\R^n\to\R$ whose restriction to each simplex of the standard triangulation of $[0,1]^n$ is the unique affine function which agrees with $\psi$ at the vertices of this simplex) and $\varphi\colon I\to\R$ is a nondecreasing function vanishing at the origin. These functions appear naturally within the scope of decision making under uncertainty since they subsume overall preference functionals associated with discrete Choquet integrals whose variables are transformed by a given utility function. To axiomatize the class of quasi-Lov\'asz extensions, we propose generalizations of properties used to characterize the Lov\'asz extensions, including a comonotonic version of modularity and a natural relaxation of homogeneity. A variant of the latter property enables us to axiomatize also the class of symmetric quasi-Lov\'asz extensions, which are compositions of symmetric Lov\'asz extensions with $1$-place nondecreasing odd functions. [less ▲]