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

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: 109 (3 UL)A generalization of Completely Separating Systems ; Schölzel, Karsten in Discrete Mathematics (2012), 312(22), 3213-3227 A Completely Separating System (CSS) C on [n] is a collection of blocks of [n] such that for any pair of distinct points x,y ∈ [n], there exist blocks A,B ∈ C such that x ∈ A-B and y ∈ B-A. One possible ... [more ▼] A Completely Separating System (CSS) C on [n] is a collection of blocks of [n] such that for any pair of distinct points x,y ∈ [n], there exist blocks A,B ∈ C such that x ∈ A-B and y ∈ B-A. One possible generalization of CSSs are r-CSSs. Let T be a subset of 2[n], the power set of [n]. A point i ∈ [n] is called r-separable if for every r-subset S ⊆ [n]-i there exists a block T ∈ T with i ∈ T and with the property that S is disjoint from T. If every point i ∈ [n] is r-separable, then T is an r-CSS (or r-(n)CSS). Furthermore, if T is a collection of k-blocks, then T is an r-(n,k)CSS. In this paper we offer some general results, analyze especially the case r=2 with the additional condition that k ≥ 5, present a construction using Latin squares, and mention some open problems. © 2012 Elsevier B.V. All rights reserved. [less ▲] Detailed reference viewed: 92 (0 UL)Weighted lattice polynomials Marichal, Jean-Luc in Discrete Mathematics (2009), 309(4), 814-820 We define the concept of weighted lattice polynomial functions as lattice polynomial functions constructed from both variables and parameters. We provide equivalent forms of these functions in an ... [more ▼] We define the concept of weighted lattice polynomial functions as lattice polynomial functions constructed from both variables and parameters. We provide equivalent forms of these functions in an arbitrary bounded distributive lattice. We also show that these functions include the class of discrete Sugeno integrals and that they are characterized by a median based decomposition formula. [less ▲] Detailed reference viewed: 127 (7 UL)Equivalence of operations with respect to discriminator clones Lehtonen, Erkko ; in Discrete Mathematics (2009), 309(4), 673-685 For each clone C on a set A there is an associated equivalence relation, called C-equivalence, on the set of all operations on A, which relates two operations iff each one is a substitution instance of ... [more ▼] For each clone C on a set A there is an associated equivalence relation, called C-equivalence, on the set of all operations on A, which relates two operations iff each one is a substitution instance of the other using operations from C. In this paper we prove that if C is a discriminator clone on a finite set, then there are only finitely many C-equivalence classes. Moreover, we show that the smallest discriminator clone is minimal with respect to this finiteness property. For discriminator clones of Boolean functions we explicitly describe the associated equivalence relations. [less ▲] Detailed reference viewed: 78 (2 UL)Generalizations of Świerczkowski’s lemma and the arity gap of finite functions Couceiro, Miguel ; Lehtonen, Erkko in Discrete Mathematics (2009), 309(20), 5905-5912 Świerczkowski’s lemma–as it is usually formulated–asserts that if f:Aⁿ→A is an operation on a finite set A, n≥4, and every operation obtained from f by identifying a pair of variables is a projection ... [more ▼] Świerczkowski’s lemma–as it is usually formulated–asserts that if f:Aⁿ→A is an operation on a finite set A, n≥4, and every operation obtained from f by identifying a pair of variables is a projection, then f is a semiprojection. We generalize this lemma in various ways. First, it is extended to B-valued functions on A instead of operations on A and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Świerczkowski’s lemma. Moreover, we explicitly classify all pseudo-Boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of B-valued functions on arbitrary finite sets A. [less ▲] Detailed reference viewed: 97 (1 UL)On weakly convex star-shaped polyhedra Schlenker, Jean-Marc in Discrete Mathematics (2009), 309(20), 6139--6145 Detailed reference viewed: 88 (1 UL)Lattice of subalgebras in the finitely generated varieties of MV-algebras Teheux, Bruno in Discrete Mathematics (2007), 307(17–18), 2261-2275 In this paper, we use the theory of natural duality to study subalgebra lattices in the finitely generated varieties of MV-algebras. With this tool, we obtain the dual atomicity of these lattices, and ... [more ▼] In this paper, we use the theory of natural duality to study subalgebra lattices in the finitely generated varieties of MV-algebras. With this tool, we obtain the dual atomicity of these lattices, and characterize the members of these varieties in which every subalgebra is an intersection of maximal subalgebras. Then, we determine the algebras that have a modular or distributive lattice of subalgebras. [less ▲] Detailed reference viewed: 126 (4 UL)Composition of Post classes and normal forms of Boolean functions Couceiro, Miguel ; ; Lehtonen, Erkko in Discrete Mathematics (2006), 306(24), 3223-3243 The class composition CK of Boolean clones, being the set of composite functions f(g1,...,gn) with f∈C, g1,...,gn∈K, is investigated. This composition CK is either the join C∨K in the Post Lattice or it ... [more ▼] The class composition CK of Boolean clones, being the set of composite functions f(g1,...,gn) with f∈C, g1,...,gn∈K, is investigated. This composition CK is either the join C∨K in the Post Lattice or it is not a clone, and all pairs of clones C,K are classified accordingly. Factorizations of the clone Ω of all Boolean functions as a composition of minimal clones are described and seen to correspond to normal form representations of Boolean functions. The median normal form, arising from the factorization of Ω with the clone SM of self-dual monotone functions as the leftmost composition factor, is compared in terms of complexity with the well-known DNF, CNF, and Zhegalkin (Reed–Muller) polynomial representations, and it is shown to provide a more efficient normal form representation. [less ▲] Detailed reference viewed: 107 (0 UL) |
||