References of "Lehtonen, Erkko 40020644"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailA complete classification of equational classes of threshold functions included in clones
Couceiro, Miguel UL; Lehtonen, Erkko UL; Schölzel, Karsten UL

in RAIRO : Operations Research = Recherche Opérationnelle (2015), 49(1), 3966

Detailed reference viewed: 57 (2 UL)
Full Text
Peer Reviewed
See detailSet-reconstructibility of Post classes
Couceiro, Miguel UL; Lehtonen, Erkko UL; Schölzel, Karsten UL

in Discrete Applied Mathematics (2015), 187

Detailed reference viewed: 36 (1 UL)
Full Text
Peer Reviewed
See detailAssociative string functions
Lehtonen, Erkko UL; Marichal, Jean-Luc UL; Teheux, Bruno UL

Scientific Conference (2014, June 24)

Detailed reference viewed: 83 (15 UL)
Full Text
Peer Reviewed
See detailAssociativity, preassociativity, and string functions
Lehtonen, Erkko UL; Marichal, Jean-Luc UL; Teheux, Bruno UL

Scientific Conference (2014, June 20)

Detailed reference viewed: 50 (9 UL)
Full Text
Peer Reviewed
See detailHypomorphic Sperner systems and non-reconstructible functions
Couceiro, Miguel UL; Lehtonen, Erkko UL; Schölzel, Karsten UL

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: 84 (27 UL)
Full Text
Peer Reviewed
See detailGeneralized entropy in expanded semigroups and in algebras with neutral element
Lehtonen, Erkko UL; Pilitowska, Agata

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: 70 (1 UL)
Full Text
Peer Reviewed
See detailReconstructing multisets over commutative groupoids and affine functions over nonassociative semirings
Lehtonen, Erkko UL

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: 58 (3 UL)
Full Text
Peer Reviewed
See detailSur des classes de fonctions à seuil caractérisables par des contraintes relationnelles
Couceiro, Miguel; Lehtonen, Erkko UL; Schölzel, Karsten UL

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: 93 (1 UL)
See detailSet-reconstructibility of Post classes
Couceiro, Miguel; Lehtonen, Erkko UL; Schölzel, Karsten UL

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: 48 (3 UL)
Full Text
Peer Reviewed
See detailAdditive decomposability of functions over abelian groups
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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: 99 (3 UL)
See detailA complete classification of equational classes of threshold functions included in clones
Couceiro, Miguel; Lehtonen, Erkko UL; Schölzel, Karsten UL

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: 57 (3 UL)
Full Text
Peer Reviewed
See detailParametrized arity gap
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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)
Full Text
Peer Reviewed
See detailCommuting polynomial operations of distributive lattices
Behrisch, Mike; Couceiro, Miguel UL; Kearnes, Keith A. 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: 46 (0 UL)
Full Text
Peer Reviewed
See detailPartial orders induced by quasilinear clones
Lehtonen, Erkko UL; Szendrei, Ágnes

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: 29 (3 UL)
Full Text
Peer Reviewed
See detailGalois theory for sets of operations closed under permutation, cylindrification and composition
Couceiro, Miguel UL; Lehtonen, Erkko UL

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: 86 (1 UL)
Full Text
Peer Reviewed
See detailThe arity gap of order-preserving functions and extensions of pseudo-Boolean functions
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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: 58 (4 UL)
Full Text
Peer Reviewed
See detailGap vs. pag
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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: 24 (0 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: 59 (3 UL)
Full Text
Peer Reviewed
See detailAn algorithm for producing median formulas for Boolean functions
Couceiro, Miguel UL; Lehtonen, Erkko UL; Marichal, Jean-Luc UL 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: 138 (3 UL)
Full Text
Peer Reviewed
See detailA survey on the arity gap
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

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