Recent zbMATH articles in MSC 08Ahttps://www.zbmath.org/atom/cc/08A2021-11-25T18:46:10.358925ZWerkzeugOn a product of universal relational systemshttps://www.zbmath.org/1472.080012021-11-25T18:46:10.358925Z"Phrommarat, Nitima"https://www.zbmath.org/authors/?q=ai:phrommarat.nitima"Sudsanit, Sivaree"https://www.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://www.zbmath.org/1472.080022021-11-25T18:46:10.358925Z"Kumduang, Thodsaporn"https://www.zbmath.org/authors/?q=ai:kumduang.thodsaporn"Leeratanavalee, Sorasak"https://www.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://www.zbmath.org/1472.080032021-11-25T18:46:10.358925Z"Kunama, Pornpimol"https://www.zbmath.org/authors/?q=ai:kunama.pornpimol"Leeratanavalee, Sorasak"https://www.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://www.zbmath.org/1472.080042021-11-25T18:46:10.358925Z"Vaggione, Diego J."https://www.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://www.zbmath.org/1472.080052021-11-25T18:46:10.358925Z"Yashunsky, Alexey D."https://www.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://www.zbmath.org/1472.080062021-11-25T18:46:10.358925Z"Bodirsky, Manuel"https://www.zbmath.org/authors/?q=ai:bodirsky.manuel"Mottet, Antoine"https://www.zbmath.org/authors/?q=ai:mottet.antoine"Olšák, Miroslav"https://www.zbmath.org/authors/?q=ai:olsak.miroslav"Opršal, Jakub"https://www.zbmath.org/authors/?q=ai:oprsal.jakub"Pinsker, Michael"https://www.zbmath.org/authors/?q=ai:pinsker.michael"Willard, Ross"https://www.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.Variations of the shifting lemma and Goursat categorieshttps://www.zbmath.org/1472.080092021-11-25T18:46:10.358925Z"Gran, Marino"https://www.zbmath.org/authors/?q=ai:gran.marino"Rodelo, Diana"https://www.zbmath.org/authors/?q=ai:rodelo.diana"Nguefeu, Idriss Tchoffo"https://www.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://www.zbmath.org/1472.080102021-11-25T18:46:10.358925Z"Johansen, Sarah M."https://www.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://www.zbmath.org/1472.130442021-11-25T18:46:10.358925Z"Bigatti, Anna Maria"https://www.zbmath.org/authors/?q=ai:bigatti.anna-maria"Robbiano, Lorenzo"https://www.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://www.zbmath.org/1472.180022021-11-25T18:46:10.358925Z"Jacqmin, Pierre-Alain"https://www.zbmath.org/authors/?q=ai:jacqmin.pierre-alain"Janelidze, Zurab"https://www.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).Transitive hyperidentity in semigroupshttps://www.zbmath.org/1472.201262021-11-25T18:46:10.358925Z"Hakobyan, T. A."https://www.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.Effectiveness of structural restrictions for hybrid CSPshttps://www.zbmath.org/1472.680692021-11-25T18:46:10.358925Z"Kolmogorov, Vladimir"https://www.zbmath.org/authors/?q=ai:kolmogorov.vladimir"Rolínek, Michal"https://www.zbmath.org/authors/?q=ai:rolinek.michal"Takhanov, Rustem"https://www.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].