Projekt A15 - Homologische und homotopische Endlichkeitsbedingungen (Homological and homotopical finiteness conditions)

(since 5/98, until 12/06)

Presentations of the form (\Sigma;R), where \Sigma is an alphabet and R is a string-rewriting system on \Sigma, provide a means to define and describe monoids . However, even if a monoid M is given through a finite presentation, the word problem for M may be undecidable. Therefore, one is interested in classes of finite presentations which guarantee that the word problem is decidable.

A class of this form that has received a lot of attention in recent years is the class of presentations that contain a finite string-rewriting system that is convergent, as such a system yields a complete set of unique representatives for the monoid presented, and given a string from \Sigma^*, the corresponding normal form can simply be computed by reduction . Hence, the question arises for an algebraic or a combinatorial characterization of the class of finitely presented monoids that admit a presentation through a finite convergent string-rewriting system.

Meanwhile quite a few conditions have been identified that a finitely presented monoid must necessarily satisfy, if it is to admit such a presentation. At first Squier proved that a monoid having a finite convergent presentation satisfies the homological finiteness conditions left FP_3 and right FP_3 [Squier 1987]. Next Kobayashi improved upon this result by showing that these monoids even satisfy the conditions left and right FP_\infty [Kobayashi 90].

Next Squier introduced the homotopical finiteness condition FDT, which is a combinatorial condition on the derivation graph associated with a given monoid presentation [Squier 94]. This condition implies the conditions left and right FP_3, but it does not imply left or right FP_\infty, as for groups it is equivalent to the condition FP_3 [Cremanns, Otto 96].

Finally Wang and Pride introduced the finiteness condition \FHT, which states that the homotopy bimodule of the given presentation is finitely generated. As the property \FDT\ this property is an invariant of finitely presented monoids, and it is implied by FDT, while it implies both left and right FP_3.

Here we are interested in the exact relationship between these various finiteness conditions.

Mitarbeiter:

Yuji Kobayashi
(Toho University, Funabashi, Japan)

Veröffentlichungen:

Kobayashi, Y., Otto, F.:
For finitely presented monoids the homological finiteness conditions FHT and bi-FP3 coincide.
Journal of Algebra, 2003, 264:327-341.
Kobayashi, Y. and Otto, F.:
Some exact sequences for the homotopy (bi-)module of a monoid.
Int. Journal of Algebra and Computation, 2002, 12:247-284.
Kobayashi, Y. and Otto, F.:
On homotopical and homological finiteness conditions for finitely presented monoids.
Int. Journal of Algebra and Computation, 2001, 11:391-403.
Katsura, M., Kobayashi, Y., Otto, F.:
Undecidability results for monoids with linear-time decidable word problem.
In Lee, D.T. and Teng, Sh., editors, Algorithms and Computation, Proceedings ISAAC 2000, pages 278-289, Lecture Notes in Computer Science 1969, Springer-Verlag, Berlin, 2000.
Otto, F. and Sattler-Klein, A. :
The property FDT is undecidable for finitely presented monoids that have polynomial-time decidable word problems
Int. Journal of Algebra and Computation, 2000, 10:285--307.

Technical Reports:

Kobayashi, Y., Otto, F.:
For finitely presented monoids the homological finiteness conditions FHT and bi-FP3 coincide.
Mathematische Schriften Kassel 4/01, Universität-GH Kassel, März 2001.
Katsura, M., Kobayashi, Y., Otto, F.:
Undecidable properties of monoids with word problem solvable in linear time - II. Cross-sections and homological and homotopical finiteness conditions.
Mathematische Schriften Kassel 2/01, Universität-GH Kassel, Januar 2001.
Kobayashi, Y. and Otto, F.:
Some exact sequences for the homotopy (bi-) module of a monoid.
Mathematische Schriften Kassel 18/00, Universität-GH Kassel, Juni 2000.
Kobayashi, Y. and Otto, F.:
On homotopical and homological finiteness conditions for finitely presented monoids.
Mathematische Schriften Kassel 1/00, Universität-GH Kassel, Januar 2000.
published in revised form in the Int. Journal of Algebra and Computation