Automatic Structures for Coxeter Groups

Abstract

In this thesis, we study automatic structures recognising the language of reduced words for Coxeter groups. In particular, we focus on conditions for minimality for these automata. We give a classification of the Coxeter systems (W,S) for which the Brink-Howlett automaton is minimal in terms of excluded sub-graphs of the Coxeter graph ΓW , thereby resolving a conjecture of Hohlweg, Nadeau and Williams. We study the minimal automaton for W by studying the Cannon cone types of W. We investigate their basic properties and the partition of W induced by its cone types. Notably, a characterisation of cone types in terms of a minimal set of roots is given. Furthermore, it is proven that for every cone type of W, there is a unique representative of minimal length, which is a suffix of every element with the same cone type. We progress towards proving that the set of minimal length cone type representatives is a Garside shadow; which would prove that the automaton built from the smallest Garside shadow is minimal (also a conjecture of Hohlweg, Nadeau and Williams). We prove this for certain classes of Coxeter groups and initiate an approach to prove this in general.