Projekt A3 - Reduktionssysteme für partiell-kommutative Monoide (Trace-rewriting 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 so-called trace-rewriting systems.


Otto, F. :
On confluence versus strong confluence for one-rule trace-rewriting systems.
Mathematical Systems Theory, 1995, 28:363-384.
Wrathall, C., Diekert, V., and Otto, F. :
One-rule trace-rewriting systems and confluence.
In Havel, I. and Koubek, V., editors, Mathematical Foundations of Computer Science 1992, Lecture Notes in Computer Science 629, pages 511-521. Springer-Verlag 1992, Berlin.
Otto, F. and Wrathall, C. :
Overlaps in free partially commutative monoids.
Journal Computer System Sciences, 1991, 42:186-198.
Otto, F. :
On deciding confluence of finite string-rewriting systems modulo partial commutativity.
Theoretical Computer Science, 1989, 67:19-35.
Narendran, P. and Otto, F. :
Preperfectness is undecidable for Thue systems containing only length-reducing rules and a single commutation rule.
Information Processing Letters, 1988, 29:125-130.
Otto, F. :
Finite canonical rewriting systems for congruences generated by concurrency relations.
Mathematical Systems Theory, 1987, 20:253-260.