Projekt A2 - Präfix-Reduktion und das verallgemeinerte Wortproblem für Gruppen

(bis 12/96)

Das verallgemeinerte Wortproblem für Gruppen läßt sich mit Hilfe von Linkskongruenzen wie folgt beschreiben. Sei (A;R) eine endliche Darstellung einer Gruppe G, und sei U eine endliche Menge von Erzeugenden. Mit U läßt sich nun eine Präfix-Reduktion assoziieren, so daß, für alle Wörter x über A, x zur Untergruppe <U> gehört gdw. x 1 gilt. Ist terminierend und konfluent auf der Klasse der 1, so läßt sich <U> mittels Präfix-Reduktion entscheiden. Ziel dieses Forschungsvorhabens ist es, hinreichende Bedingungen für die 1-Konfluenz von zu entwickeln, die sich effektiv nachprüfen lassen. Außerdem sollen Klassen von Gruppen identifiziert werden, auf die diese Verfahren anwendbar sind.

Veröffentlichungen:

Madlener, K. and Otto, F. :
Some applications of prefix-rewriting in monoids, groups and rings.
In Atkinson, M. and Gilbert, N. and Howie, J. and Linton, S. and Robertson, E., editors, Computational and Geometric Aspects of Modern Algebra, pages 150-191, London Mathematical Society Lecture Notes 275, Cambridge University Press, Cambridge, 2000.
Cremanns, R. :
Prefix-rewriting on context-free groups.
Applicable Algebra in Engineering, Communication and Computing, 8:315-344, 1997.
Kuhn, N., Madlener, K., and Otto, F. :
Computing presentations for subgroups of polycyclic groups and of context-free groups.
Applicable Algebra in Engineering, Communication and Computing, 1994, 5:287-316.
Cremanns, R. and Otto, F. :
Constructing canonical presentations for subgroups of context-free groups in polynomial time.
In von zur Gathen, J. and Giesbrecht, M., editors, Proceedings ISSAC'94, pages 147-153, New York. ACM 1994.
Kuhn, N., Madlener, K., and Otto, F. :
Computing presentations for subgroups of polycyclic groups and of context-free groups.
In Wang, P., editor, Proceedings ISSAC'92, pages 240-250, New York. ACM 1992.
Kuhn, N., Madlener, K., and Otto, F. :
A test for \lambda-confluence for certain prefix rewriting systems with applications to the generalized word problem.
In Watanabe, S. and Nagata, M., editors, Proceedings ISSAC'90, pages 8-15, New York. ACM 1990.