Groups and simple languages
HTML articles powered by AMS MathViewer
- by Robert H. Haring-Smith PDF
- Trans. Amer. Math. Soc. 279 (1983), 337-356 Request permission
Abstract:
With any finitely generated group presentation, one can associate a formal language (called the reduced word problem) consisting of those words on the generators and their inverses which are equal to the identity but which have no proper prefix equal to the identity. We show that the reduced word problem is a simple language if and only if each vertex of the presentation’s Cayley diagram has only a finite number of simple closed paths passing through it. Furthermore, if the reduced word problem is simple, then the group is a free product of a free group of finite rank and a finite number of finite groups.References
- A. V. Anīsīmov, The group languages, Kibernetika (Kiev) 4 (1971), 18–24 (Russian, with English summary). MR 301981
- Michael A. Harrison, Introduction to formal language theory, Addison-Wesley Publishing Co., Reading, Mass., 1978. MR 526397
- David E. Muller and Paul E. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. System Sci. 26 (1983), no. 3, 295–310. MR 710250, DOI 10.1016/0022-0000(83)90003-X
- John Stallings, A remark about the description of free products of groups, Proc. Cambridge Philos. Soc. 62 (1966), 129–134. MR 188332, DOI 10.1017/s0305004100039657
Additional Information
- © Copyright 1983 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 279 (1983), 337-356
- MSC: Primary 20F10; Secondary 05C25, 20E06, 68Q45
- DOI: https://doi.org/10.1090/S0002-9947-1983-0704619-4
- MathSciNet review: 704619