Set-reconstructibility of Post classes

in Discrete Applied Mathematics (2015), 187

Associative string functions

Scientific Conference (2014, June 24)

Hypomorphic Sperner systems and non-reconstructible functions

in Order: A Journal on the Theory of Ordered Sets and its Applications (2014)

A reconstruction problem is formulated for Sperner systems, and infinite families of non-reconstructible Sperner systems are presented. This has an application to a reconstruction problem for functions of ... [more ▼]

A reconstruction problem is formulated for Sperner systems, and infinite families of non-reconstructible Sperner systems are presented. This has an application to a reconstruction problem for functions of several arguments and identification minors. Sperner systems being representations of certain monotone functions, infinite families of non-reconstructible functions are thus obtained. The clones of Boolean functions are completely classified in regard to reconstructibility. [less ▲]

Reconstructing multisets over commutative groupoids and affine functions over nonassociative semirings

in International Journal of Algebra and Computation (2014), 24(1), 11-31

A reconstruction problem is formulated for multisets over commutative groupoids. The cards of a multiset are obtained by replacing a pair of its elements by their sum. Necessary and sufficient conditions ... [more ▼]

A reconstruction problem is formulated for multisets over commutative groupoids. The cards of a multiset are obtained by replacing a pair of its elements by their sum. Necessary and sufficient conditions for the reconstructibility of multisets are determined. These results find an application in a different kind of reconstruction problem for functions of several arguments and identification minors: classes of linear or affine functions over nonassociative semirings are shown to be weakly reconstructible. Moreover, affine functions of sufficiently large arity over finite fields are reconstructible. [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.

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

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

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

in Discrete Applied Mathematics (2012), 160(4-5), 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 ... [more ▼]

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. [less ▲]

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

An algorithm for producing median formulas for Boolean functions

in Proc. of the Reed Muller 2011 Workshop (2011, July)

We review various normal form representations of Boolean functions and outline a comparative study between them, which shows that the median normal form system provides representations that are more ... [more ▼]

We review various normal form representations of Boolean functions and outline a comparative study between them, which shows that the median normal form system provides representations that are more efficient than the classical DNF, CNF and Reed–Muller (polynomial) normal form representations. We present an algorithm for producing median normal form representations of Boolean functions. [less ▲]