References of "Discrete Mathematics"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailMaximal bifix decoding
Berthé, V.; De Felice, C.; Dolce, F. et al

in Discrete Mathematics (2014)

Detailed reference viewed: 35 (2 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: 105 (3 UL)
Full Text
Peer Reviewed
See detailA generalization of Completely Separating Systems
Böhm, Matthias; Schölzel, Karsten UL

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: 84 (0 UL)
Full Text
Peer Reviewed
See detailWeighted lattice polynomials
Marichal, Jean-Luc UL

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: 121 (7 UL)
Full Text
Peer Reviewed
See detailEquivalence of operations with respect to discriminator clones
Lehtonen, Erkko UL; Szendrei, Ágnes

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: 74 (2 UL)
Full Text
Peer Reviewed
See detailGeneralizations of Świerczkowski’s lemma and the arity gap of finite functions
Couceiro, Miguel UL; Lehtonen, Erkko UL

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: 90 (1 UL)
Full Text
Peer Reviewed
See detailOn weakly convex star-shaped polyhedra
Schlenker, Jean-Marc UL

in Discrete Mathematics (2009), 309(20), 6139--6145

Detailed reference viewed: 82 (1 UL)
Full Text
Peer Reviewed
See detailLattice of subalgebras in the finitely generated varieties of MV-algebras
Teheux, Bruno UL

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: 121 (4 UL)
Full Text
Peer Reviewed
See detailComposition of Post classes and normal forms of Boolean functions
Couceiro, Miguel UL; Foldes, Stephan; Lehtonen, Erkko UL

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: 102 (0 UL)