Projekt A3  Reduktionssysteme für partiellkommutative Monoide
(Tracerewriting systems)
(bis 12/94)
Recently partially commutative monoids are getting a lot of attention
from computer scientists, since these monoids are useful in studying
problems of concurrency control. Accordingly, combinatorial and
computational problems for partially commutative monoids are being
studied. We are in particular interested in rewriting systems on
partially commutative monoids, the socalled tracerewriting systems.
Veröffentlichungen:

Otto, F. :
 On confluence versus strong confluence for onerule tracerewriting
systems.
Mathematical Systems Theory, 1995, 28:363384.

Wrathall, C., Diekert, V., and Otto, F. :
 Onerule tracerewriting systems and confluence.
In Havel, I. and Koubek, V., editors, Mathematical Foundations
of Computer Science 1992, Lecture Notes in Computer Science 629, pages
511521. SpringerVerlag 1992, Berlin.

Otto, F. and Wrathall, C. :
 Overlaps in free partially commutative monoids.
Journal Computer System Sciences, 1991, 42:186198.

Otto, F. :
 On deciding confluence of finite stringrewriting systems modulo
partial commutativity.
Theoretical Computer Science, 1989, 67:1935.

Narendran, P. and Otto, F. :
 Preperfectness is undecidable for Thue systems containing only
lengthreducing rules and a single commutation rule.
Information Processing Letters, 1988, 29:125130.

Otto, F. :
 Finite canonical rewriting systems for congruences generated by
concurrency relations.
Mathematical Systems Theory, 1987, 20:253260.