On groups whose word problem is solved by a counter automaton. (English) Zbl 1061.20029
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)\).
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)\).
Reviewer: V. A. Roman’kov (Omsk)
MSC:
20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
68Q45 | Formal languages and automata |
20F05 | Generators, relations, and presentations of groups |
20M05 | Free semigroups, generators and relations, word problems |
20E07 | Subgroup theorems; subgroup growth |
Keywords:
counter automata; context-free languages; virtually Abelian groups; word problem; finitely presented groups; free monoids; subgroups of finite index; finitely generated groupsReferences:
[1] | Anisimov, A.; Seifert, F., Zur algebraischen charateristik der durch kontextfreie sprachen definierten gruppen, Elektronische Informationsverarbeitung und Kybernetik, 11, 675-702 (1975) · Zbl 0322.68047 |
[2] | Dassow, J.; Mitrana, V., Finite automata over free groups, IJAC, 10, 6, 725-737 (2000) · Zbl 0969.68093 |
[3] | Eilenberg, S., Automata, Languages and Machines (1974), Academic Press: Academic Press New York · Zbl 0317.94045 |
[4] | R.H. Gilman, Formal languages and infinite groups, in: G.B. et al. (Eds.), Geometric and Computational Perspectives on Infinite Groups, DIMACS Series in Discrete Mathematics and Computer Science, Vol. 25, American Mathematical Society, Providence, RI, 1996, pp. 27-51.; R.H. Gilman, Formal languages and infinite groups, in: G.B. et al. (Eds.), Geometric and Computational Perspectives on Infinite Groups, DIMACS Series in Discrete Mathematics and Computer Science, Vol. 25, American Mathematical Society, Providence, RI, 1996, pp. 27-51. · Zbl 0851.20030 |
[5] | Herbst, T., On subclass of context-free groups, Theoret. Informatics Appl., 25, 255-272 (1991) · Zbl 0751.68040 |
[6] | Muller, D.; Schupp, P., Groups, the theory of ends and context-free languages, J. Comput. System Sci., 26, 295-310 (1983) · Zbl 0537.20011 |
[7] | Muller, D.; Schupp, P., The theory of ends, pushdown automata, and second order logic, Theoret. Comput. Sci., 37, 51-75 (1985) · Zbl 0605.03005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.