pipette
ESEspañol

Testing epimorphism onto the bicyclic monoid is -complete

Luka Carroll, Murray Elder

Preprint

In the authors' words

We prove that deciding whether there is a surjective homomorphism from an arbitrary finitely presented inverse monoid onto the bicyclic monoid is -complete. As part of the proof, we show that an extension of existential Presburger arithmetic which involves greatest common divisors on arguments is in , extending a recent result of D\'efossez, Haase, Mansutti, and P\'erez (SODA 2024).

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 17 pages, 1 figure