Checking quasi-identities and solving equations

Description

A \emph{quasi-identity} is a formula of the form \[ \forall x_1, \ldots, x_n \,:\, (s_1 (\overline{x}) \approx t_1 (\overline{x}) \wedge \cdots \wedge s_k (\overline{x}) \approx t_k (\overline{x})) \rightarrow u (\overline{x}) \approx v (\overline{x}), \] where $s_i,t_i,u,v$ are terms in the language of some algebra $\mathbf{A}$. Such a quasi-identity is valid in $\mathbf{A}$ if the solutions of $s_1 \approx t_1 \wedge \cdots \wedge s_k \approx t_k$ are a subset of the solutions of $u \approx v$. Checking the validity of a quasi-identity in a given algebra $\mathbf{A}$ is closely related to the \emph{identity checking} and \emph{equation solving} problems that have already been considered in a universal algebraic framework, for example by B.\ Larose and L.\ Z\'{a}dori. For semigroups, the computational complexity of checking the validity of a quasi-identity has been investigated by M.\ Volkov. We determine its computational complexity for finite Mal'cev algebras of finite type. This is joint research with Simon Gr\"unbacher (JKU Linz). The main result has also been presented at STACS 2023.

Period	09 Feb 2024
Event title	AAA104 - 104th Workshop on General Algebra
Event type	Conference
Location	BulgariaShow on map