A catalogue of complete group presentations (Q1097968)

A set of rules R on the symmetrized set of generators \(\Sigma =X\cup X^{-1}\) of a group G is a collection of pairs \(u\to v\) which induces a reduction on \(\Sigma^*\), namely the reflexive-transitive closure of the relation \(R_{\to}\) given by aub\(\to avb\) for all \(a,b\in \Sigma^*\). A word is R-irreducible (or in R-normal form) if it admits no reductions. The set R is well-founded if the partial order thus defined has no infinite descending chain \(w_ 0\to w_ 1\cdot \cdot \cdot\). The set R is confluent if \(u\to v\) and \(u\to v'\) implies \(v\to w\) and v'\(\to w\) for some w. A complete presentation is a well-founded and confluent set of rules. Since reductions can be done efficiently (in linear time), a complete presentation allows normal forms for the elements of the group defined by a presentation and thus allows a fast solution to the word problem of the group G. The aim of this paper is to provide complete presentations of the following families of groups: (a) fundamental groups of orientable and nonorientable surfaces; (b) Some Coxeter groups; (c) the Dyck groups (rotation subgroups of Coxeter groups); and (d) the finite symmetric groups. The most general Fuchsian group is believed by the author to have complete presentations. A general study of the problem can be found in the author's monograph ``Canonical forms in finitely presented algebras'' [in the Lecture Notes in Theoretical Computer Science (London, Pitman Pu. Co. series)].