On the automaticity of singular Artin monoids of finite type

Abstract

Automaticity is an important concept in group theory as it yields an efficient solution to the word problem and provides other possibilities for effective computation. The concept of automaticity generalizes naturally from groups to monoids and semigroups and the efficiency of the solution of the word problem is preserved when we do this. Whilst this subject has been studied extensively (in both the group and the monoid/semigroup case), there are still some deep and major open problems, including questions concerning the automaticity of certain naturally occurring classes of groups, monoids and semigroups. In this paper, we consider two such classes of monoids, namely the positive singular Artin monoids of finite type and the singular Artin monoids of the finite type. The main purpose here is to show that these monoids are all automatic. When establishing the automaticity of monoids, one obstacle is that we often have asynchronous finite automata recognizing multiplication and we need to establish the existence of synchronous machines accomplishing the same task. Building on the work of Frougny and Sakarovitch, we establish a new criterion for achieving such a transition; this is fundamental in the establishment of the automaticity of the monoids we consider here and may well apply to other naturally occurring classes of monoids and semigroups as well.

Keywords:

• automatic groups
• automatic monoids
• finite automata
• transducers
• rational relations
• normal forms
• Coxeter graphs
• positive singular Artin monoids
• singular Artin monoids

2010 AMS Subject Classifications:

• 20M05
• 68Q45
• 68Q70

Acknowledgements

This work started while the first author was the recipient of a grant from the EPSRC (UK) and continued while she was a Marie Curie Postdoctoral Researcher (EU); the support of these two funding bodies is gratefully acknowledged. The results of this paper were obtained when the third author was affiliated to the University of Leicester and, later, the Universität Leipzig. The second and fourth authors thank Chen-Hui Chiu and Hilary Craig for all their help and encouragement. We thank the referees for their careful reading of the paper and their constructive suggestions.