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 complete classification of equational classes of threshold functions included in clones Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in RAIRO : Operations Research = Recherche Opérationnelle (2015), 49(1), 3966 Detailed reference viewed: 98 (9 UL)Set-reconstructibility of Post classes Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in Discrete Applied Mathematics (2015), 187 Detailed reference viewed: 84 (5 UL)Associative string functions Lehtonen, Erkko ; Marichal, Jean-Luc ; Teheux, Bruno Scientific Conference (2014, June 24) Detailed reference viewed: 140 (15 UL)Associativity, preassociativity, and string functions Lehtonen, Erkko ; Marichal, Jean-Luc ; Teheux, Bruno Scientific Conference (2014, June 20) Detailed reference viewed: 66 (9 UL)Reconstructing multisets over commutative groupoids and affine functions over nonassociative semirings Lehtonen, Erkko in International Journal of Algebra and Computation (2014), 24(1), 11-31 A reconstruction problem is formulated for multisets over commutative groupoids. The cards of a multiset are obtained by replacing a pair of its elements by their sum. Necessary and sufficient conditions ... [more ▼] A reconstruction problem is formulated for multisets over commutative groupoids. The cards of a multiset are obtained by replacing a pair of its elements by their sum. Necessary and sufficient conditions for the reconstructibility of multisets are determined. These results find an application in a different kind of reconstruction problem for functions of several arguments and identification minors: classes of linear or affine functions over nonassociative semirings are shown to be weakly reconstructible. Moreover, affine functions of sufficiently large arity over finite fields are reconstructible. [less ▲] Detailed reference viewed: 90 (3 UL)Hypomorphic Sperner systems and non-reconstructible functions Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in Order (2014) A reconstruction problem is formulated for Sperner systems, and infinite families of non-reconstructible Sperner systems are presented. This has an application to a reconstruction problem for functions of ... [more ▼] A reconstruction problem is formulated for Sperner systems, and infinite families of non-reconstructible Sperner systems are presented. This has an application to a reconstruction problem for functions of several arguments and identification minors. Sperner systems being representations of certain monotone functions, infinite families of non-reconstructible functions are thus obtained. The clones of Boolean functions are completely classified in regard to reconstructibility. [less ▲] Detailed reference viewed: 130 (27 UL)Generalized entropy in expanded semigroups and in algebras with neutral element Lehtonen, Erkko ; in Semigroup Forum (2014) The complex product of (non-empty) subalgebras of a given algebra from a variety V is again a subalgebra if and only if the variety V has the so-called generalized entropic property. This paper is devoted ... [more ▼] The complex product of (non-empty) subalgebras of a given algebra from a variety V is again a subalgebra if and only if the variety V has the so-called generalized entropic property. This paper is devoted to algebras with a neutral element or with a semigroup operation. We investigate relationships between the generalized entropic property and the commutativity of the fundamental operations of the algebra. In particular, we characterize the algebras with a neutral element that have the generalized entropic property. Furthermore, we show that, similarly as for n-monoids and n-groups, for inverse semigroups, the generalized entropic property is equivalent to commutativity. [less ▲] Detailed reference viewed: 120 (1 UL)Sur des classes de fonctions à seuil caractérisables par des contraintes relationnelles ; Lehtonen, Erkko ; Schölzel, Karsten in Marichal, Jean-Luc; Essounbouli, Najib; Guelton, Kevin (Eds.) Actes des 22èmes rencontres francophones sur la Logique Floue et ses Applications, 10-11 octobre 2013, Reims, France (2013, October) Motivated by modal semantics induced by majority games, we consider the class of threshold functions. It was shown by L. Hellerstein that this class is characterizable by relational constraints (or ... [more ▼] Motivated by modal semantics induced by majority games, we consider the class of threshold functions. It was shown by L. Hellerstein that this class is characterizable by relational constraints (or equivalently, by functional equations), but that there is no characterization by means of finitely many constraints. In this paper, we present a complete classification of classes of threshold functions induced by Boolean clones, into whether they are characterizable by finitely many relational constraints. Moreover we provide sets of constraints characterizing each of such classes. [less ▲] Detailed reference viewed: 154 (1 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: 41 (2 UL)Additive decomposability of functions over abelian groups Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás in International Journal of Algebra and 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: 151 (4 UL)Set-reconstructibility of Post classes ; Lehtonen, Erkko ; Schölzel, Karsten E-print/Working paper (2013) The clones of Boolean functions are classified in regard to set-reconstructibility via a strong dichotomy result: the clones containing only affine functions, conjunctions, disjunctions or constant ... [more ▼] The clones of Boolean functions are classified in regard to set-reconstructibility via a strong dichotomy result: the clones containing only affine functions, conjunctions, disjunctions or constant functions are set-reconstructible, whereas the remaing clones are not weakly reconstructible. [less ▲] Detailed reference viewed: 77 (3 UL)A complete classification of equational classes of threshold functions included in clones ; Lehtonen, Erkko ; Schölzel, Karsten E-print/Working paper (2013) The class of threshold functions is known to be characterizable by functional equations or, equivalently, by pairs of relations, which are called relational constraints. It was shown by Hellerstein that ... [more ▼] The class of threshold functions is known to be characterizable by functional equations or, equivalently, by pairs of relations, which are called relational constraints. It was shown by Hellerstein that this class cannot be characterized by a finite number of such objects. In this paper, we investigate classes of threshold functions which arise as intersections of the class of all threshold functions with clones of Boolean functions, and provide a complete classification of such intersections in respect to whether they have finite characterizations. Moreover, we provide a characterizing set of relational constraints for each class of threshold functions arising in this way. [less ▲] Detailed reference viewed: 93 (3 UL)Galois theory for sets of operations closed under permutation, cylindrification and composition Couceiro, Miguel ; Lehtonen, Erkko in Algebra Universalis (2012), 67(3), 273-297 A set of operations on A is shown to be the set of linear term operations of some algebra on A if and only if it is closed under permutation of variables, addition of inessential variables, and ... [more ▼] A set of operations on A is shown to be the set of linear term operations of some algebra on A if and only if it is closed under permutation of variables, addition of inessential variables, and composition, and if it contains all projections. A Galois framework is introduced to describe the sets of operations that are closed under the operations mentioned above, not necessarily containing all projections. The dual objects of this Galois connection are systems of pointed multisets, and the Galois closed sets of dual objects are described accordingly. Moreover, the closure systems associated with this Galois connection are shown to be uncountable (even if the closed sets of operations are assumed to contain all projections). [less ▲] Detailed reference viewed: 137 (1 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: 95 (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: 109 (4 UL)Commuting polynomial operations of distributive lattices ; Couceiro, Miguel ; et al in Order : A Journal on the Theory of Ordered Sets and its Applications (2012), 29(2), 245-269 We describe which pairs of distributive lattice polynomial operations commute. Detailed reference viewed: 99 (0 UL)Partial orders induced by quasilinear clones Lehtonen, Erkko ; in Czermak, J.; Dorfer, G.; Eigenthaler, G. (Eds.) et al Proceedings of the Salzburg Conference 2011 (AAA81) (2012) We find sufficient conditions for a subclone C of Burle's clone and for a subclone of the polynomial clone of a finite semimodule to have the property that the associated C-minor partial order has finite ... [more ▼] We find sufficient conditions for a subclone C of Burle's clone and for a subclone of the polynomial clone of a finite semimodule to have the property that the associated C-minor partial order has finite principal ideals. We also prove that for these clones the C-minor partial order is universal for the class of countable partial orders whose principal ideals are finite. [less ▲] Detailed reference viewed: 47 (5 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: 39 (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: 152 (3 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: 78 (0 UL) |
||