About the descriptive power of certain classes of finite string-rewriting systems (Q910850)

This paper is a survey of results concerning classification of monoids and groups presented by certain types of rewriting systems. It contains a large sampling of results, including proofs for some of the simpler ones, and contains an extensive bibliography of 61 entries. It also contains a number of examples which illuminate the results, or in some cases, the limitations of the results. A finite set \(\Sigma\), the alphabet, and a finite set \(R\subset \Sigma^*\times \Sigma^*\), the rewriting rules, form a presentation for a monoid \(M_ R\), often called the syntactic monoid, namely, the quotient of the free monoid \(\Sigma^*\) by the congruence generated by R. Group presentations by rewriting systems are defined analogously, but with the usual convention of providing a second copy of \(\Sigma\) to denote the inverses of the elements of \(\Sigma\) and by providing outside of the set R the relations making corresponding elements in the two copies of \(\Sigma\) inverses of each other. The difference between a presentation by a rewriting system and a presentation in the usual sense is that reductions using the rewriting system can be considered to have a sense of direction - derivations in the sense of formal language theory. Topics considered in the paper range from questions of decidability to classifications of monoid- or group-theoretic properties in terms of language-theoretic properties to questions of computational complexity. Numerous technical, but reasonable, conditions are attached to the rewriting systems, but these cannot be reproduced in the space of this review. A sampling of results may give a flavor of the paper. If a monoid \(M_ R\) has a presentation such that the class of 1 is a regular, or context-free language, then every presentation has this property. Hence, the monoid can be called regular or context-free. A group is regular if and only if it is finite. A finitely generated group is context-free if and only if it contains a subgroup of finite index which is a free group, i.e., is virtually free. Let R be a free, weight-reducing, and confluent string-rewriting system on \(\Sigma\), and let L be a regular set of irreducible words. If the monoid \(M_ R\) is a group, then \([L]_ R\), the set of words in \(\Sigma^*\) equivalent to some word in L, is a deterministic context- free language. If \(E_ n\) (n\(\geq 0)\) denote the complexity classes of the Gregorczyk hierarchy, then for all integers m, n with \(3\leq n<m\) there is a finite canonical string-rewriting system R on an alphabet \(\Sigma\) such that (a) the word problem of \(M_ R\) is of intrinsic complexity \(E_ n- E_{n-1}\), and (b) the derivational complexity \(f_ R\) of R belongs to \(E_ m-E_{m- 1}.\) There exist finitely presented monoids and groups having a decidable word problem but which do not admit any presentation by a finite canonical string-rewriting system. However, for every finitely presented monoid with a decidable word problem there exists a presentation by a canonical two-level rewriting system. (Here canonical means that every word reduces to a unique normal form. A two-level rewriting system consists of a pair of sets of rewriting rules such that one set is applied after the other.)