‘Monoids presented by rewriting systems and automatic structures for their submonoids’
International Journal of Algebra and Computation, 19, no. 6 (2009), pp. 771–790.
DOI: 10.1142/s0218196709005317. MR: 2572874. ZBL: 1201.20054.

Abstract

This paper studies $rr$-, $lr$-, $rl$-, and $ll$-automatic structures for finitely generated submonoids of monoids presented by confluent rewriting system that are either finite and special or regular and monadic. A new technique is developed that uses an automaton to ‘translate’ between words in the original rewriting system and words over the generators for the submonoid. This is applied to show that the submonoid inherits any notion of automatism possessed by the original monoid. Generalizations of results of Otto & Ruškuc are thus obtained: every finitely generated submonoid of a monoid presented by a confluent finite special rewriting system admits an automatic structure that is simultaneously $rr$-, $lr$-, $rl$-, and $ll$-automatic; and every finitely generated submonoid of a monoid presented by a confluent regular monadic rewriting system admits an automatic structure that is simultaneously $rr$- and $ll$-automatic. These structures are shown to be effectively computable. An algorithm is given to decide whether the monoid presented by a confluent monadic finite rewriting system is $lr$- or $rl$-automatic. Finally, these results are applied to yield answers to some hitherto open questions and to recover and generalize established results.