In dieser Arbeit werden frei partiell kommutative Monoide (Spurmonoide) und Ersetzungssysteme über ihnen betrachtet. Diese algebraischen Modelle zählen zu den temporalen Strukturen, mit denen sich insbesondere Nebenläufigkeit in verteilten oder parallelen Systemen mathematisch exakt modellieren läßt.

Ersetzungssysteme über diesen Strukturen erlauben es, Prozeßtransformationen in nebenläufigen Kontexten zu beschreiben. Es werden zwei Problemstellungen untersucht, das Konfluenzproblem und das Normalformenproblem.

Wir geben einen alternativen Beweis für die Unentscheidbarkeit des Konfluenzproblems und zeigen, daß sogar schon bei vier Buchstaben die Konfluenz eines verkürzenden Ersetzungssystems nicht mehr entscheidbar ist (bei einer Kommutation). Es werden verschiedene konkrete Darstellungen von frei partiell kommutativen Monoiden gegeben und Faktorisierungsdarstellungen der Elemente eingeführt, die die Konstruktion von Datenstrukturen für effiziente Algorithmen ermöglichen. Dabei führen besondere Eigenschaften der linken Seiten eines Ersetzungssystems wie der "Zusammenhang" aller linken Seiten oder eine "Sichtbarkeitseigenschaft" zu effizienten Algorithmen. Es wird eine Dekompositionsmethode entwickelt, die auf "Cographenmonoiden" führt, und mit der der Algorithmus von Book so verallgemeinert werden kann, daß die nicht-uniforme Zeitkomplexität linear bleibt.