WoG 2026 Talk 1.2: Luka Carrol - The complexity of the epimorphism problem for the bicyclic monoid

Speaker: Luka Carrol Institution: University of Technology Sydney Title: The complexity of the epimorphism problem for the bicyclic monoid Abstract: The bicyclic monoid (or bicyclic semigroup) $\mathcal{B}$ is the infinite monoid on two generators $a,b$ subject only to the relation $ab=1$. The monoid $\mathcal{B}$ is a fundamental algebraic structure that has found numerous applications in algebra, combinatorics, and theoretical computer science. The monoid $\mathcal{B}$ is an inverse monoid; that is, $\mathcal{B}$ is a monoid in which every $x\in\mathcal{B}$ has a unique generalised inverse $x^{-1}\in\mathcal{B}$, meaning $x^{-1}$ satisfies only the identities $xx^{-1}x=x$ and $x^{-1}xx^{-1}=x^{-1}$ rather than the stronger identity $xx^{-1}=x^{-1}x=1$ satisfied by group inverses. In this talk we consider the computational complexity of the epimorphism problem for the bicyclic monoid. This is the problem of deciding if there exists a surjective homomorphism from an arbitrary, finitely presented inverse monoid $\mathcal{M}$ onto the bicyclic monoid (or, equivalently, if $\mathcal{M}$ has a quotient that is isomorphic to $\mathcal{B}$). We analyse this problem via a reduction to Presburger arithmetic, the first-order theory of linear arithmetic over the integers. Through this analysis we gain new insights into the complexity of an extension of Presburger arithmetic. This is joint work with Murray Elder.