Nonuniform deterministic finite automata over finite algebraic structures

DOI10.4230/LIPICS.ICALP.2025.161MaRDI QIDQ7397622zbMATH OpenFDO

Authors Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.161

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A degree-decreasing lemma for \((\text{MOD}_q - \text{MOD}_p)\) circuits
• A dichotomy theorem for nonuniform CSPs
• A proof of the CSP dichotomy conjecture
• Algebras from congruences
• Circuit equivalence in 2-nilpotent algebras
• Complexity of modular circuits
• Equation satisfiability in solvable groups
• Equivalence and equation solvability problems for the alternating group A₄.
• Even Faster Algorithms for CSAT Over supernilpotent Algebras.
• Hardness of equations over finite solvable groups under the exponential time hypothesis
• scientific article; zbMATH DE number 4035895 (Why is no real title available?)
• scientific article; zbMATH DE number 1759404 (Why is no real title available?)
• Intermediate problems in modular circuits satisfiability
• Lower Bounds for (MOD_p - MOD_m) Circuits
• Lower bounds for circuits with \(\mathrm{MOD}_m\) gates
• Non-uniform automata over groups
• On the number of finite Mal'tsev algebras
• Representing Boolean functions as polynomials modulo composite numbers
• Results on the equivalence problem for finite groups.
• Satisfiability in MultiValued Circuits
• Satisfiability of circuits and equations over finite malcev algebras
• Satisfiability problems for finite groups
• Some applications of higher commutators in Mal'cev algebras
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• The complexity of solving equations over finite groups
• The complexity of the equation solvability and equivalence problems over finite groups
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• The equation solvability problem over supernilpotent algebras with Mal’cev term
• The structure of finite algebras
• Violating constant degree hypothesis requires breaking symmetry

This page was built for publication: Nonuniform deterministic finite automata over finite algebraic structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7397622)