Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Relation graphs and partial clones on a 2-element set. Schölzel, Karsten ; ; 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: 58 (2 UL)A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones Schölzel, Karsten ; Couceiro, Miguel ; 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: 69 (2 UL)Additive decomposability of functions over abelian groups Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás 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: 115 (3 UL)Parametrized arity gap Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás 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)Locally monotone Boolean and pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc ; Waldhauser, Tamás 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: 88 (3 UL)Decompositions of functions based on arity gap Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás 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: 70 (3 UL)The arity gap of order-preserving functions and extensions of pseudo-Boolean functions Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás 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: 70 (4 UL)Gap vs. pag Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás 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: 27 (0 UL)Hierarchies of local monotonicities and lattice derivatives for Boolean and pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc ; Waldhauser, Tamás 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: 85 (2 UL)On signature-based expressions of system reliability Marichal, Jean-Luc ; Mathonet, Pierre ; Waldhauser, Tamás 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: 92 (13 UL)Signatures, decompositions of reliability, and approximation problems Marichal, Jean-Luc ; Mathonet, Pierre ; Waldhauser, Tamás Presentation (2011, September 07) Detailed reference viewed: 33 (0 UL)Agents in the shadow (cooperative games with non-cooperating players) Waldhauser, Tamás ; Couceiro, Miguel ; Marichal, Jean-Luc 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: 108 (0 UL)An algorithm for producing median formulas for Boolean functions Couceiro, Miguel ; Lehtonen, Erkko ; Marichal, Jean-Luc 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: 141 (3 UL)On equational definability of function classes Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás 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: 63 (0 UL)A survey on the arity gap Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás 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: 25 (0 UL) |
||