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

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: 40 (0 UL)On the homomorphism order of labeled posets ; Lehtonen, Erkko in Order: A Journal on the Theory of Ordered Sets and its Applications (2011), 28(2), 251-265 Partially ordered sets labeled with k labels (k-posets) and their homomorphisms are examined. We give a representation of directed graphs by k-posets; this provides a new proof of the universality of the ... [more ▼] Partially ordered sets labeled with k labels (k-posets) and their homomorphisms are examined. We give a representation of directed graphs by k-posets; this provides a new proof of the universality of the homomorphism order of k-posets. This universal order is a distributive lattice. We investigate some other properties, namely the infinite distributivity, the computation of infinite suprema and infima, and the complexity of certain decision problems involving the homomorphism order of k-posets. Sublattices are also examined. [less ▲] Detailed reference viewed: 97 (2 UL)Self-commuting lattice polynomial functions on chains Couceiro, Miguel ; Lehtonen, Erkko in Aequationes Mathematicae (2011), 81(3), 263-278 We provide sufficient conditions for a lattice polynomial function to be self-commuting. We explicitly describe self-commuting polynomial functions on chains. Detailed reference viewed: 90 (0 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: 96 (0 UL)Explicit descriptions of bisymmetric Sugeno integrals Couceiro, Miguel ; Lehtonen, Erkko in Hüllermeier, Eyke; Kruse, Rudolf; Hoffmann, Frank (Eds.) Computational Intelligence for Knowledge-Based Systems Design (2010) We provide sufficient conditions for a Sugeno integral to be bisymmetric. We explicitly describe bisymmetric Sugeno integrals over chains. Detailed reference viewed: 88 (1 UL)Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms Lehtonen, Erkko ; in European Journal of Combinatorics (2010), 31(8), 1981-1995 Each clone C on a fixed base set A induces a quasi-order on the set of all operations on A by the following rule: f is a C-minor of g if f can be obtained by substituting operations from C for the ... [more ▼] Each clone C on a fixed base set A induces a quasi-order on the set of all operations on A by the following rule: f is a C-minor of g if f can be obtained by substituting operations from C for the variables of g. By making use of a representation of Boolean functions by hypergraphs and hypergraph homomorphisms, it is shown that a clone C on {0,1} has the property that the corresponding C-minor partial order is universal if and only if C is one of the countably many clones of clique functions or the clone of self-dual monotone functions. Furthermore, the C-minor partial orders are dense when C is a clone of clique functions. [less ▲] Detailed reference viewed: 90 (0 UL)Classes of operations closed under permutation, cylindrification and composition Couceiro, Miguel ; Lehtonen, Erkko in 40th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2010) (2010) We describe the classes of operations closed under permutation of variables, addition of dummy variables and composition in terms of a preservation relation between operations and certain systems of ... [more ▼] We describe the classes of operations closed under permutation of variables, addition of dummy variables and composition in terms of a preservation relation between operations and certain systems of multisets. [less ▲] Detailed reference viewed: 90 (0 UL)Characterization of preclones by matrix collections Lehtonen, Erkko in Asian-European Journal of Mathematics (2010), 3(3), 457-473 Preclones are described as the closed classes of the Galois connection induced by a preservation relation between operations and matrix collections. The Galois closed classes of matrix collections are ... [more ▼] Preclones are described as the closed classes of the Galois connection induced by a preservation relation between operations and matrix collections. The Galois closed classes of matrix collections are also described by explicit closure conditions. [less ▲] Detailed reference viewed: 80 (2 UL)The submaximal clones on the three-element set with finitely many relative R-classes Lehtonen, Erkko ; in Discussiones Mathematicae. General Algebra and Applications (2010), 30(1), 7-33 For each clone C on a set A there is an associated equivalence relation analogous to Green's R-relation, which relates two operations on A if and only if each one is a substitution instance of the other ... [more ▼] For each clone C on a set A there is an associated equivalence relation analogous to Green's R-relation, which relates two operations on A if and only if each one is a substitution instance of the other using operations from C. We study the maximal and submaximal clones on a three-element set and determine which of them have only finitely many relative R-classes. [less ▲] Detailed reference viewed: 91 (1 UL)The arity gap of polynomial functions over bounded distributive lattices Couceiro, Miguel ; Lehtonen, Erkko in 40th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2010) (2010) Let A and B be arbitrary sets with at least two elements. The arity gap of a function f : An→ B is the minimum decrease in its essential arity when essential arguments of f are identified. In this paper ... [more ▼] Let A and B be arbitrary sets with at least two elements. The arity gap of a function f : An→ B is the minimum decrease in its essential arity when essential arguments of f are identified. In this paper we study the arity gap of polynomial functions over bounded distributive lattices and present a complete classification of such functions in terms of their arity gap. To this extent, we present a characterization of the essential arguments of polynomial functions, which we then use to show that almost all lattice polynomial functions have arity gap 1, with the exception of truncated median functions, whose arity gap is 2. [less ▲] Detailed reference viewed: 82 (0 UL)A note on minors determined by clones of semilattices Lehtonen, Erkko in Novi Sad Journal of Mathematics (2010), 40(3), 75-81 The C-minor partial orders determined by the clones generated by a semilattice operation (and possibly the constant operations corresponding to its identity or zero elements) are shown to satisfy the ... [more ▼] The C-minor partial orders determined by the clones generated by a semilattice operation (and possibly the constant operations corresponding to its identity or zero elements) are shown to satisfy the descending chain condition. [less ▲] Detailed reference viewed: 40 (0 UL)Closed classes of functions, generalized constraints and clusters Lehtonen, Erkko in Algebra Universalis (2010), 63(2-3), 203-234 Classes of functions of several variables on arbitrary nonempty domains that are closed under permutation of variables and addition of dummy variables are characterized by generalized constraints, and ... [more ▼] Classes of functions of several variables on arbitrary nonempty domains that are closed under permutation of variables and addition of dummy variables are characterized by generalized constraints, and hereby Hellerstein's Galois theory of functions and generalized constraints is extended to infinite domains. Furthermore, classes of operations on arbitrary nonempty domains that are closed under permutation of variables, addition of dummy variables, and composition are characterized by clusters, and a Galois connection is established between operations and clusters. [less ▲] Detailed reference viewed: 84 (0 UL)Column-partitioned matrices over rings without invertible transversal submatrices ; Lehtonen, Erkko in Ars Combinatoria (2010), 97 Let the columns of a p×q matrix M over any ring be partitioned into n blocks, M = [M1,...,Mn]. If no p×p submatrix of M with columns from distinct blocks Mi is invertible, then there is an invertible p×p ... [more ▼] Let the columns of a p×q matrix M over any ring be partitioned into n blocks, M = [M1,...,Mn]. If no p×p submatrix of M with columns from distinct blocks Mi is invertible, then there is an invertible p×p matrix Q and a positive integer m ≤ p such that QM = [QM1,...,QMn] is in reduced echelon form and in all but at most m - 1 blocks QMi the last m entries of each column are either all zero or they include a non-zero non-unit. [less ▲] Detailed reference viewed: 22 (1 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: 91 (1 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: 75 (2 UL)On the arity gap of finite functions: results and applications Couceiro, Miguel ; Lehtonen, Erkko in Boudabbous, Youssef; Zaguia, Nejib (Eds.) Proceedings of the First International Conference on Relations, Orders and Graphs: Interaction with Computer Science (ROGICS '08) (2008) Let A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f:Aⁿ→B is the minimum decrease in the number of essential variables when essential variables of f are ... [more ▼] Let A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f:Aⁿ→B is the minimum decrease in the number of essential variables when essential variables of f are identified. A non-trivial fact is that the arity gap of such B-valued functions on A is at most |A|. Even less trivial to verify is the fact that the arity gap of B-valued functions on A with more than |A| essential variables is at most 2. These facts ask for a classification of B-valued functions on A in terms of their arity gap. In this paper, we survey what is known about this problem. We present a general characterization of the arity gap of B-valued functions on A and provide explicit classifications of the arity gap of Boolean and pseudo-Boolean functions. Moreover, we reveal unsettled questions related to this topic, and discuss links and possible applications of some results to other subjects of research. [less ▲] Detailed reference viewed: 59 (1 UL)Labeled posets are universal Lehtonen, Erkko in European Journal of Combinatorics (2008), 29(2), 493-506 Partially ordered sets labeled with k labels (k-posets) and their homomorphisms are examined. The homomorphicity order of finite k-posets is shown to be a distributive lattice. Homomorphicity orders of ... [more ▼] Partially ordered sets labeled with k labels (k-posets) and their homomorphisms are examined. The homomorphicity order of finite k-posets is shown to be a distributive lattice. Homomorphicity orders of finite k-posets and k-lattices are shown to be universal in the sense that every countable poset can be embedded into them. Labeled posets are represented by directed graphs, and a categorical isomorphism between k-posets and their digraph representations is established. [less ▲] Detailed reference viewed: 72 (0 UL)Operations on Finite Sets, Functional Composition, and Ordered Sets Lehtonen, Erkko Doctoral thesis (2007) The unifying theme of this research work is functional composition. We study operations on a nonempty set A, an important particular case being that of Boolean functions when A = {0, 1}. A class of ... [more ▼] The unifying theme of this research work is functional composition. We study operations on a nonempty set A, an important particular case being that of Boolean functions when A = {0, 1}. A class of operations is a subset of the set of all operations on A. A clone on A is a class of operations on A that contains all projection maps and is closed under functional composition. The first part of this thesis is a study of compositions of the clones of Boolean functions. The clone of all Boolean functions can be decomposed in various ways into minimal clones, and we observe that such decompositions correspond to different normal form systems: the disjunctive normal form (DNF), conjunctive normal form (CNF), Zhegalkin polynomial, dual Zhegalkin polynomial, and so-called median normal form. These normal form systems are compared in terms of efficiency, and we establish that the median normal form system provides in a certain sense more efficient representations than the other four normal form systems mentioned above. The second part of this thesis is a study of certain order relations on the set of all operations on A. For a fixed class C of operations on A, we say that f is a C-subfunction of g, if f can be obtained by composing g from inside with operations from C. We say that f and g are C-equivalent, if f and g are C-subfunctions of each other. The C-subfunction relation is a quasiorder (a reflexive and transitive relation) on the set of all operations on A if and only if the parametrizing class C is a clone. The simplest example of C-subfunction relations is obtained when C is the smallest clone I of projections on A. Forming I-subfunctions corresponds to simple manipulation of variables, namely addition and deletion of dummy variables, permutation of variables, and identification of variables. None of these operations increases the number of essential variables, and only variable identification may decrease this number. We study more carefully the effect of variable identification on the number of essential variables of operations on finite base sets. We then study certain order-theoretical properties of various C-subfunction partial orders defined by larger clones C on finite base sets A. We are mostly concerned about the descending chain condition and the existence of infinite antichains, and as it turns out, these properties on the defining clone C. Homomorphisms of labeled posets (or k-posets) are applied in our analysis of subfunction relations defined by clones of monotone functions. The third part of this thesis is a study of the homomorphicity order of finite k-posets on its own right. We establish that this order is a distributive lattice, and furthermore, it is universal in the sense that every countable poset can be embedded into it. This result implies universality of the subfunction partial orders defined by clones of monotone functions on finite sets of more than two elements. In this way, we also obtain a new proof for the well-known universality of the homomorphicity order of graphs. [less ▲] Detailed reference viewed: 54 (8 UL)On the effect of variable identification on the essential arity of functions on finite sets Couceiro, Miguel ; Lehtonen, Erkko in International Journal of Foundations of Computer Science (2007), 18(5), 975-986 We show that every function of several variables on a finite set of k elements with n > k essential variables has a variable identification minor with at least n − k essential variables. This is a ... [more ▼] We show that every function of several variables on a finite set of k elements with n > k essential variables has a variable identification minor with at least n − k essential variables. This is a generalization of a theorem of Salomaa on the essential variables of Boolean functions. We also strengthen Salomaa's theorem by characterizing all the Boolean functions f having a variable identification minor that has just one essential variable less than f. [less ▲] Detailed reference viewed: 84 (0 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: 102 (0 UL) |
||