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: 117 (9 UL)Set-reconstructibility of Post classes Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in Discrete Applied Mathematics (2015), 187 Detailed reference viewed: 98 (5 UL)Hypomorphic Sperner systems and non-reconstructible functions Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in Order: A Journal on the Theory of Ordered Sets and its Applications (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: 141 (29 UL)A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones Schölzel, Karsten ; Couceiro, Miguel ; et al in Multiple-Valued Logic (ISMVL), 2013 IEEE 43rd International Symposium on (2013) The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose ... [more ▼] The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose total component is C. We establish some results in this direction and combine them with previous ones to show the following dichotomy result: For every total clone C on 2, the set I(C) is either finite or of continuum cardinality. [less ▲] Detailed reference viewed: 100 (2 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: 53 (3 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: 172 (4 UL)Aczélian n-ary semigroups Couceiro, Miguel ; Marichal, Jean-Luc in Semigroup Forum (2012), 85(1), 81-90 We show that the real continuous, symmetric, and cancellative n-ary semigroups are topologically order-isomorphic to additive real n-ary semigroups. The binary case (n=2) was originally proved by Aczél ... [more ▼] We show that the real continuous, symmetric, and cancellative n-ary semigroups are topologically order-isomorphic to additive real n-ary semigroups. The binary case (n=2) was originally proved by Aczél (1949); there symmetry was redundant. [less ▲] Detailed reference viewed: 168 (19 UL)Locally monotone Boolean and pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc ; Waldhauser, Tamás in Discrete Applied Mathematics (2012), 160(12), 1651-1660 We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on ... [more ▼] We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on tuples which differ in less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are shown to be tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions are shown to have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden "sections", i.e., functions which can be obtained by substituting constants for variables. This description is made explicit in the special case when p=2. [less ▲] Detailed reference viewed: 127 (4 UL)On the Poset of Computation Rules for Nonassociative Calculus Couceiro, Miguel ; in Order: A Journal on the Theory of Ordered Sets and its Applications (2012), 30(1), 269-288 Detailed reference viewed: 85 (1 UL)Intersections of Finitely Generated Maximal Partial Clones Couceiro, Miguel ; in Journal of Multiple-Valued Logic and Soft Computing (2012), 19(1-3), 85-94 Let A be a finite non-singleton set. For A ={0, 1} we show that the set of all self-dual monotonic partial functions is a not finitely generated partial clone on {0, 1} and that it contains a family of ... [more ▼] Let A be a finite non-singleton set. For A ={0, 1} we show that the set of all self-dual monotonic partial functions is a not finitely generated partial clone on {0, 1} and that it contains a family of partial subclones of continuum cardinality. Moreover, for |A| ≥ 3, we show that there are pairs of finitely generated maximal partial clones whose intersection is a not finitely generated partial clone on A. [less ▲] Detailed reference viewed: 33 (1 UL)Polynomial functions over bounded distributive lattices Couceiro, Miguel ; Marichal, Jean-Luc in Journal of Multiple-Valued Logic and Soft Computing (2012), 18(3-4), 247-256 Let $L$ be a bounded distributive lattice. We give several characterizations of those $L^n \to L$ mappings that are polynomial functions, i.e., functions which can be obtained from projections and ... [more ▼] Let $L$ be a bounded distributive lattice. We give several characterizations of those $L^n \to L$ mappings that are polynomial functions, i.e., functions which can be obtained from projections and constant functions using binary joins and meets. Moreover, we discuss the disjunctive normal form representations of these polynomial functions. [less ▲] Detailed reference viewed: 86 (16 UL)Decision making with Sugeno integrals: DMU vs. MCDM Couceiro, Miguel ; ; et al in ECAI 2012 - 20th European Conference on Artificial Intelligence, 27–31 August 2012, Montpellier, France (2012) Detailed reference viewed: 38 (1 UL)General Interpolation by Polynomial Functions of Distributive Lattices Couceiro, Miguel ; ; et al in 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (2012) Detailed reference viewed: 84 (2 UL)A Survey on Intersections of Maximal Partial Clones of Boolean Partial Functions Couceiro, Miguel ; in Multiple-Valued Logic (ISMVL), 2012 42nd IEEE International Symposium on (2012) We survey known results and present some new ones about intersections of maximal partial clones on a 2-element set. Detailed reference viewed: 85 (0 UL)Hierarchies of local monotonicities and lattice derivatives for Boolean and pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc ; Waldhauser, Tamás in Miller, D. Michael; Gaudet, Vincent C. (Eds.) 42nd IEEE International Symposium on Multiple-Valued Logic, ISMVL 2012, Victoria, BC, Canada, May 14-16, 2012 (2012) In this paper we report recent results in [1] concerning local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if each ... [more ▼] In this paper we report recent results in [1] concerning local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if each of its partial derivatives keeps the same sign on tuples which differ on less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden “sections”, i.e., functions which can be obtained by substituting variables for constants. This description is made explicit in the special case when p=2. [less ▲] Detailed reference viewed: 128 (4 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: 105 (3 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: 47 (0 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: 144 (1 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: 117 (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: 110 (1 UL) |
||