Journal article
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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 493.7KB, Terms of use)
-
- Publisher copy:
- 10.1145/3816149
Authors
+ UK Research and Innovation
More from this funder
- Funder identifier:
- https://ror.org/001aqnf71
- Grant:
- EP/X024431/1
- Publisher:
- Association for Computing Machinery (ACM)
- Journal:
- ACM Transactions on Computational Logic More from this journal
- Publication date:
- 2026-05-21
- Acceptance date:
- 2026-04-30
- DOI:
- EISSN:
-
1557-945X
- ISSN:
-
1529-3785
- Language:
-
English
- Keywords:
- Pubs id:
-
2412980
- Local pid:
-
pubs:2412980
- Deposit date:
-
2026-04-30
- ARK identifier:
Terms of use
- Copyright holder:
- Larrauri et al.
- Copyright date:
- 2026
- Rights statement:
- © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM.
- Notes:
- The author accepted manuscript (AAM) of this paper has been made available under the University of Oxford's Open Access Publications Policy, and a CC BY public copyright licence has been applied.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record