The Library

Groups and semigroups with a one-counter word problem

Tools

Holt, Derek F., Owens, Matthew D. and Thomas, R. M.. (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

Dates:

Date	Event
October 2008	Published

Volume:

Vol.85

Number:

No.2

Number of Pages:

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.