Erkko Lehtonen

Extending Sparks’s theorem, we determine the cardinality of the lattice of [ ]-clonoids of Boolean functions for certain pairs [ ] of clones of essentially unary, linear, or [ ]- or [ ]-separating functions or semilattice operations. When such a [ ]-clonoid lattice is uncountable, the proof is in most cases based on exhibiting a countably infinite family of functions with the property that distinct subsets thereof always generate distinct [ ]-clonoids. In the cases when the lattice is finite, we enumerate the corresponding [ ]-clonoids. We also provide a summary of the cardinalities of [ ]-clonoid lattices of Boolean functions.

A necessary and sufficient condition is presented for a graph algebra to satisfy a bracketing identity. The associative spectrum of an arbitrary graph algebra is shown to be either constant or exponentially growing.

Associative spectra of graph algebras are examined with the help of homomorphisms of DFS trees. Undirected graphs are classified according to the associative spectra of their graph algebras; there are only three distinct possibilities: constant 1, powers of 2, and Catalan numbers. Associative and antiassociative digraphs are described, and associative spectra are determined for certain families of digraphs, such as paths, cycles, and graphs on two vertices.

Classes of multisorted minions closed under extensions, reflections, and direct powers are considered from a relational point of view. As a generalization of a result of Barto, Opršal, and Pinsker, the closure of a multisorted minion is characterized in terms of constructions on multisorted relation pairs which are invariant for minions.

Analogical proportions are statements of the form "a is to b as c is to d", where a, b, c, d are tuples of attribute values describing items. The mechanism of analogical inference, empirically proved to be efficient in classification and reasoning tasks, started to be better understood when the characterization of the class of classification functions with which the analogical inference always agrees was established for Boolean attributes. The purpose of this paper is to study the case of finite attribute domains that are not necessarily two-valued, i.e., when attributes are nominal. In particular, we describe the more stringent class of "hard" analogy preserving (HAP) functions f : X1×· · ·×Xm → X over finite domains X1,. .. , Xm, X for binary classification purposes. This description is obtained in two steps. First we observe that such AP functions are almost affine, that is, their restriction to any S1×· · ·×Sm, where Si ⊆ Xi and |Si| ≤ 2 (1 ≤ i ≤ m), can be turned into an affine function by renaming variable and function values. We then use this result together with some universal algebraic tools to show that they are essentially unary or quasi-linear, which provides a general representation of HAP functions. As a by-product, in the case when X1 = · · · = Xm = X, it follows that this class of HAP functions constitutes a clone on X, thus generalizing several results by some of the authors in the Boolean case.