##
**Word problems and a homological finiteness condition for monoids.**
*(English)*
Zbl 0648.20045

A terminating Church-Rosser presentation (also known as a complete rewriting system) for a monoid S consists of a set R of ordered pairs of words in a free monoid F. This free monoid, together with the set of equalities arising from the pairs in R, should present S.

If u,v\(\in F\), then v is a subword of u if \(u=avb\) for some a,b\(\in F\). A single replacement then consists of replacing a subword which is a left hand side of a pair in R by the right hand side of the pair. We require that there is no infinite sequence of such replacements. There is then a corresponding set of irreducible elements for which no replacement is possible and we further require that the natural map from irreducible elements of F to elements of S be bijective.

In this interesting paper, such rewriting systems are exploited to give the beginnings - up to dimension 3 - of a free \({\mathbb{Z}}S\)-resolution of \({\mathbb{Z}}\). In the case of groups, this extends the well-known partial resolution which arises from the so-called ‘relation sequence’. Thus the term in dimension 0 is \({\mathbb{Z}}S\) and in dimensions 1 and 2 is a free module on a basis which is bijective with, respectively, the generators of F, and R. The author adds a term in dimension 3 for which the basis is bijective with the set of all overlaps of left-hand sides of rules if R. He then defines a reasonably natural (although not unique) boundary map and shows the necessary exactness.

The result can also be used to give an example of group or monoid with a finite presentation and solvable word problem which can have no finite terminating Church-Rosser presentation. For the result shows that if S has a finite terminating Church-Rosser presentation then there must be a \({\mathbb{Z}}S\)-resolution of \({\mathbb{Z}}\) which is finitely generated in the first 3 dimensions; i.e. S has type \((FP)_ 3\).

The interested reader should, however, be aware of results of D. J. Anick [Trans. Am. Math. Soc. 296, 641-659 (1986; Zbl 0598.16028)] which appear to be related. With somewhat different, but apparently related, hypotheses, Anick gives a \({\mathbb{Z}}S\)-resolution of \({\mathbb{Z}}\) (in all dimensions). Where the hypotheses overlap, this resolution seems to agree with the one given here in the first three dimensions.

If u,v\(\in F\), then v is a subword of u if \(u=avb\) for some a,b\(\in F\). A single replacement then consists of replacing a subword which is a left hand side of a pair in R by the right hand side of the pair. We require that there is no infinite sequence of such replacements. There is then a corresponding set of irreducible elements for which no replacement is possible and we further require that the natural map from irreducible elements of F to elements of S be bijective.

In this interesting paper, such rewriting systems are exploited to give the beginnings - up to dimension 3 - of a free \({\mathbb{Z}}S\)-resolution of \({\mathbb{Z}}\). In the case of groups, this extends the well-known partial resolution which arises from the so-called ‘relation sequence’. Thus the term in dimension 0 is \({\mathbb{Z}}S\) and in dimensions 1 and 2 is a free module on a basis which is bijective with, respectively, the generators of F, and R. The author adds a term in dimension 3 for which the basis is bijective with the set of all overlaps of left-hand sides of rules if R. He then defines a reasonably natural (although not unique) boundary map and shows the necessary exactness.

The result can also be used to give an example of group or monoid with a finite presentation and solvable word problem which can have no finite terminating Church-Rosser presentation. For the result shows that if S has a finite terminating Church-Rosser presentation then there must be a \({\mathbb{Z}}S\)-resolution of \({\mathbb{Z}}\) which is finitely generated in the first 3 dimensions; i.e. S has type \((FP)_ 3\).

The interested reader should, however, be aware of results of D. J. Anick [Trans. Am. Math. Soc. 296, 641-659 (1986; Zbl 0598.16028)] which appear to be related. With somewhat different, but apparently related, hypotheses, Anick gives a \({\mathbb{Z}}S\)-resolution of \({\mathbb{Z}}\) (in all dimensions). Where the hypotheses overlap, this resolution seems to agree with the one given here in the first three dimensions.

Reviewer: J.R.J.Groves

### MSC:

20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |

20F05 | Generators, relations, and presentations of groups |

20J05 | Homological methods in group theory |

20M05 | Free semigroups, generators and relations, word problems |

### Keywords:

terminating Church-Rosser presentation; complete rewriting system; free monoid; replacements; irreducible elements; free \({bbfZ}S\)-resolution; boundary map; solvable word problem; type \((FP)_ 3\)### Citations:

Zbl 0598.16028
PDF
BibTeX
XML
Cite

\textit{C. C. Squier}, J. Pure Appl. Algebra 49, 201--217 (1987; Zbl 0648.20045)

Full Text:
DOI

### References:

[1] | Abels, H., An example of a finitely presented solvable group, (Wall, C. T.C., Homological Group Theory, London Mathematical Society Lecture Notes, 36, (1979), Cambridge University Press Cambridge), 205-211 |

[2] | H. Abels and K.S. Brown, Finiteness properties of solvable S-arithmetic groups, Preprint. · Zbl 0617.20020 |

[3] | Bieri, R., Homological dimension of discrete groups, Queen Mary College Mathematics Notes, (1976), London · Zbl 0357.20027 |

[4] | Bieri, R., A connection between the integral homology and the centre of a rational linear group, Math. Z., 170, 263-266, (1980) · Zbl 0427.20042 |

[5] | Book, R. V., Thue systems and the church-rosser property: replacement systems, specification of formal languages and presentations of monoids, (Cummings, L. J., Combinatorics on Words: Progress and Perspectives, (1983), Academic Press New York), 1-38 · Zbl 0563.68062 |

[6] | Brown, K. S., Cohomology of groups, (1982), Springer Berlin · Zbl 0367.18012 |

[7] | K.S. Brown, Finiteness properties of groups, Preprint. · Zbl 0613.20033 |

[8] | Cartan, H.; Eilenberg, S., Homological algebra, (1956), Princeton University Press Princeton, NJ · Zbl 0075.24305 |

[9] | Church, A.; Rosser, J. B., Some properties of conversion, Trans. Amer. Math. Soc., 39, 472-482, (1936) · Zbl 0014.38504 |

[10] | Cohn, P. M., Universal algebra, (1965), Harper and Row New York · Zbl 0141.01002 |

[11] | Fox, R. H., Free differential calculus I, Ann. of Math., 57, 547-560, (1953) · Zbl 0142.22303 |

[12] | Hilton, P. J.; Stammbach, U., A course in homological algebra, (1971), Springer Berlin · Zbl 0238.18006 |

[13] | Houghton, C. H., The first cohomology of a group with permutation module coefficients, Arch. Math., 31, 254-258, (1978) · Zbl 0377.20044 |

[14] | Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, J. Assoc. Comput. Mach., 27, 797-821, (1980) · Zbl 0458.68007 |

[15] | Jantzen, M., A note on a special one-rule semi-thue system, Inform. Process. Lett., 21, 135-140, (1985) · Zbl 0581.68030 |

[16] | Newman, M. H.A., On theories with a combinatorial definition of “equivalence”, Ann. of Math., 43, 223-243, (1943) · Zbl 0060.12501 |

[17] | Nivat, M., Congruences parfaites et quasi-parfaites, Seminaire Dubreil, 7, (1971-1972) · Zbl 0338.02018 |

[18] | Stallings, J. R., A finitely-presented group whose 3-dimensional integral homology is not finitely-generated, Amer. J. Math., 85, 541-543, (1963) · Zbl 0122.27301 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.