On groups whose word problem is solved by a counter automaton.
type: Item
instance of: scholarly article
title: On groups whose word problem is solved by a counter automaton.
zbMATH Open document ID: 1061.20029
author: Gillian Elston
author: Gretchen Ostheimer
published in: Theoretical Computer Science
publication date: 2004-08-10T00:00:00Z
review text: 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 inve…
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20E07
zbMATH DE Number: 2085504
zbMATH Keywords: counter automata
zbMATH Keywords: context-free languages
zbMATH Keywords: virtually Abelian groups
zbMATH Keywords: word problem
zbMATH Keywords: finitely presented groups
zbMATH Keywords: free monoids
zbMATH Keywords: subgroups of finite index
zbMATH Keywords: finitely generated groups
reviewed by: Vitaliĭ Roman'kov
MaRDI profile type: Publication
full work available at URL: j.tcs.2003.09.007
OpenAlex ID: W1993619792
cites work: Q4085266
cites work: Finite automata over free groups
cites work: Q4079524
cites work: Q4867134
cites work: On a subclass of context-free groups
cites work: Groups, the theory of ends, and context-free languages
cites work: The theory of ends, pushdown automata, and second-order logic
DOI: 10.1016/J.TCS.2003.09.007
description: scientific article; zbMATH DE number 2085504