On the definition of word hyperbolic groups. (Q1433428)

Let \(G\) be a finitely generated group, \(\Sigma\) be a finite alphabet, \(\#\) a letter not in \(\Sigma\), \(\Sigma_\#=\Sigma\cup\{\#\}\), and \(\Sigma^*\) be the free monoid over \(\Sigma\). In addition \(\Sigma_\varepsilon=\Sigma\cup\{\varepsilon\}\subset \Sigma^*\) where \(\varepsilon\) stands for the empty word. The alphabet \(\Sigma\) has formal inverses if it admits a permutation \(a\to a^{-1}\) with orbits of length two. Formal inverses on \(\Sigma\) extend to formal inverses on \(\Sigma^*\) by means of the rule \((wv)^{-1}=v^{-1}w^{-1}\). A formal language is a subset of a free monoid \(\Sigma^*\) over a finite alphabet \(\Sigma\). The connection between a group \(G\) and languages over \(\Sigma\) is made by means of a surjective monoid homomorphism \(\Sigma^*\to G\) which maps \(w\in\Sigma^*\) to \(\overline w\in G\). A choice of generators for \(G\) consists of a finite alphabet \(\Sigma\) equipped with formal inverses together with a surjective monoid homomorphism \(\Sigma^*\to G\) which maps \(w^{-1}\) to \(\overline w^{-1}\). Any choice of generators \(\Sigma^*\to G\) is extended to \(\Sigma_\#^*\to G\) via \(\overline\#=1\). The main results of the paper under review are the following. Theorem 1. Let \(\Sigma^*\to G\) be a choice of generators for the group \(G\). \(G\) is word-hyperbolic if and only if for some regular combing \(R\subset\Sigma^*\), then the language \(M=\{u\#v\#w\mid u,v,w \in R,\;\overline{uvw}=1\}\) is context-free. For any combing \(R\), \(M=\{u\#v\#w\mid u,v,w \in R,\;\overline{uvw}=1\}\) is called the multiplication table determined by \(R\). Theorem 2 is a variation on the main result of \textit{D. E. Muller} and \textit{P. E. Schupp} [J. Comput. Syst. Sci. 26, 295-310 (1983; Zbl 0537.20011)]. Theorem 2. Let \(\Sigma^*\to G\) be a choice of generators and \(M\) the multiplication table corresponding to the combing \(R=\Sigma^*\). (1) \(G\) is finite if and only if \(M\) is a regular language. (2) \(G\) is virtually free if and only if \(M\) is context-free. The column of \(g\in G\) is \(C(g)=\{u\#w\mid u,w\in R,\;\overline ug\overline w=1\}\). Columns are related to the comparator automata used in the definition of automatic groups. Suppose \(G\) is automatic with respect to the combing used to define \(M\), and \(a\in\Sigma_\varepsilon\). The binary relation accepted by the comparator automaton for \(a\) is \(\{(u,w)\mid u,w\in R,\;\overline ua=\overline w\}\) while \(C(\overline a)=\{u\#w\mid u,w \in R,\;\overline{uaw}=1\} \). Theorem 3. Let \(\Sigma^*\to G\) be a choice of generators. There exists a combing \(R\subset\Sigma^*\) such that \(C(\overline a)\) is context-free for all \(a\in \Sigma_\varepsilon\) if and only if \(G\) is asynchronously automatic with respect to a combing contained in \(\Sigma^*\) and closed under taking formal inverses.