Combings of groups and the grammar of reparameterization. (Q1422174)

A choice of generating set for a given group \(G\) is a surjective monoid homomorphism \(\mu\colon\Sigma^*\to G\) where \(\Sigma^*\) denotes the free monoid over the finite set \(\Sigma\). A `combing' of \(G\) is a map \(\sigma\colon G\to\Sigma^*\) satisfying \(\mu\circ\sigma(g)=g\) for all \(g\in G\). The image of \(\sigma\) is also referred to as the language of words in the combing. For a full abstract family of languages \(\mathcal A\), \(\sigma\) is an `\(\mathcal A\)-combing' if it satisfies the so-called `fellow-traveller property' and the image of \(\sigma\) is a language in the class \(\mathcal A\). If such a \(\sigma\) exists, \(G\) is called `\(\mathcal A\)-combable'. The `regular' (Reg), `context-free' (CF), and `indexed' (Ind) classes of languages form the increasing hierarchy \(\text{Reg}\subset\text{CF}\subset\text{Ind}\). These classes are known to be generated by corresponding types of `grammars'. In the special case where \({\mathcal A}=\text{Reg}\), an \(\mathcal A\)-combing is called an `automatic structure' for \(G\). In this paper, the author introduces a new method for constructing combings of groups. This new construction is used to answer questions that were raised concerning the distinguishability of several classes of groups. In particular, this new construction of combings provides examples of Ind-combable groups that are not Reg-combable. The author also analyses the grammatical complexity of the combings constructed with his new method. In many cases, the language of words in the combing turns out to be a language in the class Ind.