EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Equations over Finite Monoids with Infinite Promises

Alberto Larrauri, Antoine Mottet, Stanislav Živný

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →