The complexity of checking quasi-identities over finite algebras with a Mal'cev term

  • Simon Grünbacher (Speaker)

Activity: Talk or presentation › Contributed talk › science-to-science

Description

We prove that for each finite algebra with a Mal'cev term and finitely many fundamental operations, checking the validity of quasi-identities is $\coNP$-complete if the algebra is not abelian, and in $\PP$ when the algebra is abelian (joint work with Erhard Aichinger).
Period07 Mar 2023
Event title40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Event typeConference
LocationGermanyShow on map

Fields of science

  • 101013 Mathematical logic
  • 101001 Algebra
  • 101 Mathematics
  • 102031 Theoretical computer science
  • 101005 Computer algebra

JKU Focus areas

  • Digital Transformation

Documents & Links

Related content