Projekt A11 - Gutartige unendliche konvergente Wortersetzungssysteme: Ausdruckskraft und algorithmische Eigenschaften

(bis 12/99)

Konvergente Wortersetzungssysteme bilden eine wichtige Möglichkeit, das Wortproblem für einige einfache algebraische Strukturen wie Monoide oder Gruppen zu lösen und in diesen Strukturen effektiv zu rechnen. Dazu braucht man allerdings die Einschränkung, daß die von dem betrachteten Wortersetzungssystem induzierte Reduktionsrelation effektiv berechenbar ist. Dies ist beispielsweise immer dann der Fall, wenn das betrachtete System endlich ist. In diesem Forschungsvorhaben geht es nun darum, solche unendlichen konvergenten Wortersetzungssysteme zu untersuchen, für die die induzierte Reduktionsrelation ebenfalls effektiv berechenbar ist.

Mitarbeiter:

Masashi Katsura
(Department of Mathematics, Kyoto-Sangyo University, Kyoto, Japan)

Yuji Kobayashi
(Department of Information Science, Toho University, Funabashi, Japan)

Interne Berichte:

Katsura, M., Kobayashi, Y., and Otto, F. :
Infinite convergent string-rewriting systems and cross-sections for monoids
Mathematische Schriften Kassel 3/96, Universität-GH Kassel.
published in Journal of Symbolic Computation in revised form.

Veröffentlichungen:

Katsura, M., Kobayashi, Y., and Otto, F. :
Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
Journal of Symbolic Computation, 1998, 26:621-648.