Options
Equations over finite monoids with infinite promises
Citation Link: https://doi.org/10.15480/882.17377
Publikationstyp
Journal Article
Date Issued
2026-06-19
Sprache
English
TORE-DOI
Volume
27
Issue
3
Article Number
19
Citation
ACM Transactions on Computational Logic 27 (3): 19 (2026)
Publisher DOI
Publisher
Association for Computing Machinery (ACM)
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.
Subjects
constraint satisfaction
promise constraint satisfaction
equations
minions
monoids
DDC Class
519: Applied Mathematics, Probabilities
Publication version
publishedVersion
Loading...
Name
38161498(1).pdf
Type
Main Article
Size
1.27 MB
Format
Adobe PDF