Bibliography | Bertol, Michael W.: Effiziente Normalform-Algorithmen für Ersetzungssysteme über frei partiell kommutativen Monoiden. University of Stuttgart, Faculty of Computer Science, Doctoral Thesis (1996). 114 pages, german.
|
CR-Schema | F.2.m (Analysis of Algorithms and Problem Complexity Miscellaneous)
|
Abstract | 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.
|
Full text and other links | PostScript (1165518 Bytes) HTML (generated from PostScript)
|
Department(s) | University of Stuttgart, Institute of Computer Science, Theoretical Computer Science
|
Entry date | June 10, 1996 |
---|