The Library

Groups and semigroups with a one-counter word problem

Tools

Holt, Derek F., Owens, Matthew D. and Thomas, R. M. (Richard Monro), 1952-. (2008) Groups and semigroups with a one-counter word problem. Journal of the Australian Mathematical Society, Vol.85 (No.2). pp. 197-209. ISSN 1446-7887

Preview

PDF
WRAP_Holt_Group_semigroups.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (171Kb)

Official URL: http://dx.doi.org/10.1017/S1446788708000864

Abstract

We prove that a finitely generated semigroup whose word problem is a one-counter language has a linear growth function. This provides us with a very strong restriction on the structure of such a semigroup, which, in particular, yields an elementary proof of a result of Herbst, that a group with a one-counter word problem is virtually cyclic. We prove also that the word problem of a group is an intersection of finitely many one-counter languages if and only if the group is virtually abelian.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Word problems (Mathematics), Semigroup, Finite groups, Abelian groups, Group theory
Journal or Publication Title:	Journal of the Australian Mathematical Society
Publisher:	Cambridge University Press
ISSN:	1446-7887
Official Date:	October 2008
Volume:	Vol.85
Number:	No.2
Number of Pages:	13
Page Range:	pp. 197-209
Identification Number:	10.1017/S1446788708000864
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
References:	[1] Anisimov, A. V., ‘Certain algorithmic problems for groups and context-free languages’, Kibernetica 2 (1972), 4–11. [2] Berstel, Jean, Transductions and Context-Free Languages (Teubner, Stuttgart, 1979). [3] Duncan, Andrew and Gilman, Robert H., ‘Word hyperbolic semigroups’, Math. Proc. Cambridge Philos. Soc. 136 (2004), 513–524. [4] Dunwoody, M. J., ‘The accessibility of finitely presented groups’, Invent. Math. 81 (1985), 449–457. [5] Elder, Murray, Kambites, Mark and Ostheimer, Gretchen, On groups and counter automata, arXiv:math/0611188v1, 7 Nov 2006. [6] Epstein, David B. A., Cannon, J. W., Holt, D. F., Levy, S., Paterson, M. S. and Thurston, W. P., Word Processing in Groups (Jones and Bartlett, Boston, MA, 1992). [7] Gromov, Mikhael, ‘Groups of polynomial growth and expanding maps’, Publ. Math. Inst. Hautes Études Sci. 53 (1981), 53–78. [8] Herbst, Thomas, ‘On a subclass of context-free groups’, RAIRO Inform. Théor. Appl. 25 (1991), 255–272. [9] Herbst, Thomas and Thomas, Richard M., ‘Group presentations, formal languages and characterizations of one-counter groups’, Theoret. Comput. Sci. 112 (1993), 187–213. [10] Holt, Derek F., Röver, Claas E., Rees, Sarah and Thomas, Richard M., ‘Groups with a context-free co-word problem’, J. London Math. Soc. 71 (2005), 643–657. [11] Justin, J., ‘Groupes et semi-groupes à croissance linéaire’, C. R. Acad. Sci. Paris Sér. A–B 273 (1971), 212–214. [12] Muller, David E. and Schupp, Paul E., ‘Groups, the theory of ends, and context-free languages’, J. Comput. System Sci. 26 (1983), 295–310. [13] Neumann, B. H., ‘Groups covered by permutable subsets’, J. London Math. Soc. 29 (1954), 236–248. [14] Parikh, Rohit J., ‘Language-generating devices’, Quarterly Research Reports, 60, Research Laboratory of Electronics, MIT, Cambridge, MA, 1961, pp. 199–212. [15] Stallings, John, Group Theory and Three-Dimensional Manifolds, Yale Mathematical Monographs, 4 (Yale University Press, New Haven, CT and London, 1971). [16] Wilkie, A. J. and van den Dries, L., ‘An effective bound for groups of linear growth’, Arch. Math. (Basel) 42 (1984), 391–396.
URI:	http://wrap.warwick.ac.uk/id/eprint/861