References of "Waldhauser, Tamás 40000708"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailRelation graphs and partial clones on a 2-element set.
Schölzel, Karsten UL; Couceiro, Miguel; Haddad, Lucien et al

in Multiple-Valued Logic (ISMVL), 2014 IEEE 44rd International Symposium on (2014)

In a recent paper, the authors show that the sublattice of partial clones that preserve the relation $\{(0,0),(0,1),(1,0)\}$ is of continuum cardinality on $\2$. In this paper we give an alternative proof ... [more ▼]

In a recent paper, the authors show that the sublattice of partial clones that preserve the relation $\{(0,0),(0,1),(1,0)\}$ is of continuum cardinality on $\2$. In this paper we give an alternative proof to this result by making use of a representation of relations derived from $\{(0,0),(0,1),(1,0)\}$ in terms of certain types of graphs. As a by-product, this tool brings some light into the understanding of the structure of this uncountable sublattice of strong partial clones. [less ▲]

Detailed reference viewed: 46 (2 UL)
Full Text
Peer Reviewed
See detailParametrized arity gap
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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

Detailed reference viewed: 27 (2 UL)
Full Text
Peer Reviewed
See detailAdditive decomposability of functions over abelian groups
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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

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

Detailed reference viewed: 97 (3 UL)
Full Text
Peer Reviewed
See detailA Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones
Schölzel, Karsten UL; Couceiro, Miguel UL; Haddad, Lucien et al

in Multiple-Valued Logic (ISMVL), 2013 IEEE 43rd International Symposium on (2013)

The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose ... [more ▼]

The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose total component is C. We establish some results in this direction and combine them with previous ones to show the following dichotomy result: For every total clone C on 2, the set I(C) is either finite or of continuum cardinality. [less ▲]

Detailed reference viewed: 56 (2 UL)
Full Text
Peer Reviewed
See detailLocally monotone Boolean and pseudo-Boolean functions
Couceiro, Miguel UL; Marichal, Jean-Luc UL; Waldhauser, Tamás UL

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

Detailed reference viewed: 73 (3 UL)
Full Text
Peer Reviewed
See detailDecompositions of functions based on arity gap
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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

Detailed reference viewed: 56 (3 UL)
Full Text
Peer Reviewed
See detailThe arity gap of order-preserving functions and extensions of pseudo-Boolean functions
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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

Detailed reference viewed: 56 (4 UL)
Full Text
Peer Reviewed
See detailHierarchies of local monotonicities and lattice derivatives for Boolean and pseudo-Boolean functions
Couceiro, Miguel UL; Marichal, Jean-Luc UL; Waldhauser, Tamás UL

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

Detailed reference viewed: 70 (2 UL)
Full Text
Peer Reviewed
See detailGap vs. pag
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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

Detailed reference viewed: 24 (0 UL)
Full Text
Peer Reviewed
See detailOn signature-based expressions of system reliability
Marichal, Jean-Luc UL; Mathonet, Pierre UL; Waldhauser, Tamás UL

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

Detailed reference viewed: 75 (13 UL)
Full Text
See detailAgents in the shadow (cooperative games with non-cooperating players)
Waldhauser, Tamás UL; Couceiro, Miguel UL; Marichal, Jean-Luc UL

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

Detailed reference viewed: 103 (0 UL)
Full Text
Peer Reviewed
See detailAn algorithm for producing median formulas for Boolean functions
Couceiro, Miguel UL; Lehtonen, Erkko UL; Marichal, Jean-Luc UL et al

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

Detailed reference viewed: 138 (3 UL)
Full Text
Peer Reviewed
See detailA survey on the arity gap
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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

The arity gap of a function of several variables is defined as the minimum decrease in the number of essential variables when essential variables are identified. We present a brief survey on the research ... [more ▼]

The arity gap of a function of several variables is defined as the minimum decrease in the number of essential variables when essential variables are identified. We present a brief survey on the research done on the arity gap, from the first studies of this notion up to recent developments. [less ▲]

Detailed reference viewed: 23 (0 UL)
Full Text
Peer Reviewed
See detailOn equational definability of function classes
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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

Detailed reference viewed: 50 (0 UL)