2020/12/02 by Nyberg-Brodda, Carl-Fredrik
#20M05 (primary) 20F10 #20M35 #68Q45 (secondary) #FOS: Mathematics #Group Theory (math.GR)
paper · doi:10.48550/arxiv.2012.01402
We study the language-theoretic properties of the word problem, in the sense of Duncan & Gilman, of weakly compressible monoids, as defined by Adian & Oganesian. We show that if C is a reversal-closed super-AFL, as defined by Greibach, then M has word problem in C if and only if its compressed left monoid L(M) has word problem in C. As a special case, we may take C to be the class of context-free or indexed languages. As a corollary, we find many new classes of monoids with decidable rational subset membership problem. Finally, we show that it is decidable whether a one-relation monoid containing a non-trivial idempotent has context-free word problem. This answers a generalisation of a question first asked by Zhang in 1992.