1 Search Results for "Grünbacher, Simon"


Document
The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term

Authors: Erhard Aichinger and Simon Grünbacher

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)


Abstract
We consider finite algebraic structures and ask whether every solution of a given system of equations satisfies some other equation. This can be formulated as checking the validity of certain first order formulae called quasi-identities. Checking the validity of quasi-identities is closely linked to solving systems of equations. For systems of equations over finite algebras with finitely many fundamental operations, a complete P/NPC dichotomy is known, while the situation appears to be more complicated for single equations. The complexity of checking the validity of a quasi-identity lies between the complexity of term equivalence (checking whether two terms induce the same function) and the complexity of solving systems of polynomial equations. 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 P when the algebra is abelian.

Cite as

Erhard Aichinger and Simon Grünbacher. The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{aichinger_et_al:LIPIcs.STACS.2023.4,
  author =	{Aichinger, Erhard and Gr\"{u}nbacher, Simon},
  title =	{{The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.4},
  URN =		{urn:nbn:de:0030-drops-176560},
  doi =		{10.4230/LIPIcs.STACS.2023.4},
  annote =	{Keywords: quasi-identities, conditional identities, systems of equations}
}
  • Refine by Author
  • 1 Aichinger, Erhard
  • 1 Grünbacher, Simon

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Complexity classes

  • Refine by Keyword
  • 1 conditional identities
  • 1 quasi-identities
  • 1 systems of equations

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail