Recent zbMATH articles in MSC 08https://zbmath.org/atom/cc/082021-11-25T18:46:10.358925ZWerkzeugFinite coverability propertyhttps://zbmath.org/1472.030272021-11-25T18:46:10.358925Z"Botur, Michal"https://zbmath.org/authors/?q=ai:botur.michal"Broušek, Martin"https://zbmath.org/authors/?q=ai:brousek.martinSummary: In this article we present a new characterization of the class \(\mathrm{HSP}_U(\mathcal {K})\) using a condition analogous to the finite embeddability property.JI-distributive, dually quasi-de Morgan semi-Heyting and Heyting algebrashttps://zbmath.org/1472.060102021-11-25T18:46:10.358925Z"Sankappanavar, Hanamantagouda P."https://zbmath.org/authors/?q=ai:sankappanavar.hanamantagouda-pSummary: The variety \(\mathbf{DQD}\) of dually quasi-De Morgan semi-Heyting algebras and several of its subvarieties were investigated in the series \textit{H. P. Sankappanavar} [Stud. Log. 98, No. 1--2, 27--81 (2011; Zbl 1254.06006); Categ. Gen. Algebr. Struct. Appl. 2, No. 1, 47--64 (2014; Zbl 1371.06008); Categ. Gen. Algebr. Struct. Appl. 2, No. 1, 65--82 (2014; Zbl 1371.06009); Demonstr. Math. 49, No. 3, 252--265 (2016; Zbl 1353.06002); ``Regular dually Stone semi-Heyting algebras'', Preprint; in: New trends in algebras and combinatorics. Proceedings of the 3rd international congress in algebras and combinatorics, ICAC 2017, Hong Kong, China, August 25--28, 2017. In honor of Professor Leonid Bokut on the occasion of his 80th birthday. Hackensack, NJ: World Scientific. 447--457 (2020; Zbl 1448.06003)]. In this paper we define and investigate a new subvariety \(\mathbf{JID}\) of \(\mathbf{DQD}\), called ``JI-distributive, dually quasi-De Morgan semi-Heyting algebras'', defined by the identity: \(x'\vee(y\to z)\approx(x'\vee y)\to(x'\vee z)\), as well as the (closely related) variety \(\mathbf{DSt}\) of dually Stone semi-Heyting algebras. Firstly, we prove that \(\mathbf{DSt}\) and \(\mathbf{JID}\) are discriminator varieties of level 1 and level 2 respectively. Secondly, we give a characterization of subdirectly irreducible algebras of the subvariety \(\mathbf{JID}_1\) of \(\mathbf{JID}\) of level 1. As applications, we derive that the variety \(\mathbf{JID}_1\) is the join of the variety \(\mathbf{DSt}\) and the variety of De Morgan Boolean semi-Heyting algebras, give a concrete description of the subdirectly irreducible algebras in the subvariety \(\mathbf{JIDL}_1\) of \(\mathbf{JID}_1\) defined by the linear identity: \((x\to y)\vee(y\to x)\approx 1\), and deduce that the variety \(\mathbf{JIDL}_1\) is the join of the variety \(\mathbf{DStHC}\) generated by the dually Stone Heyting chains and the variety generated by the 4-element De Morgan Boolean Heyting algebra. Furthermore, we present an explicit description of the lattice of subvarieties of \(\mathbf{JIDL}_1\) and equational bases for all subvarieties of \(\mathbf{JIDL}_1\). Finally, we prove that the amalgamation property holds for all subvarieties of \(\mathbf{DStHC}\).Algebraic geometry for \(\ell \)-groupshttps://zbmath.org/1472.060232021-11-25T18:46:10.358925Z"Di Nola, Antonio"https://zbmath.org/authors/?q=ai:di-nola.antonio"Lenzi, Giacomo"https://zbmath.org/authors/?q=ai:lenzi.giacomo"Vitale, Gaetano"https://zbmath.org/authors/?q=ai:vitale.gaetanoSummary: In this paper we focus on the algebraic geometry of the variety of \(\ell \)-groups (i.e. lattice ordered abelian groups). In particular we study the role of the introduction of constants in functional spaces and \(\ell \)-polynomial spaces, which are themselves \(\ell \)-groups, evaluated over other \(\ell \)-groups. We use different tools and techniques, with an increasing level of abstraction, to describe properties of \(\ell \)-groups, topological spaces (with the Zariski topology) and a formal logic, all linked by the underlying theme of solutions of \(\ell \)-equations.On a product of universal relational systemshttps://zbmath.org/1472.080012021-11-25T18:46:10.358925Z"Phrommarat, Nitima"https://zbmath.org/authors/?q=ai:phrommarat.nitima"Sudsanit, Sivaree"https://zbmath.org/authors/?q=ai:sudsanit.sivareeLet \(\Omega\) be a nonempty set. A family \(\tau =(K_{\lambda}:\lambda\in\Omega)\) of sets is called a type. A universal relational system of type \(\tau\) is a pair \((A,(\rho_{\lambda}:\lambda\in \Omega))\), where \(A\) is a nonempty set, and, for every \(\lambda\in\Omega\), \(\rho_{\lambda}\) is a \(K_{\lambda}\)-ary relation, i.e., \(\rho_{\lambda}\subseteq A^{K_{\lambda}}\). Properties of such systems are described.Menger hyperalgebras and their representationshttps://zbmath.org/1472.080022021-11-25T18:46:10.358925Z"Kumduang, Thodsaporn"https://zbmath.org/authors/?q=ai:kumduang.thodsaporn"Leeratanavalee, Sorasak"https://zbmath.org/authors/?q=ai:leeratanavalee.sorasakMenger hyparalgebras are algebras of \(n\)-ary hyperoperations with Menger compositions of hyperoperations. The obtained results are a simple generalization of results on classical algebras of multiplace functions presented in the book [the reviewer and \textit{V. S. Trokhimenko}, Algebras of multiplace functions. Berlin: Walter de Gruyter (2012; Zbl 1253.08001)].All maximal completely regular submonoids of \(\mathrm{Hyp}_G(n)\)https://zbmath.org/1472.080032021-11-25T18:46:10.358925Z"Kunama, Pornpimol"https://zbmath.org/authors/?q=ai:kunama.pornpimol"Leeratanavalee, Sorasak"https://zbmath.org/authors/?q=ai:leeratanavalee.sorasakSummary: A generalized hypersubstitution of type \(\tau=(n)\) is a mapping \(\sigma\) which maps the \(n\)-ary operation symbol \(f\) to the term \(\sigma(f)\) which does not necessarily preserve the arity. The set of all generalized hypersubstitutions of type \(\tau=(n)\) together with a binary operation defined on this set and the identity hypersubstitution \(\sigma_{id}\) which maps \(f\) to the term \(f(x_1,\dots,x_n)\) forms a monoid. Our motivation in this paper, is to determine all maximal completely regular submonoids of this monoid.Infinitary Baker-Pixley theoremhttps://zbmath.org/1472.080042021-11-25T18:46:10.358925Z"Vaggione, Diego J."https://zbmath.org/authors/?q=ai:vaggione.diego-joseSummary: An important theorem of \textit{K. A. Baker} and \textit{A. F. Pixley} [Math. Z. 143, 165--174 (1975; Zbl 0292.08004)] states that if \(\mathbf {A}\) is a finite algebra with a \((d+1)\)-ary near-unanimity term and \(f\) is an \(n\)-ary operation on \(A\) such that every subalgebra of \(\mathbf {A}^{d}\) is closed under \(f\), then \(f\) is representable by a term in \(\mathbf {A}\). It is well known that the Baker-Pixley theorem does not hold when \(\mathbf {A}\) is infinite. We give an infinitary version of the Baker-Pixley theorem which applies to an arbitrary class of structures with a \((d+1)\)-ary near-unanimity term instead of a single finite algebra.Clone-induced approximation algebras of Bernoulli distributionshttps://zbmath.org/1472.080052021-11-25T18:46:10.358925Z"Yashunsky, Alexey D."https://zbmath.org/authors/?q=ai:yashunsky.aleksey-dSummary: We consider the problem of approximating distributions of Bernoulli random variables by applying Boolean functions to independent random variables with distributions from a given set. For a set \(B\) of Boolean functions, the set of approximable distributions forms an algebra, named the approximation algebra of Bernoulli distributions induced by \(B\). We provide a complete description of approximation algebras induced by most clones of Boolean functions. For remaining clones, we prove a criterion for approximation algebras and a property of algebras that are finitely generated.\( \omega \)-categorical structures avoiding height 1 identitieshttps://zbmath.org/1472.080062021-11-25T18:46:10.358925Z"Bodirsky, Manuel"https://zbmath.org/authors/?q=ai:bodirsky.manuel"Mottet, Antoine"https://zbmath.org/authors/?q=ai:mottet.antoine"Olšák, Miroslav"https://zbmath.org/authors/?q=ai:olsak.miroslav"Opršal, Jakub"https://zbmath.org/authors/?q=ai:oprsal.jakub"Pinsker, Michael"https://zbmath.org/authors/?q=ai:pinsker.michael"Willard, Ross"https://zbmath.org/authors/?q=ai:willard.rossIt is an open problem whether there exists a P/(NP-complete) dichotomy for first-order reducts of finitely bounded homogeneous structures. This paper refutes some plausible conjectures related to this problem. The two main theorems are:
Theorem~1.3. For every nontrivial height \(1\) condition \(\Sigma\) there exists a structure \(\mathbb B\) such that
\begin{itemize}
\item \(\mathbb B\) is a first-order reduct of a finitely bounded homogeneous structure;
\item \(\textrm{Pol}(\mathbb B)\) does not satisfy \(\Sigma\);
\item \(\textrm{Pol}(\mathbb B)\) satisfies some other nontrivial height \(1\) condition (consequently, there is no minion homomorphism to \(\mathcal P\));
\item \(\textrm{CSP}(\mathbb B)\) is in \(P\).
\end{itemize}
Theorem~1.4. There exists a structure \(\mathbb S\) with the following properties:
\begin{enumerate}
\item[(1)] \(\mathbb S\) is an \(\omega\)-categorical structure with less than doubly exponential orbit growth.
\item[(2)] \(\textrm{Pol}(\mathbb S)\) has a minion homomorphism to \(\mathcal P\).
\item[(3)] \(\textrm{Pol}(\mathbb S)\) has no uniformly continuous minion homomorphism to \(\mathcal P\).
\end{enumerate}
In these theorems, \(\mathcal P\) (calligraphic font) is the clone of projections.Taylor term does not imply any nontrivial linear one-equality Maltsev conditionhttps://zbmath.org/1472.080072021-11-25T18:46:10.358925Z"Kazda, Alexandr"https://zbmath.org/authors/?q=ai:kazda.alexandrSummary: It is known that any finite idempotent algebra that satisfies a nontrivial Maltsev condition must satisfy the linear one-equality Maltsev condition (a variant of the term discovered by \textit{M. H. Siggers} [Algebra Univers. 64, No. 1--2, 15--20 (2010; Zbl 1216.08002)] and refined by \textit{K. Kearnes} et al. [Algebra Univers. 72, No. 1, 91--100 (2014; Zbl 1305.08008)]):
\[
t(r,a,r,e)\approx t(a,r,e,a).
\]
We show that if we drop the finiteness assumption, the \(k\)-ary weak near unanimity equations imply only trivial linear one-equality Maltsev conditions for every \(k\geq3\). From this it follows that there is no nontrivial linear one-equality condition that would hold in all idempotent algebras having Taylor terms. \textit{M. Olšák} [Bull. Lond. Math. Soc. 49, No. 6, 1028--1047 (2017; Zbl 1414.08002)] has recently shown that there is a weakest nontrivial strong Maltsev condition for idempotent algebras. Olšák has found several such (mutually equivalent) conditions consisting of two or more equations. Our result shows that Olšák's equation systems cannot be compressed into just one equation.Abelian doppelsemigroupshttps://zbmath.org/1472.080082021-11-25T18:46:10.358925Z"Zhuchok, Anatolii V."https://zbmath.org/authors/?q=ai:zhuchok.anatolii-v"Knauer, Kolja"https://zbmath.org/authors/?q=ai:knauer.kolja-bSummary: A doppelsemigroup is an algebraic system consisting of a set with two binary associative operations satisfying certain identities. Doppelsemigroups are a generalization of semigroups and they have relationships with such algebraic structures as doppelalgebras, duplexes, interassociative semigroups, restrictive bisemigroups, dimonoids and trioids. This paper is devoted to the study of abelian doppelsemigroups. We show that every abelian doppelsemigroup can be constructed from a left and right commutative semigroup and describe the free abelian doppelsemigroup. We also characterize the least abelian congruence on the free doppelsemigroup, give examples of abelian doppelsemigroups and find conditions under which the operations of an abelian doppelsemigroup coincide.Variations of the shifting lemma and Goursat categorieshttps://zbmath.org/1472.080092021-11-25T18:46:10.358925Z"Gran, Marino"https://zbmath.org/authors/?q=ai:gran.marino"Rodelo, Diana"https://zbmath.org/authors/?q=ai:rodelo.diana"Nguefeu, Idriss Tchoffo"https://zbmath.org/authors/?q=ai:nguefeu.idriss-tchoffoSummary: We prove that Mal'tsev and Goursat categories may be characterized through variations of the Shifting Lemma, that is classically expressed in terms of three congruences \(R\), \(S\) and \(T\), and characterizes congruence modular varieties. We first show that a regular category \(\mathbb{C}\) is a Mal'tsev category if and only if the Shifting Lemma holds for reflexive relations on the same object in \(\mathbb{C}\). Moreover, we prove that a regular category \(\mathbb{C}\) is a Goursat category if and only if the Shifting Lemma holds for a reflexive relation \(S\) and reflexive and positive relations \(R\) and \(T\) in \(\mathbb{C}\). In particular this provides a new characterization of 2-permutable and 3-permutable varieties and quasi-varieties of universal algebras.Dualisability of partial unarshttps://zbmath.org/1472.080102021-11-25T18:46:10.358925Z"Johansen, Sarah M."https://zbmath.org/authors/?q=ai:johansen.sarah-mSummary: The dualisability of partial algebras is a largely unexplored area within natural duality theory. This paper considers the dualisability of finite structures that have a single partial unary operation in the type. We show that every such finite partial unar is dualisable. We obtain this result by showing that the relational structure obtained by replacing the fundamental operation by its graph is dualisable. We also give a finite generator for the class of all disjoint unions of directed trees up to some fixed height, considered as partial unars.Saturations of subalgebras, SAGBI bases, and U-invariantshttps://zbmath.org/1472.130442021-11-25T18:46:10.358925Z"Bigatti, Anna Maria"https://zbmath.org/authors/?q=ai:bigatti.anna-maria"Robbiano, Lorenzo"https://zbmath.org/authors/?q=ai:robbiano.lorenzoLet \(R=K[x_1,\dots ,x_n]\) and \(F\) be a (not necessarily finite) subset of \(R\). Then the subalgebra of \(R\) generated by \(F\) is denoted \(K[F]\). Similar to the notion of Grobner bases for ideals of \(R\), we can define the notion of SAGBI Gröbner basis for \(K[F]\) (see e.g. the paper of the second author and \textit{M. Sweedler} [Lect. Notes Math. 1430, 61--87 (1990; Zbl 0725.13013)] which is regarded as a pioneer work).
Let \(S\) be a \(K\)-subalgebra of the polynomial ring \(R\) , and let \(0 \ne g\in S\). We denote the set \(\bigcup_{i=0}^\infty \{ f \in R \ | \ g^i f \in S\}\) by \(S : g^\infty\).
The problem that the authors address in this paper is as follows: Given polynomials \(g_1,\dots, g_r \in R\), let \(S= K[g_1,\dots, g_r]\) and \(0\ne g \in S\). The problem is to compute a set of generators for \(S : g^\infty\). In the first part of the paper, an algorithm has been presented to compute a set of generators for \(S : g^\infty\) which terminates if and only if it is finitely generated.
In the second part of the paper, the authors consider the case that \(S\) is graded. They show that two operations of computing a SAGBI basis for \(S\) and a set of generators for \(S : g^\infty\) commute and this leads to nice algorithms for computing with \(S : g^\infty\).On linear exactness propertieshttps://zbmath.org/1472.180022021-11-25T18:46:10.358925Z"Jacqmin, Pierre-Alain"https://zbmath.org/authors/?q=ai:jacqmin.pierre-alain"Janelidze, Zurab"https://zbmath.org/authors/?q=ai:janelidze.zurabThe authors elaborate on the conceptual framework they introduced in [\textit{P.-A. Jacqmin} and \textit{Z. Janelidze}, Adv. Math. 377, Article ID 107484, 56 p. (2021; Zbl 1452.18005)]. There, an abstract formalism was developed, based on the notion of sketch, in order to give an abstract account of exactness properties on a small finitely complete category \(\mathbb{C}\) that are preserved under pro-completion (completion under co-filtered limits, given by the embedding \( \mathbb{C} \hookrightarrow \mathrm{Lex}(\mathbb{C},\mathrm{Set})^{op}).\) Here the same formalism is used in order to obtain exactness properties in regular categories such that, when the category is algebraic, turn out to be equivalent to the existence of certain Mal'tsev terms in the corresponding algebraic theory. The main characterization theorem of the article (Theorem 3.3) asserts the equivalence of suitable exactness conditions and the existence of Mal'tsev terms and equations in the context of essentially algebraic (hence locally finitely presentable) regular categories. The theorem exploits a reformulation of those exactness conditions on a finitely cocomplete regular category in terms of a certain morphism, in the image of a left Kan extension with values in the finitely cocomplete category, being a regular epimorphism (Theorem 2.1).Complete \(\kappa\)-reducibility of pseudovarieties of the form DRHhttps://zbmath.org/1472.201232021-11-25T18:46:10.358925Z"Almeida, Jorge"https://zbmath.org/authors/?q=ai:almeida.jorge"Borlido, Célia"https://zbmath.org/authors/?q=ai:borlido.celiaCancellable elements of the lattice of semigroup varietieshttps://zbmath.org/1472.201252021-11-25T18:46:10.358925Z"Gusev, Sergey V."https://zbmath.org/authors/?q=ai:gusev.sergei-valentinovich"Skokov, Dmitry V."https://zbmath.org/authors/?q=ai:skokov.dmitrii-vyacheslavovich"Vernikov, Boris M."https://zbmath.org/authors/?q=ai:vernikov.boris-munevichSummary: We completely determine all commutative semigroup varieties that are cancellable elements of the lattice \textbf{SEM} of all semigroup varieties. In particular, we verify that a commutative semigroup variety is a cancellable element of the lattice \textbf{SEM} if and only if it is a modular element of this lattice.Transitive hyperidentity in semigroupshttps://zbmath.org/1472.201262021-11-25T18:46:10.358925Z"Hakobyan, T. A."https://zbmath.org/authors/?q=ai:hakobyan.tigran-lSummary: In this paper we characterize all semigroups in which the hyperidentity of transitivity \(X(X(x;y);X(y; z)) = X(x; z)\) is polynomially satisfied. In particular, we show that every transitive semigroup (that is a semigroup with the identity
\(xy^2z = xz\)) is also hypertransitive.On singleton kernel classes in the lattice of varieties of completely regular semigroupshttps://zbmath.org/1472.201272021-11-25T18:46:10.358925Z"Kad'ourek, Jiří"https://zbmath.org/authors/?q=ai:kadourek.jiriLee monoid \(L_4^1\) is non-finitely basedhttps://zbmath.org/1472.201282021-11-25T18:46:10.358925Z"Mikhailova, Inna A."https://zbmath.org/authors/?q=ai:mikhailova.inna-a"Sapir, Olga B."https://zbmath.org/authors/?q=ai:sapir.olga-bSummary: We establish a new sufficient condition under which a monoid is non-finitely based and apply this condition to show that the 9-element monoid \(L_4^1\) is non-finitely based. The monoid \(L_4^1\) was the only unsolved case in the finite basis problem for Lee monoids \(L_\ell ^1\), obtained by adjoining an identity element to the semigroup \(L_\ell \) generated by two idempotents \(a\) and \(b\) subjected to the relation \(0=abab \cdots \) (length \(\ell \)). We also prove a syntactic sufficient condition which is equivalent to the sufficient condition of Lee under which a semigroup is non-finitely based. This gives a new proof to the results of \textit{W. T. Zhang} and \textit{Y. F. Luo} [Bull. Aust. Math. Soc. 84, No. 3, 484--491 (2011; Zbl 1243.20072)] and \textit{E. W. H. Lee} [Houston J. Math. 44, No. 2, 399--411 (2018; Zbl 06938802); Algebra Univers. 78, No. 2, 131--145 (2017; Zbl 1373.20071)] that the semigroup \(L_\ell \) is non-finitely based for each \(\ell \geq 3\).Effectiveness of structural restrictions for hybrid CSPshttps://zbmath.org/1472.680692021-11-25T18:46:10.358925Z"Kolmogorov, Vladimir"https://zbmath.org/authors/?q=ai:kolmogorov.vladimir"Rolínek, Michal"https://zbmath.org/authors/?q=ai:rolinek.michal"Takhanov, Rustem"https://zbmath.org/authors/?q=ai:takhanov.rustemSummary: Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism \({\mathbf {R}\rightarrow \boldsymbol{\Gamma}}\) between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the \textit{fixed template CSPs} where the right side \(\boldsymbol{\Gamma}\) is fixed and the left side \(\mathbf {R}\) is unconstrained.
Far fewer results are known for the \textit{hybrid} setting that restricts both sides simultaneously. It assumes that \(\mathbf {R}\) belongs to a certain class of relational structures (called a \textit{structural restriction} in this paper). We study which structural restrictions are \textit{effective}, i.e. there exists a fixed template \(\boldsymbol{\Gamma}\) (from a certain class of languages) for which the problem is tractable when \(\mathbf {R}\) is restricted, and NP-hard otherwise. We provide
a characterization for structural restrictions that are \textit{closed under inverse homomorphisms}. The criterion is based on the \textit{chromatic number} of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph.
As our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a ``lifted language''. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs.
For the entire collection see [Zbl 1326.68015].