On groups whose word problem is solved by a counter automaton. (Q596085)

Let \(H\) be a group given by a finite presentation \(\langle X \mid R\rangle\), and let \(W(H)\) be the word problem for \(H\). That is, let \(W(H)\) be the set of words in the free monoid \((X\cup X^{-1})^*\) that represent the identity element in \(H\). It is a well known that \(W(H)\) is a regular language if and only if \(H\) is finite. Muller and Schupp proved that \(W(H)\) is a context-free language if and only if \(H\) has a free subgroup of finite index. Let \(G\) be a group. A \(G\)-automaton \(A_G\) over a finite set \(X\) is a finite directed graph with distinguished initial vertex (state), some distinguished terminal vertices, and with edges labelled by \(G\times(X^\pm)^*\). In particular, a \(\mathbb{Z}^k\)-automaton is called a counter automaton, and a \(\mathbb{Z}\)-automaton is a one-counter automaton. A \(G\)-automaton over \(X\) is said to accept a word \(w\in(X^\pm)^*\) if there is a path \(p\) from the initial state to some terminal state such that \(w(p)=w\), and \(g(p)=1\), where \(w(p)\) is the product of all second coordinates of labels of edges, and \(g(p)\) is the product of all first ones, appearing in \(p\). It is proved that the set \(W(H)\) for a finitely generated group \(H\) is accepted by a deterministic \(G\)-automaton with the inverse property if and only if the group \(H\) has a finite index subgroup \(K\) such that \(K\) is isomorphic to a subgroup of \(G\). The inverse property is a weakened version of the assumption that for each edge from \(\sigma\) to \(\tau\) labeled by \(x\) there is a corresponding edge from \(\tau\) to \(\sigma\) labeled by \(x^{-1}\). It follows that in the case of the counter \(G\)-automaton for \(W(H)\) the finitely generated group \(H\) should be virtually-free Abelian. Combining the results by the authors and Muller and Schupp we get the following corollary: Let \(H\) be a finitely generated group, \(W(H)\) is context-free if and only if there is a deterministic \(G\)-automaton \(A_G\) with the inverse property and \(G\) free such that \(A_G\) accepts \(W(H)\).