Konvergente Darstellungen algebraischer Strukturen - Research Information System | University of Kassel

without external funding

Konvergente Darstellungen algebraischer Strukturen

Project Details

Project duration: 07/1991–12/2002

Website: http://www.theory.informatik.uni-kassel.de/

Abstract

Hat eine algebraische Stuktur eine endliche konvergente Darstellung,
dann laesst sich das Wortproblem mittels des sogenannten
"Normalformenalgorithmus" loesen. Also ist die Loesbarkeit des
Wortproblems eine notwendige Voraussetzung dafuer, dass ueberhaupt
eine endliche konvergente Darstellung existieren kann. Es war lange
Zeit offen, ob diese Bedingung auch bereits hinreichend ist.
Inzwischen ist erkannt worden, dass dies nicht der Fall ist, und
es sind weitere notwendige Bedingungen entdeckt worden, so die
homologische Endlichkeitsbedingung FP3 und die kombinatorische
Bedingung des "endlichen Ableitungstyps". Sind diese Bedingungen
nun hinreichend fuer die Existenz endlicher konvergenter Darstellungen,
und in welcher Beziehung stehen diese verschiedenen notwendigen
Bedingungen zueinander?

Desweiteren interessiert man sich dafuer, welche im allgemeinen
unentscheidbaren Probleme loesbar werden, wenn man sie auf gewisse
Klassen von konvergentenDarstellungen einschraenkt.

Publications

2002	Cremanns, R., Otto, F., 2002. A completion procedure for finitely presented groups that is based on word cycles. Journal of Automated Reasoning 28, 235–256. https://doi.org/10.1023/A:1015741511536
2002	Kobayashi, Y., Otto, F., 2002. Some exact sequences for the homotopy (bi-)module of a monoid. Int. Journal of Algebra and Computation 12, 247–284. https://doi.org/10.1142/S0218196702000985
2002	Otto, F., 2002. Some results on Green’s relations for monoids presented by monadic string-rewriting systems. Semigroup Forum 65, 374–385. https://doi.org/10.1007/s002330010139
2001	Kobayashi, Y., Otto, F., 2001. On homotopical and homological finiteness conditions for finitely presented monoids. International Journal of Algebra and Computation 11, 391–403. https://doi.org/10.1142/S0218196701000577
2000	Otto, F., 2000. A survey on the computational power of some classes of monoid-presentations, in: J.C. Birget, S.M. (Hrsg.), Algorithmic Problems in Groups and Semigroups. Birkhaeuser, Boston, S. 171–194.
2000	Madlener, K., Otto, F., 2000. Some applications of prefix-rewriting in monoids, groups, and rings, in: M. Atkinson, N.G. (Hrsg.), Geometric Aspects of Modern Algebra. Cambridge University Press, Cambridge, S. 150–191.
2000	Otto, F., Sattler-Klein, A., 2000. The property FDT is undecidable for finitely presented monoids that have polynomial-time decidable word problems. International Journal of Algebra and Computation 10, 285–307. https://doi.org/10.1142/S0218196700000108
2000	Katsura, M., Kobayashi, Y., Otto, F., 2000. Undecidability results for monoids with linear-time decidable word problem, in: D.T. Lee, S.T. (Hrsg.), Algorithms and Computation, Proceedings ISAAC’2000. Springer, Berlin, S. 278–289.
1996	Cremanns, R., Otto, F., 1996. For groups the property of having finite derivation type is equivalent to the homological finiteness condition FP3 22, 155–177. https://doi.org/10.1006/jsco.1996.0046