Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-26T12:59:55.650Z Has data issue: false hasContentIssue false
  • English
  • Français

Monoid presentations of groups by finite special string-rewritingsystems

Published online by Cambridge University Press:  15 June 2004

Duncan W. Parkes ,
V. Yu. Shavrukov  and
Richard M. Thomas
Duncan W. Parkes
Affiliation:
Department of Mathematics and Computer Science, University of Leicester, University Road, Leicester, LE1 7RH, England; [email protected]. : School of Mathematics and Statistics, University of St Andrews, St Andrews, KY16 9SS, Scotland; [email protected].
V. Yu. Shavrukov
Affiliation:
Department of Mathematics and Computer Science, University of Leicester, University Road, Leicester, LE1 7RH, England; [email protected]. : IT-Universitetet i København, Glentevej 67, 2400 København NV, Denmark; [email protected].
Richard M. Thomas
Affiliation:
Department of Mathematics and Computer Science, University of Leicester, University Road, Leicester, LE1 7RH, England; [email protected].
Get access

Abstract

We show that the class of groups which have monoid presentations by means of finite special [λ]-confluent string-rewriting systems strictly contains the class of plain groups (the groups which are free products of a finitely generated free group and finitely many finite groups), and that any group which has an infinite cyclic central subgroup can be presented by such a string-rewriting system if and only if it is the direct product of an infinite cyclic group and a finite cyclic group.

Keywords

Groupmonoid presentationCayley graphspecial string-rewriting systemword problem.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 38 , Issue 3 , July 2004 , pp. 245 - 256
Copyright
© EDP Sciences, 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

R.V. Book and F. Otto, String-Rewriting Systems. Texts and Monographs in Computer Science, Springer-Verlag (1993).
Y. Cochet, Church-Rosser congruences on free semigroups, in Algebraic Theory of Semigroups, edited by G. Pollák. Colloquia Mathematica Societatis János Bolyai 20, North-Holland Publishing Co. (1979) 51–60.
Haring-Smith, R.H., Groups and simple languages. Trans. Amer. Math. Soc. 279 (1983) 337–356.
Herbst, T. and Thomas, R.M., Group presentations, formal languages and characterizations of one-counter groups. Theoret. Comput. Sci. 112 (1993) 187–213. CrossRef
R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete 89, Springer-Verlag (1977).
Madlener, K. and Otto, F., About the descriptive power of certain classes of finite string-rewriting systems. Theoret. Comput. Sci. 67 (1989) 143–172. CrossRef
W. Magnus, A. Karrass and D. Solitar, Combinatorial Group Theory, 2nd edn. Dover (1976).