No Access
ON GROUPS AND COUNTER AUTOMATA
https://doi.org/10.1142/S0218196708004901Cited by:15 (Source: Crossref)
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.
AMSC: 20F10, 68Q70
References
- J. Austral. Math. Soc. 18, 41 (1974). Crossref, Web of Science, Google Scholar
- H.-R. Cho, An introduction to counter groups, Ph.D. thesis, Stevens Institute of Technology (2006) . Google Scholar
N. Chomsky and M. P. Schützenberger , Computer Programming and Formal Systems (North-Holland, Amsterdam, 1963) pp. 118–161. Crossref, Google Scholar- S. Cleary, M. Elder and G. Ostheimer, The word problem distinguishes counter languages, (2006) , arXiv:math.GR/0606415 . Google Scholar
- Int. J. Algebra Comput. 15(3), 455 (2005), DOI: 10.1142/S0218196705002360. Link, Web of Science, Google Scholar
-
J. D. Dixon , The Structure of Linear Groups ( Van Nostrand Reinhold , New York , 1971 ) . Google Scholar - Invent. Math. 81(3), 449 (1985), DOI: 10.1007/BF01388581. Crossref, Web of Science, Google Scholar
-
S. Eilenberg , Automata, Languages, and Machines ,Pure and Applied Mathematics 58 ( Academic Press , New York , 1974 ) . Google Scholar M. Elder , Groups St. Andrews 2005,London Mathematical Society Lecture Note Series 339 (Cambridge University Press, Cambridge, 2007) pp. 313–318. Crossref, Google Scholar- Theoret. Comput. Sci. 320(2–3), 175 (2004), DOI: 10.1016/j.tcs.2003.09.007. Crossref, Web of Science, Google Scholar
R. H. Gilman , Geometric and Computational Perspectives on Infinite Groups (Minneapolis, MN and New Brunswick, NJ, 1994),DIMACS Series in Discrete Mathematics and Theoretical Computer Science 25 (American Mathematical Society, Providence, RI, 1996) pp. 27–51. Google Scholar- R. H. Gilman and M. Shapiro, On groups whose word problem is solved by a nested stack automaton; (1998) , arXiv:math.GR/9812028 . Google Scholar
- Theoret. Comput. Sci. 1(4), 269 (1976), DOI: 10.1016/0304-3975(76)90072-4. Crossref, Google Scholar
- Theoret. Comput. Sci. 7(3), 311 (1978), DOI: 10.1016/0304-3975(78)90020-8. Crossref, Google Scholar
- Inst. Hautes Études Sci. Publ. Math. (53) 53 (1981), DOI: 10.1007/BF02698687. Google Scholar
- RAIRO Inform. Théor. Appl. 25(3), 255 (1991). Crossref, Web of Science, Google Scholar
- Theoret. Comput. Sci. 112(2), 187 (1993), DOI: 10.1016/0304-3975(93)90018-O. Crossref, Web of Science, Google Scholar
- Proc. Roy. Soc. Ser. A 262, 455 (1961). Crossref, Google Scholar
- J. London Math. Soc. (2) 71(3), 643 (2005), DOI: 10.1112/S002461070500654X. Crossref, Web of Science, Google Scholar
-
J. E. Hopcroft and J. D. Ullman , Formal Languages and their Relation to Automata ( Addison-Wesley , 1969 ) . Google Scholar - Commun. Algebra . Google Scholar
- Theoret. Computun. Sci. 362(1), 232 (2006), DOI: 10.1016/j.tcs.2006.06.026. Crossref, Web of Science, Google Scholar
- J. Algebra 309, 622 (2007), DOI: 10.1016/j.jalgebra.2006.05.020. Crossref, Web of Science, Google Scholar
V. Mitrana and R. Stiebe , New Trends in Formal Languages,Lecture Notes in Computer Science 1218 (Springer, Berlin, 1997) pp. 39–48. Crossref, Google Scholar- J. Comput. Syst. Sci. 26(3), 295 (1983), DOI: 10.1016/0022-0000(83)90003-X. Crossref, Web of Science, Google Scholar
- J. Assoc. Comput. Mach. 13, 570 (1966). Crossref, Web of Science, Google Scholar
-
D. J. S. Robinson , A Course in the Theory of Groups , 2nd edn. ,Graduate Texts in Mathematics 80 ( Springer-Verlag , 1996 ) . Crossref, Google Scholar -
D. Segal , Polycyclic Groups ,Cambridge Tracts in Mathematics 82 ( Cambridge University Press , New York , 1983 ) . Crossref, Google Scholar - Ann. Math. (2) 88, 312 (1968), DOI: 10.2307/1970577. Crossref, Web of Science, Google Scholar
- Arch. Math. (Basel) 42(5), 391 (1984). Crossref, Web of Science, Google Scholar
