ON GROUPS AND COUNTER AUTOMATA
Authors:
- 1 December 2008
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Algebra and Computation
- Vol. 18 (08) , 1345-1364
Abstract
We study finitely generated groups whose word problems are accepted by counter automata. We show that a group has word problem accepted by a blind n-counter automaton in the sense of Greibach if and only if it is virtually free abelian of rank n; this result, which answers a question of Gilman, is in a very precise sense an abelian analogue of the Muller–Schupp theorem. More generally, if G is a virtually abelian group then every group with word problem recognized by a G-automaton is virtually abelian with growth class bounded above by the growth class of G. We consider also other types of counter automata.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- G-automata, counter languages and the Chomsky hierarchy2007
- EXTENDED FINITE AUTOMATA AND WORD PROBLEMSInternational Journal of Algebra and Computation, 2005
- On groups whose word problem is solved by a~counter automatonTheoretical Computer Science, 2004
- Group presentations, formal languages and characterizations of one-counter groupsTheoretical Computer Science, 1993
- The accessibility of finitely presented groupsInventiones Mathematicae, 1985
- Remarks on blind and partially blind one-way multicounter machinesTheoretical Computer Science, 1978
- Remarks on the complexity of nondeterministic counter languagesTheoretical Computer Science, 1976
- An algebraic characterization of groups with soluble word problemJournal of the Australian Mathematical Society, 1974
- The Algebraic Theory of Context-Free Languages1963
- Subgroups of finitely presented groupsProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1961