Equations over Finite Monoids with Infinite Promises
Abstract
Larrauri and Živný [ICALP’24/ACM ToCL’24] recently established a complete complexity classification of the problem of solving a system of equations over a monoid \({N}\) assuming that a solution exists over a monoid \({M}\) , where both monoids are finite and \({M}\) admits a homomorphism to \({N}\) . Using the algebraic approach to promise constraint satisfaction problems, we extend their complexity classification in two directions: we obtain a complexity dichotomy in the case where arbitrary relations are added to the monoids, and we moreover allow the monoid \({M}\) to be finitely generated.
Fields of Study & Subjects
Rings
Modules
and Algebras
semigroups and automata theory
Advanced Algebra and Logic
Publication details
- Journal / source
- ACM Transactions on Computational Logic
- Volume
- 27
- Issue
- 3
- Pages
- 1–23
- Publication date
- 21 May 2026
- Language
- EN