Narrow Results

We study the algorithmic complexity of determining whether a system of polynomial equations over a finite algebra admits a solution. We characterize, within various families of algebras, which of them give rise to an NP-complete problem and which yield a problem solvable in polynomial time. In particular, we prove a dichotomy result which encompasses the cases of lattices, rings, modules, quasigroups and also generalizes a result of Goldmann and Russell for groups [15].

We study the algorithmic complexity of determining whether a system of polynomial equations over a finite algebra admits a solution. We prove that the problem has a dichotomy in the class of finite groupoids with an identity element. By developing the underlying idea further, we present a dichotomy theorem in the class of finite algebras that admit a non-trivial idempotent Maltsev condition. This is a substantial extension of most of the earlier results on the topic.

A semigroup is complex if it generates a variety with the property that every finite lattice is embeddable in its subvariety lattice. In this paper, subvariety lattices of varieties generated by small semigroups will be investigated. Specifically, all complex semigroups of minimal order will be identified.

Modes are idempotent and entropic algebras. Although it had been established many years ago that groupoid modes embed as subreducts of semimodules over commutative semirings, the general embeddability question remained open until Stronkowski and Stanovský's recent constructions of isolated examples of modes without such an embedding. The current paper now presents a broad class of modes that are not embeddable into semimodules, including structural investigations and an analysis of the lattice of varieties.

A variety is said to be a Rees–Sushkevich variety if it is contained in a periodic variety generated by 0-simple semigroups. It is shown that all combinatorial Rees–Sushkevich varieties are finitely based.

A gap in the proof of Proposition 4.5 in the article cited in the heading is mended.

Differential modes provide examples of modes that do not embed as subreducts into semimodules over commutative semirings. The current paper studies differential modes, so-called Szendrei differential modes, which actually do embed into semimodules. These algebras form a variety. The main result states that the lattice of nontrivial subvarieties is dually isomorphic to the (nonmodular) lattice of congruences of the free commutative monoid on two generators. Consequently, all varieties of Szendrei differential modes are finitely based.

We consider uniformities associated with a variety of finite monoids V, but we work with arbitrary monoids and not only with free or free profinite monoids. The aim of this paper is to address two general questions on these uniform structures and a few more specialized ones. A first question is whether these uniformities can be defined by a metric or a pseudometric. The second question is the description of continous and uniformly continuous functions. We first give a characterization of these functions in term of recognizable sets and use it to extend a result of Reutenauer and Schützenberger on continuous functions for the pro-group topology. Next we introduce the notion of hereditary continuity and discuss the behaviour of our three main properties (continuity, uniform continuity, hereditary continuity) under composition, product or exponential. In the last section, we analyze the properties of V-uniform continuity when V is the intersection or the join of a family of varieties and we discuss in some detail the case where V is commutative.

The connection between classical model theoretical types (MT-types) and logically-geometrical types (LG-types) introduced by B. Plotkin is considered. It is proved that MT-types of two $n$-tuples in two universal algebras coincide if and only if their LG-types coincide. Two problems set by B. Plotkin are considered: (1) let two tuples in an algebra have the same type, does it imply that they are connected by an automorphism of this algebra? and (2) let two algebras have the same type, does it imply that they are isomorphic? Some varieties of universal algebras are considered having in view these problems. In particular, it is proved that if a variety is hopfian or co-hopfian, then finitely generated free algebras of such a variety are completely determined by their type.

The number of distinct $n$-variable word maps on a finite group $G$ is the order of the rank $n$ free group in the variety generated by $G$. For a group $G$, the number of word maps on just two variables can be quite large. We improve upon previous bounds for the number of word maps over a finite group $G$. Moreover, we show that our bound is sharp for the number of 2-variable word maps over the affine group over fields of prime order and over the alternating group on five symbols.

We study splittings or lack of them, in lattices of subvarieties of some logic-related varieties. We present a general lemma, the non-splitting lemma, which when combined with some variety-specific constructions, yields each of our negative results: the variety of commutative integral residuated lattices contains no splitting algebras, and in the varieties of double Heyting algebras, dually pseudocomplemented Heyting algebras and regular double $p$-algebras the only splitting algebras are the two-element and three-element chains.

We study semigroup varieties generated by full and upper triangular tropical matrix semigroups and the plactic monoid of rank 4. We prove that the upper triangular tropical matrix semigroup ${\mathrm{\text{UT}}}_n(𝕋)$ generates a different semigroup variety for each dimension $n$. We show a weaker version of this fact for the full matrix semigroup: full tropical matrix semigroups of different prime dimensions generate different semigroup varieties. For the plactic monoid of rank 4, ${\mathbb{P}}_4$, we find a new set of identities satisfied by ${\mathbb{P}}_4$ shorter than those previously known, and show that the semigroup variety generated by ${\mathbb{P}}_4$ is strictly contained in the variety generated by ${\mathrm{\text{UT}}}_5(𝕋)$.

Graph algebras establish a connection between directed graphs without multiple edges and special universal algebras of type (2,0). We say that a graph G satisfies a term equation s ≈ t if the corresponding graph algebra A(G) satisfies s ≈ t. A class of graph algebras V is called a graph variety if V = Mod_gΣ where Σ is a subset of T(X) × T(X). A graph variety V' = Mod_gΣ' is called a biregular leftmost graph variety if Σ' is a set of biregular leftmost term equations. A term equation s ≈ t is called an identity in a variety V if G satisfies s ≈ t for all G ∈ V.

In this paper we characterize identities in each biregular leftmost graph variety. For identities, varieties and other basic concepts of universal algebra see e.g. [1].

In the present paper, we classify varieties of algebraic systems of the type $((n),(m))$, for natural numbers $n$ and $m$, which are closed under particular derived algebraic systems. If we replace in an algebraic system the $n$-ary operation by an $n$-ary term operation and the $m$-ary relation by the $m$-ary relation generated by an $m$-ary formula, we obtain a new algebraic system of the same type, which we call derived algebraic system. We shall restrict the replacement to so-called “linear” terms and atomic “linear” formulas, respectively.

Graph algebras establish a connection between directed graphs without multiple edges and special universal algebras of type $(2,0)$. We say that a graph $G$ satisfies a term equation $s\approx t$ if the corresponding graph algebra $\underline{A(G)}$ satisfies $s\approx t$. The set of all term equations $s\approx t$, which the graph $G$ satisfies, is denoted by $\mathrm{\text{Id}}(\{G\})$. The class of all graph algebras satisfy all term equations in $\mathrm{\text{Id}}(\{G\})$ is called the graph variety generated by $G$ denoted by ${{𝒱}}_g(\{G\})$. A term is called a linear term if each variable which occurs in the term, occurs only once. A term equation $s\approx t$ is called a linear term equation if $s$ and $t$ are linear terms. This paper is devoted to a thorough investigation of graph varieties defined by linear term equations. In particular, we give a complete description of rooted graphs generating a graph variety described by linear term equations.

We have shown that a variety of left(right) normal bands is closed in some homotypical varieties. Further, we partially generalize a result of Isbell from the class of commutative semigroups to some generalized classes of commutative semigroups by showing that dominion of such semigroups belongs to same classes.