×

zbMATH — the first resource for mathematics

A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier). (English) Zbl 0832.20080
The paper deals with Squier’s arguments on finite derivation type [C. C. Squier, J. Pure Appl. Algebra 49, 201-217 (1987; Zbl 0648.20045); C. C. Squier and F. Otto, Lect. Notes Comput. Sci. 256, 74-82 (1987; Zbl 0625.03023)]. Proofs are made shorter and easier by categorical machinery. Squier’s finiteness condition is of invariant type. It can be defined in terms of a finite presentation, but does not depend on the choice of this presentation. The result is that if a monoid has finite derivation type, then its third homology group is of finite type.

MSC:
20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
20M50 Connections of semigroups with homological algebra and category theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Burroni, A., Higher dimensional word problem, Theoret. comput. sci., 115, 43-62, (1993) · Zbl 0791.08004
[2] R. Cremanns and F. Otto, Finite derivation type implies the homological finiteness condition FP3, Mathematische Schriften Kassel, preprint 12/93. · Zbl 0834.20065
[3] Grooves, J.R.J., Rewriting systems and homology of groups, (), 114-141, Groups-Canberra 1989
[4] Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, J. ACM, 27, 797-821, (1980) · Zbl 0458.68007
[5] Kobayashi, Y., Complete rewriting systems and homology of monoid algebras, J. pure appl. algebra, 65, 263-275, (1990) · Zbl 0711.20035
[6] Lafont, Y.; ProutĂ©, A., Church-rosser property and homology of monoids, Math. struct. comput. sci., 1, 297-326, (1991) · Zbl 0748.68035
[7] Le Chenadec, P., Canonical forms in finitely presented algebras, (1986), Pitman London, Wiley, New York · Zbl 0682.68034
[8] Lane, S.Mac, Categories for the working Mathematician, () · Zbl 0906.18001
[9] Squier, C.C., Word problems and a homological finiteness condition for monoids, J. pure appl. algebra, 49, 201-217, (1987) · Zbl 0648.20045
[10] C.C. Squier, A finiteness condition for rewriting systems, revision by F. Otto and Y. Kobayashi, Theoret. Comput. Sci., to appear. · Zbl 0863.68082
[11] Squier, C.C.; Otto, F., The word problem for finitely presented monoids and finite canonical rewriting systems, (), 74-82
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.