Equations over Finite Monoids with Infinite Promises
ACM Transactions on Computational Logic · 31.07.2026 · 27 (3) · 1-23
DOI: 10.1145/3816149 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 19.06.2026. Verfasst von Alberto Larrauri und 2 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: UKRI.
Abstract (Originalsprache)
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.
Förderung
- UKRI
Zitieren
APA
Larrauri, A., Mottet, A., & Živný, S. (2026). Equations over Finite Monoids with Infinite Promises. ACM Transactions on Computational Logic, 27(3), 1-23. https://doi.org/10.1145/3816149
Vancouver
Larrauri A, Mottet A, Živný S. Equations over Finite Monoids with Infinite Promises. ACM Transactions on Computational Logic. 2026;27(3):1-23. doi:10.1145/3816149
BibTeX
@article{Larrauri2026,
author = {Larrauri, Alberto and Mottet, Antoine and Živný, Stanislav},
title = {Equations over Finite Monoids with Infinite Promises},
journal = {ACM Transactions on Computational Logic},
year = {2026},
volume = {27},
number = {3},
pages = {1--23},
doi = {10.1145/3816149}
}
EUVIMED