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.
Mots-clés : group, monoid presentation, Cayley graph, special string-rewriting system, word problem
@article{ITA_2004__38_3_245_0, author = {Parkes, Duncan W. and Shavrukov, V. Yu. and Thomas, Richard M.}, title = {Monoid presentations of groups by finite special string-rewriting systems}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {245--256}, publisher = {EDP-Sciences}, volume = {38}, number = {3}, year = {2004}, doi = {10.1051/ita:2004012}, mrnumber = {2076402}, zbl = {1071.20037}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2004012/} }
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 SP - 245 EP - 256 VL - 38 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2004012/ DO - 10.1051/ita:2004012 LA - en ID - ITA_2004__38_3_245_0 ER -
%0 Journal Article %A Parkes, Duncan W. %A Shavrukov, V. Yu. %A Thomas, Richard M. %T Monoid presentations of groups by finite special string-rewriting systems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2004 %P 245-256 %V 38 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2004012/ %R 10.1051/ita:2004012 %G en %F ITA_2004__38_3_245_0
Parkes, Duncan W.; Shavrukov, V. Yu.; Thomas, Richard M. Monoid presentations of groups by finite special string-rewriting systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 3, pp. 245-256. doi : 10.1051/ita:2004012. http://archive.numdam.org/articles/10.1051/ita:2004012/
[1] String-Rewriting Systems. Texts and Monographs in Computer Science, Springer-Verlag (1993). | MR | Zbl
and ,[2] 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. | Zbl
,[3] Groups and simple languages. Trans. Amer. Math. Soc. 279 (1983) 337-356. | Zbl
,[4] Group presentations, formal languages and characterizations of one-counter groups. Theoret. Comput. Sci. 112 (1993) 187-213. | Zbl
and ,[5] Combinatorial Group Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete 89, Springer-Verlag (1977). | MR | Zbl
and ,[6] About the descriptive power of certain classes of finite string-rewriting systems. Theoret. Comput. Sci. 67 (1989) 143-172. | Zbl
and ,[7] Combinatorial Group Theory, 2nd edn. Dover (1976). | MR | Zbl
, and ,Cité par Sources :