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.

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 ▲]

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 ▲]

On signature-based expressions of system reliability

in Journal of Multivariate Analysis (2011), 102(10), 1410-1416

The concept of signature was introduced by Samaniego for systems whose components have i.i.d. lifetimes. This concept proved to be useful in the analysis of theoretical behaviors of systems. In particular ... [more ▼]

The concept of signature was introduced by Samaniego for systems whose components have i.i.d. lifetimes. This concept proved to be useful in the analysis of theoretical behaviors of systems. In particular, it provides an interesting signature-based representation of the system reliability in terms of reliabilities of k-out-of-n systems. In the non-i.i.d. case, we show that, at any time, this representation still holds true for every coherent system if and only if the component states are exchangeable. We also discuss conditions for obtaining an alternative representation of the system reliability in which the signature is replaced by its non-i.i.d. extension. Finally, we discuss conditions for the system reliability to have both representations. [less ▲]

Agents in the shadow (cooperative games with non-cooperating players)

Scientific Conference (2011, July 19)

The aim of this talk is to report on recent investigations about lattice derivatives of Boolean and pseudo-Boolean functions and their interpretations in game theory. The partial lattice derivatives of a ... [more ▼]

The aim of this talk is to report on recent investigations about lattice derivatives of Boolean and pseudo-Boolean functions and their interpretations in game theory. The partial lattice derivatives of a (pseudo-) Boolean function are analogues of the classical partial derivatives, with the difference operation replaced by the minimum or the maximum operation. We focus on commutation properties of these lattice differential operators and relate them to local monotonicity properties. The least and greatest functions that can be obtained from a given function f, by forming lattice derivatives with respect to all variables, are called the lower and the upper shadows of f, respectively. It turns out that the lower and upper shadows of f coincide with the alpha- and beta-effectivity functions of the cooperative game corresponding to f. Thus a function f has a unique shadow if and only if the two effectivity functions coincide, which is equivalent to the fact that certain two-player zero-sum games associated with (the cooperative game corresponding to) f are strictly determined. We formulate a conjecture about Boolean functions (i.e., simple games) with a unique shadow, and present proofs in some special cases as well as results of computer experiments that support our conjecture. [less ▲]

On equational definability of function classes

in 41st IEEE International Symposium on Multiple-Valued Logic (ISMVL 2011) (2011)

We propose a notion of functional equation for functions of fixed arity, which is based on a pair of clones. We present necessary conditions for a class of functions to be definable by such equations, and ... [more ▼]

We propose a notion of functional equation for functions of fixed arity, which is based on a pair of clones. We present necessary conditions for a class of functions to be definable by such equations, and show that for certain choices of clones these conditions are also sufficient. [less ▲]