Confluent Monadic String-Rewriting Systems and Automatic Structures
Friedrich Otto, Nik Ruškuc · 2001
If a monoid $M$ is presented through a finite, special, and confluent string-rewriting system, then the set of irreducible strings is part of an automatic structure for $M$ that is simultaneously $\ell\ell$-, $\ell r$-, $r\ell$-, and $rr$-automatic. However, if the presentation is regular instead of finite or monadic instead of special, then the resulting automatic structure is in general only $\ell\ell$- and $rr$-automatic.