2026-07-25T10:16:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19755 2024-03-11T06:37:05Z ddc:004 open_access

Circuit Equivalence in 2-Nilpotent Algebras Kawałek, Piotr Kompatscher, Michael Krzaczkowski, Jacek circuit equivalence identity checking nilpotent algebra The circuit equivalence problem Ceqv(A) of a finite algebra A is the problem of deciding whether two circuits over A compute the same function or not. This problem not only generalises the equivalence problem for Boolean circuits, but is also of interest in universal algebra, as it models the problem of checking identities in A. In this paper we prove that Ceqv(A) ∈ 𝖯, if A is a finite 2-nilpotent algebra from a congruence modular variety. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Piotr Kawałek and Michael Kompatscher and Jacek Krzaczkowski 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.45 urn:nbn:de:0030-drops-197554 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.45 eng https://creativecommons.org/licenses/by/4.0/legalcode