Testing epimorphism onto the bicyclic monoid is -complete
En palabras de los autores
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).
Resultado principalEl resumen no menciona limitaciones.
Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 17 pages, 1 figure