Larrauri, AlbertoAlbertoLarrauriMottet, AntoineAntoineMottetŽivný, StanislavStanislavŽivný2026-06-302026-06-302026-06-19ACM Transactions on Computational Logic 27 (3): 19 (2026)https://hdl.handle.net/11420/63684Larrauri 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.en1529-378520263Association for Computing Machinery (ACM)https://creativecommons.org/licenses/by/4.0/constraint satisfactionpromise constraint satisfactionequationsminionsmonoidsNatural Sciences and Mathematics::519: Applied Mathematics, ProbabilitiesJournal Articlehttps://doi.org/10.15480/882.1737710.1145/381614910.15480/882.17377