Proving that a semigroup is regular In a number of diverse situations of interest to me (mostly associated with something called the abelian sandpile model), one can define a nonabelian semigroup generated by commuting elements $a_1,\dots,a_n$ and commuting elements $b_1,\dots,b_n$ such that for all $i$, $a_i$ and $b_i$ do not commute but are semigroup inverses, aka quasi-inverses (i.e., $a_ib_ia_i=a_i$ and $b_ia_ib_i=b_i$).  I'd like to know more about the structure of the semigroup. In particular, I'd like to know that for every sequence $i_1, \dots, i_r$ with terms in ${1,\dots,n}$, the products $a_{i_1} \dots a_{i_r}$ and $b_{i_1} \dots b_{i_r}$ are semigroup inverses. Are there standard theorems or methods in semigroup theory that would help me? I should mention that for my applications, the elements $a_i$ and $b_i$ are not inverses in the group sense, even though the semigroup is unital; that is, there is an identity element $e$, but we do not have $a_i b_i = e$ or $b_i a_i = e$. 
[In the original version of the question I wrote "$b_i=Ua_iU$ ($1 \leq i \leq n$) for some fixed involution $U$" but then Boris Novikov's question made me realize that for the applications of interest to me $U$ belongs to a larger semigroup, so it seemed best to omit $U$ from the statement of the problem for the time being. I also did not state explicitly that the semigroup is nonabelian.]
There is an extant notion of "sandpile semigroups", but I'm pretty sure that the semigroup I'm interested (introduced by Andrea Sportiello and his coworkers) is something different.
See http://jamespropp.org/pseudo.pdf for a (slightly out-of-date) one-page blurb about the questions that motivated the post, concerning the sandpile model, rotor-router model, and divisible sandpile model. I'm hoping that basic theorems from the theory of semigroups will provide a uniform approach to proving regularity of semigroups in all three contexts.
 A: If your monoid is defined in terms of generators and relations, a simple tool you can use to check whether elements have quasi-inverses of the specified form is Bergman's diamond lemma.  For instance, if your monoid is given the presentation $\langle a,b\ :\ aba=a,bab=b \rangle$ you can quickly check that the two relations give a "reduction system".  The element $a^2$ does not have a quasi-inverse because if $m$ is any monomial on the letters $a,b$, then just compute the reduced form of $a^2ma^2$ (which must contain at least three instances of $a$).  It is even easier to check that $a^2b^2a^2$ is already in reduced form, so $b^2$ is not a quasi-inverse to $a^2$.
Thus, taking $a_1=a_2=a$ and $b_1=b_2=b$, you have your desired counter-example.  With more complicated relations, it may take a little more work but you should be able to rule out (von Neumann) regularity in many cases.
A: As I mentioned in an earlier note, the post is actually asking two different questions (and confusing them with each other).
If the intended question is "How can I go about proving regularity of semigroups like this?", the best answer now seems likely to be "Semigroups like this usually aren't regular."  But this isn't as dispiriting a state of affairs as I originally thought, since I now understand (thanks to the example of the biHecke monoid) that non-regular semigroups can still have lots of regularities (in the broad sense) that make them amenable to analysis; and for that matter, regular semigroups aren't necessarily that nice.
If the intended question is the narrower one that I originally asked, about the existence of quasi-inverses of special elements of the form $a_{i_1} a_{i_2} \dots$, then there is cause for hope.  However, I am not yet aware of any algebraic "magic bullet" that would somehow bring all the monoids I'm interested in under one roof and do all the heavy lifting. (Sorry for the colliding cliches in that last sentence!)
