Monoid presentations of groups by finite special string-rewriting systems

Duncan W. Parkes; V. Yu. Shavrukov; Richard M. Thomas

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2004)

  • Volume: 38, Issue: 3, page 245-256
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Parkes, Duncan W., Shavrukov, V. Yu., and Thomas, Richard M.. "Monoid presentations of groups by finite special string-rewriting systems." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 38.3 (2004): 245-256. <http://eudml.org/doc/245331>.

@article{Parkes2004,
abstract = {We show that the class of groups which have monoid presentations by means of finite special $[\lambda ]$-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.},
author = {Parkes, Duncan W., Shavrukov, V. Yu., Thomas, Richard M.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {group; monoid presentation; Cayley graph; special string-rewriting system; word problem; plain groups; monoid presentations; Cayley graphs; special string-rewriting systems; free products; direct products},
language = {eng},
number = {3},
pages = {245-256},
publisher = {EDP-Sciences},
title = {Monoid presentations of groups by finite special string-rewriting systems},
url = {http://eudml.org/doc/245331},
volume = {38},
year = {2004},
}

TY - JOUR
AU - Parkes, Duncan W.
AU - Shavrukov, V. Yu.
AU - Thomas, Richard M.
TI - Monoid presentations of groups by finite special string-rewriting systems
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2004
PB - EDP-Sciences
VL - 38
IS - 3
SP - 245
EP - 256
AB - We show that the class of groups which have monoid presentations by means of finite special $[\lambda ]$-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.
LA - eng
KW - group; monoid presentation; Cayley graph; special string-rewriting system; word problem; plain groups; monoid presentations; Cayley graphs; special string-rewriting systems; free products; direct products
UR - http://eudml.org/doc/245331
ER -

References

top
  1. [1] R.V. Book and F. Otto, String-Rewriting Systems. Texts and Monographs in Computer Science, Springer-Verlag (1993). Zbl0832.68061MR1215932
  2. [2] 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. Zbl0408.20054
  3. [3] R.H. Haring-Smith, Groups and simple languages. Trans. Amer. Math. Soc. 279 (1983) 337–356. Zbl0518.20030
  4. [4] T. Herbst and R.M. Thomas, Group presentations, formal languages and characterizations of one-counter groups. Theoret. Comput. Sci. 112 (1993) 187–213. Zbl0783.68066
  5. [5] R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete 89, Springer-Verlag (1977). Zbl0368.20023MR577064
  6. [6] K. Madlener and F. Otto, About the descriptive power of certain classes of finite string-rewriting systems. Theoret. Comput. Sci. 67 (1989) 143–172. Zbl0697.20017
  7. [7] W. Magnus, A. Karrass and D. Solitar, Combinatorial Group Theory, 2nd edn. Dover (1976). Zbl0362.20023MR422434

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.