Effiziente Normalform-Algorithmen für Ersetzungssysteme über frei partiell kommutativen Monoiden c a X b B C A Von der Fakultät für Informatik der Universität Stuttgart zur Erlangung der Würde eines Doktors der Naturwissenschaften genehmigte Abhandlung von Michael W. Bertol aus München Hauptberichter: Prof. Dr. V. Diekert Mitberichter: Prof. Dr. M. Jantzen Institut für Informatik der Universität Stuttgart, 1996 i Danksagung Ich danke meinen Kollegen der beiden Theorie-Abteilungen für ihr Interesse an meinen Themen, insbesondere danke ich Anca Muscholl und Holger Petersen für eine sehr gute Zusammenarbeit. Für interessante Anregungen und Gespräche bedanke ich mich bei Dan Teodosiu und Zolt?an ? Esik. Dank der intensiven Unterstützung von Prof. Dr. Volker Diekert konnte die vorliegende Arbeit in so kurzer Zeit fertiggestellt werden. Seinem regen Interesse und seiner optimistschen Grundhaltung verdanke ich sehr viel. Für die Übernahme des Berichtes möchte ich mich bei Prof. Dr. Matthias Jantzen bedanken. Mein größter Dank gilt meiner Familie für ihre riesige Unterstützung. iii Zusammenfassung 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. v Inhaltsverzeichnis 1 Einleitung 1 1.1 Semantik nebenläufiger Vorgänge . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Spuren und ihre Darstellungen 7 2.1 Konkrete Beschreibungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Das Levi-Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Das Einbettungstheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Ersetzungssysteme 11 3.1 Eigenschaften von Ersetzungssystemen . . . . . . . . . . . . . . . . . . . 11 4 Konfluenz von Spurersetzungssystemen 13 4.1 Unentscheidbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5 Algorithmen für Ersetzungssysteme mit zusammenhängenden linken Seiten 20 5.1 Das Berechnungsmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2 Die C?-Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.3 Der Datentyp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.4 Operationen auf der Darstellung . . . . . . . . . . . . . . . . . . . . . . . 36 5.4.1 CONCATTRACE . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4.2 SPLITTRACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.5 Der Reduktionsalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 41 6 Effizienzsteigerung durch Sichtbarkeit bei Ersetzungssystemen mit zusammenhängenden linken Seiten 44 6.1 Sichtbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2 Ein Linearzeit-Reduktionsalgorithmus . . . . . . . . . . . . . . . . . . . . 47 7 Dekomposition von Spurmonoiden 52 7.1 Der Term-Morphismus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.2 Charakterisierung von Faktoren . . . . . . . . . . . . . . . . . . . . . . . 56 vii 8 Auf Dekompositionen basierende Algorithmen 58 8.1 Dekomposition von Ersetzungssystemen . . . . . . . . . . . . . . . . . . . 58 8.2 Term-Beschriftung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 8.3 Der abstrakte Datentyp . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 8.3.1 Algorithmische Primitive . . . . . . . . . . . . . . . . . . . . . . . 62 8.3.2 Quotientenberechnung . . . . . . . . . . . . . . . . . . . . . . . . 68 8.4 Dekomponierbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 8.5 Ein O(n log n)-Reduktionsalgorithmus . . . . . . . . . . . . . . . . . . . 70 8.6 Ein Linearzeit-Reduktionsalgorithmus . . . . . . . . . . . . . . . . . . . . 76 9 Ausblick 89 Anhang 89 A Anhang: Faktoren und Faktorisierungen 90 A.1 Darstellungen von Faktorisierungen . . . . . . . . . . . . . . . . . . . . . 90 A.2 Ordnungen für Vorkommen . . . . . . . . . . . . . . . . . . . . . . . . . 92 A.3 Zusammenhängende Faktoren . . . . . . . . . . . . . . . . . . . . . . . . 94 A.4 Allgemeine Faktoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 viii 1 Einleitung Der sequentiellen Bearbeitung rechenintensiver Probleme sind technologische Grenzen gesetzt. Ein Weg zur Überwindung dieser Grenzen ist Parallelisierung. Nebenläufigkeit, Parallelität und Verteiltheit haben sich innerhalb der letzten Dekade als sehr wichtige Konzepte in der Informatik erwiesen. Deshalb war es notwendig, eine mathematisch logisch fundierte Formalisierung solcher Systeme und insbesondere ihrer temporalen Struktur zu entwickeln. Diese Formalisierungen können zur Beschreibung und Validierung von Eigenschaften oder als Kalkül verwendet werden. Einer der ersten dieser Ansätze waren die Petrinetzsemantiken, die von Hoare [Hoa78] definierten kommunizierenden sequentiellen Prozesse CSP und der von Milner und Hennessy [Mil80] eingeführte Kalkül CCS. Pratt schlug eine auf Halbordnungen basierende Semantik vor [Pra86]. Es folgte eine Vielzahl von sehr allgemeinen algebraischen und logischen Modellen wie Ereignisräume, monoidale Kategorien, Chu-Räume und viele mehr. Ursprünglich wurden die frei partiell kommutativen Monoide oder Spurmonoide von Cartier und Foata [CF69] verwendet, um kombinatorische Probleme zu behandeln. Aufgrund ihrer algebraischen Eigenschaften und ihrer Verwandtschaft zur Theorie der formalen Sprachen erscheinen sie für weitere Untersuchungen attraktiv. Gleichzeitig hat sich die Theorie der Spuren als ein adäquates Modell zur Analyse einer großen Klasse von nebenläufigen Vorgängen erwiesen. Der erste, der diese Verbindung entdeckt hat, war Mazurkiewicz. In [Maz77] wurden die frei partiell kommutativen Monoide als eine Semantik für nebenläufige Prozesse erkannt. Die Verwandtschaft zu freien Monoiden motivierte Diekert in [Die87], einen Teil der Theorie der Semi-Thue-Systeme oder Wortersetzungssysteme für frei partiell kommutative Monoide zu verallgemeinern. Der Hintergrund war, Formalismen zur Beschreibung von statischen Ersetzungen in nebenläufigen Kontexten zu finden. Mit Spurersetzungssystemen können Programm- bzw. Prozeßtransformationen in der Spursemantik beschrieben werden. Die korrekte und effiziente Transformation von nebenläufigen und konkurrierenden Programmschemata ist eine Voraussetzung für den Umgang mit paralleleln und verteilten Rechnermodellen bzw. Algorithmen. 1.1 Semantik nebenläufiger Vorgänge Betrachten wir ein konkretes einführendes Beispiel. Sei ein nebenläufiges Programmsystem (beispielsweise ein nebenläufiges Datenbank-Transaktionssystem) durch die folgen- 1 den Transaktionen Ta x := f(x; z) Tb y := g(y; z) Tc z := h(x; y) Td x := i(z) beschrieben. Dann, vorausgesetzt die Funktionen f; g; h; i besitzen keine Seiteneffekte, existiert die folgende die (Daten-)Abhängigkeiten beschreibende Funktion mit ff : fa; b; c; dg ?! Pfx; y; zg a 7?! fx; zg b 7?! fy; zg c 7?! fz; x; yg d 7?! fx; zg Wir identifizieren Tx mit x für x 2 fa; b; c; dg. Das Bild einer Transaktion ist ihr Datenraum, hier also die Variablen. Durch diese Funktion wird ein Abhängigkeitsgraph (V; E) via V = fa; b; c; dg und (u; v) 2 E () ff(u) \ ff(v) 6= ; für alle u; v 2 V definiert. Sei nun w 2 fa; b; c; dg? eine Ausführungssequenz, so ist das Resultat nicht von der Reihenfolge innerhalb Teilsequenzen, die nur die Transaktionen d und b enthalten, abhängig, denn es gilt (b; d) = 2 D oder äquivalent dazu ff(b) \ ff(d) 6= ; | diese Aktionen können nebenläufig abgearbeitet werden. D.h. Sequenzen modulo der Kommutation db = bd besitzen dieselbe Semantik | warum sollten sie unterschieden werden? Den diese Semantik spezifizierenden Graphen (V; E) = (?; D) werden wir als Abhängigkeitsalphabet einführen. Abstrahiert man von den Variablen im Beispiel, so erkennt man, daß jede exklusive Ressource (in einem System) diesen Typ von Abhängigkeiten induziert. Damit verfügen wir über eine mathematische Beschreibung nebenläufiger und konkurrierender Vorgänge bzw. äquivalenter serieller Sequenzen. Die durch D definierte Kommutationsrelation ab = ba für alle (a; b) = 2 D induziert eine Kongruenz via uabv = ubav, u; v 2 ??, auf dem freien Monoid ?? ? = S i2N ?i, und die Katenation, d.h. die sequentielle Komposition, wird als Operation ererbt. Die Verwandtschaft dieser Struktur zu freien Monoiden motivierte eine Reihe von Mathematikern und Informatikern, andere bekannte Konzepte auf diese algebraischen Strukturen zu übertragen. Eines dieser Konzepte sind die hier betrachteten Ersetzungssysteme. Das Einführen eines Ersetzungssystems führt zu einer operationellen Semantik für nebenläufige Vorgänge. Jede Transaktion läßt sich als ein Modifikator, eine Ersetzung, auffassen. Betrachten wir als zweites Beispiel Petrinetze, das vermutlich populärste Modellierungswerkzeug in diesem Kontext. Sei N = (S; T; F; M) ein Petrinetz mit den Stellen S, den Transitionen T , den Kanten F ? (T ? S) [ (S ? T ) und einer Markierung M : S ! N . 2 Dann kann eine Berechnung dieses Petrinetzes1 mit dem Ersetzungssystem R = ?? tv(s))s2S ! (tn(s))s2S ? j t 2 T ? über dem Monoid M = NM ? = Q s2Mfsg? mit tv(s) = ? 1 sF t 0 :sF t und tn = ? 1 tF s 0 :tF s simuliert werden. Ein anderes Spezifizierungswerkzeug sind die erkennbaren Mengen (über einem hier partiell kommutativen Monoid M (?; D)). Sei h : M (?; D) ?! N ein Homomorphismus in ein endliches Monoid N = (N; ?; 1) und X ? N eine Teilmenge so, daß die Sprache L = h?1(X) erkannt wird. Dann kann mit dem Ersetzungssystem fxa ! x ? h(a) j x 2 N; a 2 ?g kontrolliert werden, ob ein Element t 2 M (?; D) die Spezifikation t 2 L erfüllt, denn 1N t ? =)R x 2 X gilt genau dann, wenn t 2 L. Sei t = [t1 : : : ti : : : tn] die Spur, die eine Prozeßsequenz t1 : : : tn modelliert. Dabei können einzelne Prozesse durchaus nebenläufig sein. Das bedeutet, t ist die Menge aller durch die Abhängigkeitsrelation D ? ? ? ? beschriebenen äquivalenten Sequentialisierungen der Folge t1 : : : tn. Eine Verfeinerung von Prozeß ti durch Prozeß x sei durch eine Regel ti ! x beschrieben. x kann wiederum aus Prozessen [x1 : : : xm] bestehen, die wieder nebenläufig seien können. Diese Prozesse können auch mit den Prozessen t1; : : : ; ti?1; ti+1; : : : ; tn kommutieren. Die Anwendung der Regel transformiert die Prozeßsequenz entsprechend. [t1 : : : ti?1][ti][ti+1 : : : tn] =) [t1 : : : ti?1][x1 : : : xm][ti+1 : : : tn] Mit der gleichen Methode lassen sich auch Teilprozesse abstrahieren, was sich durch Umkehren der Regel zu x ! ti erreichen läßt. [t1 : : : ti?1x1 : : : xmti+1 : : : tn] =) [t1 : : : ti?1titi+1 : : : tn] Mit dem Formalismus " Ersetzungssystem modulo Kommutationen\ lassen sich Programmtransformationen, d.h. Compiler und Optimierer beschreiben. Betrachten wir eine einfache prozedurale Programmiersprache mit den Variablen a, b, c, d, e und den Operationen +; ?, sowie den Anweisungen read und write und dem Zuweisungsoperator :=. Das Rechnermodell verfüge über die Prozessoren PA, A ? fa; b; c; d; eg, einen Eingabekanal, einen Ausgabekanal und den entsprechenden Speicher für die Variablen. Jeder Prozessor PA hat einen Akkumulator und verfügt über den Instruktionssatz LOADA v, STOREA v, ADDA v, SUBA v, READA und WRITEA. 1Feuersequenzen f 2 T ? (bei 1-sicheren Netzen) können als eine Spur interpretiert werden. 3 Ein Compiler könnte die Anweisungen wie folgt transformieren: Programmkonstrukt S Maschinenkonstrukt M(S) v1 := v2 + v3 LOADA v2; ADDA v3; STOREA v1 v1 := v2 ? v3 LOADA v2; SUBA v3; STOREA v1 read v READfvg; STOREfvg v write v LOADfvg v; WRITEfvg (A = fv1; v2; v3g in der ersten und zweiten Zeile.) Verwenden wir die im ersten Beispiel vorgestellte Methode um die einzelnen Aufgaben auf die Prozessoren zu verteilen, indem wir die Zuweisungen v1 := v2ffiv3, ffi 2 f+; ?g mit Buchstaben av1:=v2ffiv3 und die Anweisung read v mit bv und write v mit cv assoziieren, so erhalten wir die Abhängigkeiten (av1:=v2ffiv3 ; av01:=v02ffi0v03 ) 2 D () fv1; v2; v3g \ fv0 1; v0 2; v0 3g 6= ; (av1:=v2ffiv3 ; bv); (bv; av1:=v2ffiv3) 2 D () v 2 fv1; v2; v3g (av1:=v2ffiv3 ; cv); (cv; av1:=v2ffiv3) 2 D () v 2 fv1; v2; v3g (bv; bv); (cv; cv); (bv; cv); (cv; bv) 2 D Die " Buchstaben\ LOADA v, ADDB v, STOREC v kommutieren (nach Spezifikation des Maschinenmodells), wenn die Indizes nichtleeren Schnitt besitzen. Die " Buchstaben\ READA v und WRITEB v0 sind genau dann abhängig, wenn A \B 6= ;. Ansonsten ist, da es nur einen Eingabe- und einen Ausgabekanal gibt, READA v von READB v0 bzw. WRITEA v von WRITEB v0 für alle A; B ? fa; b; c; d; eg abhängig. Das Ersetzungssystem R mit den Regeln aS !M(S) (siehe Tabelle) simuliert einen automatisch (kanonisch) parallelisierenden Compiler. Dieser könnte noch um eine Optimierung erweitert werden, indem entsprechende Regeln eingeführt werden, die beispielsweise die kombinierten READ-STORE-Anweisungen durch eine einzige READ-Anweisung auf dem die gelesene Variable bearbeitenden Prozessor unter bestimmten Bedingungen (Kontexten) ersetzen. Die Existenz von sehr effizienten Ersetzungsalgorithmen ermöglicht sogar ein Austauschen von Teilabläufen durch einen Dispatcher während des Abarbeitens der Prozesse. D.h. eine weitere denkbare Applikation ist die dynamische Optimierung von Prozeß- sequenzen. Sei t = t1 : : : tn beispielsweise eine Sequenz von noch nicht abgearbeiteten Transaktionen in einem Datenbanksystem, die von links fortlaufend abgearbeitet und von rechts erweitert wird. Weiter seien in gewissen Kontexten effizientere Transaktionen möglich, die durch ein System von Regeln beschrieben sind. Im laufenden Betrieb eines solchen Systems treten Sequenzen von noch nicht bearbeiteten Transaktionen auf. Diese Sequenzen könnten dann mit Optimierungsregeln in effizientere Sequenzen transformiert werden, so daß die ursprüngliche Semantik erhalten bleibt. Diese Anwendung motiviert die Entwicklung von Algorithmen, die effizient Links-Reduktionen durchführen können. Auch vom mathematischen Standpunkt ist das Studium von Ersetzungssystemen modulo Kommutation interessant. Die Theorie der Spurersetzungssysteme ist eine natürliche 4 Verallgemeinerung der Ersetzungssysteme über freien Monoiden, den sogenannten Semi- Thue-Systemen oder Wortersetzungssystemen. So konnten viele Resultate, die bereits für freie Monoide bekannt waren, auf die partiell kommutative Theorie verallgemeinert werden. Eines der interessantesten Resultate ist eine Version des Knuth-Bendix-Reduktionsalgorithmus von Diekert [Die87]. Eine der Herausforderungen ist der Entwurf effizienter Algorithmen für Ersetzungssysteme über frei partiell kommutativen Monoiden. In dieser Arbeit werden einige Methoden vorgestellt, wie man effizient algorithmisch Normalformen berechnet und warum es kein dem Konfluenzentscheidungsverfahren im Falle freier Monoide entsprechendes effektives Pendant im partiell kommutativen Fall geben kann. 1.2 Überblick Die Arbeit wird von einer Reihe von Definitionen eingeleitet. Anschließend werden einige Repräsentationen diskutiert. Hiernach werden Ersetzungssysteme definiert und ein Unentscheidbarkeitsresultat von Narendran und Otto [NO88] verfeinert. In den folgenden Abschnitten beschäftigen wir uns mit dem " Normalformenproblem\. Im Kapitel 5 wird für Ersetzungssysteme mit zusammenhängenden linken Seiten eine Datenstruktur vorgestellt, die effiziente Manipulationen ermöglicht und zu einem " n log n\-Algorithmus führt. In dem darauffolgenden Kapitel wird eine Einschränkung, die " Sichtbarkeit\ untersucht. Sie führt zu einem " optimalen\ Reduktionsalgorithmus, der den Algorithmus von Book verallgemeinert. Eine interessante Unterklasse der Abhängigkeitsalphabete entspricht einer schon 1970 von Dijkstra vorgeschlagenen Spezifizierungsrestriktion. Die von ihm eingeführten parallelen Programmkonstrukte parbegin S1 jj S2 jj ... jj Sn parend und ; führen zu Abhängigkeitsalphabeten mit Cographstruktur. Sie finden sich im Cographenansatz in Kapitel 8 als Operatoren für das freie und das direkte Produkt wieder. Betrachtet man Prozessoren als Ressource R, besitzt die Ressourcenabbildung ff : ? ?! P(R) (siehe oben) dann eine der folgenden Strukturen: (i) Entweder existiert eine Zerlegung (der Anweisungen) ? = ?1 _[?2 so, daß die Menge der Ressourcen ff(?) = fff(a) ? R j a 2 ?g in zwei Teile T1 _[ T2 mit 8X 2 T18Y 2 T2 : X \ Y = ; zerfällt (d.h. absolute Parallelität), und die restringierten Abbildungen ffj?1 und ffj?2 besitzen jeweils eine dieser strukturellen Eigenschaften rekursiv, (ii) oder, wenn keine solche Zerlegung existiert, dann existiert eine andere Zerlegung ? = ?1 _[ ?2 so, daß die Menge der Ressourcen ff(?) = fff(a) ? R j a 2 ?g in zwei Teile T1 _[ T2 mit 8X 2 T18Y 2 T2 : X \ Y 6= ; 5 zerfällt, und die restringierten Abbildungen ffj?1 und ffj?2 besitzen jeweils eine der drei strukturellen Eigenschaften rekursiv (Damit ist das Mengensystem T1 [ T2 in einem gewissen Sinn isomorph zum kartesischen Produkt ?1 ? ?2.), (iii) oder die Anweisung ist atomar, d.h. unteilbar. Diese rekursive Struktur von Abhängigkeitsalphabeten induziert ihrerseits Zerlegungen von Spuren, die zu einer einfacheren, modularen Charakterisierung der Faktoreigenschaft und einer interessanten Algorithmenstruktur führen. Für die von Cographen-Abhängigkeitsalphabete erzeugte partiell kommutativer Monoide konnten Dekompositionstechniken entwickelt werden, die den Entwurf eines linearen Normalformalgorithmus ermöglichen. Wir schließen mit einem Ausblick und einer Zusammenfassung der Resultate über Faktorisierungen. In einem Anhang sind einige Ideen zu Verallgemeinerungen der vorgestellten Verfahren und technische Beweise zusammengefaßt. 6 2 Spuren und ihre Darstellungen Wir leiten diesen Abschnitt mit einer kurzen Einführung der grundlegenden Begriffe ein, zusammen mit einigen Notationen. Ein Abhängigkeitsalphabet ist ein geordnetes Paar (?; D), wobei ? ein endliches Alphabet und D ? ??? eine reflexive und symmetrische Relation bezeichnet, die Abhängigkeitsrelation. Die komplementäre Relation I = (? ? ?) n D wird als Unabhängigkeitsrelation oder als Kommutationsrelation bezeichnet. Wir bezeichnen das von ? erzeugte freie Monoid mit ??. Sei ?I? ?? ? ?? die Äquivalenzrelation, die durch die Menge geordneter Paare f(uabv; ubav) j u; v 2 ??; (a; b) 2 Ig induziert wird. Die Relation ?I ist eine Kongruenz über ?? und das zugehörige Quotientenmonoid M (?; D) = ??=?I ist das von (?; D) erzeugte frei partiell kommutative Monoid oder einfach Spurmonoid. Die Elemente dieses Monoids nennen wir Spuren. Eine Spur t 2 M (?; D) besitzt das aus den Buchstaben eines Repräsentanten bestehende induzierte Alphabet ?(t) ? ? und (?; D)(t) bezeichnet das induzierte Abhängigkeitsalphabet (?(t); D \ (?(t) ? ?(t)). Mit jtj bezeichnen wir die Länge eines Repräsentanten und mit jtja die Anzahl der Vorkommen des Buchstaben a, seine a-Länge. N ist die Menge der natürlichen Zahlen, und mit [n] bezeichnen wir die Menge f1; : : : ; ng ? N für n 2 N . 2.1 Konkrete Beschreibungen Wir haben Spuren als Äquivalenzklassen über Worten definiert. Die Wahl eines Repräsentanten ist nicht eineindeutig. Deshalb betrachten wir Normalformen. Die historisch erste ist die von Foata [CF69]. Wir bezeichnen mit F die Menge fF ? ? j (F ? F ) n id? ? Ig der elementaren Schritte. Zu jedem elementaren Schritt F 2 F existiert eine Spur [F ] = Q a2F a 2 M (?; D). Das folgende Theorem etabliert die Foata-Normalform. Theorem 1 Sei t 2 M (?; D). Dann existiert genau eine Sequenz elementarer Schritte (F1; : : : ; Fr) 2 F? mit Q i2[r] Fi = t so, daß für alle 2 <= i <= r zwei abhängige Buchstaben (a; b) 2 D mit a 2 Fi?1 und b 2 Fi existieren. Q i2[r] ti notiert hier das Produkt t1 ? : : : ? tr. Eine natürliche Darstellung von Spuren sind Abhängigkeitsgraphen oder partiell geordnete Multimengen. Diese Repräsentationen besitzen auch eine einfache geometrische Interpretation. 7 Ein Abhängigkeitsgraph ist ein knotenbeschrifteter azyklischer Graph G = [V; E; >=] mit Knotenmenge V , Kantenmenge E ? V ? V und >= : V ?! ? als Beschriftung. Für alle Knoten x; y 2 V soll entweder eine Kante von x nach y oder von y nach x führen, falls (>=(x); >=(y)) 2 D. Gemeinsam mit der Verknüpfung [V1; E1; >=1] ? [V2; E2; >=2] = [V1 _[V2; E1 _[E2 _[f(x; y) 2 V1 ? V2 j (>=1(x); >=2(y)) 2 Dg; >=1 _[>=2] und dem neutralen Element [;; ;; ;] bilden die Abhängigkeitsgraphen ein Monoid. Das Symbol _[ bezeichnet die disjunkte Vereinigung. Wir bezeichnen das durch die Einpunkt- Abhängigkeitsgraphen [f1g; ;; >= : 1 7! a], a 2 ?, erzeugte Monoid vorläufig mit G (?; D). Entsprechend läßt sich der transitive Abschluß eines Abhängigkeitsgraphen als partiell geordnete Multimenge über den Buchstaben auffassen. Eine Multimenge M über ? ist eine Abbildung M : ? ?! N in die natürlichen Zahlen. Wir notieren M durch eine Aufzählung der Elemente mit Vielfachheiten und identifizieren stellenweise ein Element einer Multimenge mit einem einer gewöhnlichen Menge. Ist die Multimenge M mit einer partiellen Ordnung <= ? M ? M versehen, so sprechen wir von einer partiell geordneten Multimenge hM; <=i. Die mengentheoretischen Operationen [, \, n etc. und die Relationen wie ?, 2 etc. verwenden wir für Multimengen und geordnete Multimengen wie bei gewöhnlichen Mengen. Die partiell geordneten Multimengen bilden gemeinsam mit der leeren Menge h;; ;i und der Verknüpfung hM1; <=1i ? hM2; <=2i = hM1 _[M2; <=1 _[ <=2 _[f(a; b) 2 M1 ?M2 j (a; b) 2 Dgi ein Monoid. Das von den einelementigen partiell geordneten Mengen erzeugte Monoid bezeichnen wir vorläufig mit O(?; D). Die eineindeutige Fortsetzung der Abbildungen hG : [a] 7?! [f1g; ;; 1 7! a] bzw. hO : [a] 7?! hfag; f(a; a)gi zu Homomorphismen hG : M (?; D) ?! G (?; D) und hO : M (?; D) ?! O(?; D) liefert zwei Isomorphismen. Damit erhalten wir zwei weitere Darstellungen für endlich erzeugte frei partiell kommutative Monoide. Lemma 1 Das durch das Abhängigkeitsalphabet erzeugte frei partiell kommutative Monoid M (?; D) ist isomorph zu dem Monoid der Abhängigkeitsgraphen G (?; D) und zu dem Monoid der partiell geordneten Multimengen O(?; D). Zu einer Spur t = [a1 : : : an] 2 M (?; D) mit ai 2 ? für alle i 2 [n] wird der dazugehörige Abhängigkeitsgraph HG (t) gebildet, indem zunächst eine n-elementige Knotenmenge V = fv1; : : : ; vng (wir betrachten Isomorphieklassen von Graphen) so beschriftet wird, daß >=(vi) = ai gilt. Die Kantenmenge wird durch E = f(vi; vj) j i < j; (>=(vi); >=(vj)) 2 Dg festgelegt. Interpretiert man den reflexiven und transitiven Abschluß dieses Graphen als partiell geordnete Multimenge, so erhält man hO(t) = hM; <=i. Lemma 2 Die partielle Ordnung <= einer partiell geordneten Multimenge hO(t) = hM; <= i 2 O(?; D) ist der Schnitt über die Ordnung der Wortrepräsentanten von t 2 M (?; D), 8 <= = T w2t O(w). Dabei ist O(w) die durch die Reihenfolge der Buchstaben in w induzierte lineare Ordnung. Das heißt O(1) = ;, O(a) = f(a; a)g und O(uv) = O(u)[O(v)[(u? v) mit a1 : : : an ? b1 : : : bm = fa1; : : : ; ang ? fb1; : : : ; bmg, a; a1; : : : ; an; b1; : : : ; bm 2 ?. Für jede topologische Permutation ß der Spur hM; <=i ist aß(1) : : : aß(n), a1; : : : ; an 2 ? ein Wortrepräsentant von t = [a1 : : : an]. (Eine topologische Permutation ist eine bijektive Abbildung ß : [n] ?! [n] mit aß(i) < aß(i+1), für alle i 2 [n ? 1].) Im weiteren werden wir die Monoide M (?; D), G (?; D) und O(?; D) identifizieren. Das heißt, wir werden Elemente eines frei partiell kommutativen Monoids bis auf Isomorphie identifizieren. 2.2 Das Levi-Lemma Das Lemma von Levi für Wörter aus freien Monoiden ?? besitzt die folgende Verallgemeinerung. Lemma 3 (Levi-Lemma) Seien x; y; z; t 2 M (?; D) Spuren. Dann sind die folgenden Behauptungen zwei äquivalent. (i) xy = zt (ii) 9r; u; v; s 2 M (?; D) mit x = ru, y = vs, z = rv, t = us und uIv. Interessant ist das mit durch Äquivalenz (i) , (ii), zusammen mit der Existenz eines positiven Gewichtes, einen Homomorphismus w : M ! N mit w?1(0) = 1, ein Monoid M als frei partiell kommutativ charakterisiert wird. 2.3 Das Einbettungstheorem Eine konkrete Darstellung von M (?; D), die wir zur Beschreibung von Algorithmen verwenden werden, ist eine Einbettung in ein direktes Produkt freier Monoide. Bei der Konstruktion folgen wir dem kategoriellen Ansatz von Diekert [Die90b] und Fischer [Fis86]. Jedem Abhängigkeitsalphabet (?; D) ordnen wir (bijektiv) den ungerichteten, schlingenfreien Graphen G(?; D) = (?; D n id?) zu, D ? ?? 2 ? . Betrachten wir die Kategorie, in der die Objekte die endlichen ungerichteten schlingenfreien Graphen und die Morphismen h : (V; E) ?! (V 0; E 0) Abbildungen V ?! V 0 sind, die der Bedingung xy 2 E =) h(x)h(y) 2 E 0 für alle x; y 2 V genügen. Dann erhält man einen kontravarianten Funktor M in die Kategorie der Monoide (?; D n id?) 7?! M (?; D) h : (?; D? n id?) ! (?; D? n id?) 7?! M (h) : M (?; D?) ! M (?; D?); worin M (h) die eineindeutige Fortsetzung der Abbildung y 7?! Q x2h?1(y) x ist, y 2 ?. (Hier bezeichnet Q die Verknüpfung in M (?; D).) 9 Wir bezeichnen die kanonischen Projektionen M (?; D) ?! M (?; D \ (? ? ?)) auf ein von ? ? ? induziertes Teilalphabet mit ß?. Das ist der durch die Abbildung a 7! a für a 2 ? und a 7! 1 anderenfalls induzierte Homomorphismus. Für einelementige Alphabete ? = fag schreiben wir auch ßa für ßfag. Eine Überdeckung eines Abhängigkeitsalphabets (?; D) ist eine Familie A von Abhängigkeitsalphabeten, mit ? = [ (?;D?)2A ? und D = [ (?;D?)2A D?: Theorem 2 Sei (?; D) ein Abhängigkeitsalphabet und A eine Überdeckung von (?; D). Dann ist der Homomorphismus ß : M (?; D) ?! Y (?;D?)2A M (?; D?); t 7?! ? ß?(t) ? (?;D?)2A injektiv. Unter einer Clique C von einem Abhängigkeitsalphabet (?; D) verstehen wir in diesem Kontext ein Teilalphabet C ? ? mit der Eigenschaft C ? C ? D. Eine Cliquenüberdeckung von (?; D) ist eine Familie C von Cliquen so, daß ? = S C2C C und D = S C2C(C ? C). Da M (C; C ? C) ? = C? erhalten wir eine zur Formulierung von effizienten Algorithmen geeignete Darstellung für Spuren. Korollar 1 Sei (?; D) ein Abhängigkeitsalphabet und C eine Cliquenüberdeckung. Dann ist der Homomorphismus ß : M (?; D) ?! Y C2C C?; t 7?! ? ßC(t) ? C2C injektiv. Obgleich wir die verschiedenen Repräsentationen identifizieren, werden wir bei der Darstellung von Algorithmen die letztere bevorzugen, da zur Repräsentation bereits wohlbekannte Datenstrukturen, die Strings, existieren. Für Korrektheitsbeweise sind jedoch meistens Abhängigkeitgraphen bzw. partielle Ordnungen geeigneter, da sie ein intuitiveres Verständnis einer Beweissituation durch ihre geometrische Interpretation vermitteln. 10 3 Ersetzungssysteme In diesem Abschnitt führen wir Spurersetzungssysteme ein. Definition 1 (Spurersetzungssystem) Ein Spurersetzungssystem ist eine endliche binäre Relation R über einem frei partiell kommutativen Monoid M = M (?; D). Ein Spurersetzungssystem R ? M ?M definiert eine Derivations- oder Ableitungsrelation =)R ? M ? M via x =)R y, falls x = ulv; y = urv, für u; v 2 M und l ! r 2 R: Für (r; l) 2 R notieren wir kurz r ! l. Die iterierte Anwendung ist durch x 0 =)R x für alle x 2 M x n+1 =)R y falls ein z 2 M existiert, mit x n =)R z =)R y für alle n 2 N definiert. Mit ? =)R notieren wir die reflexive und transitive Hülle S n2N n =)R von =)R , und mit ? ()R die symmetrische, reflexive und transitive Hülle R ? (= [ ? =)R . Die Relation ? ()R ist eine Kongruenz über dem frei partiell kommutativem Monoid M . Wir notieren M =R für den Quotienten f[t] ? ()R j t 2 M g, mit [t] ? ()R = ft0 2 M j t ? ()R t0g und nennen zwei Ersetzungssysteme R und S äquivalent, wenn M =R ? = M =S. 3.1 Eigenschaften von Ersetzungssystemen Ein Spurersetzungssystem R ? M ? M ist (i) längenreduzierend, wenn für alle Regeln l ! r 2 R jlj > jrj gilt, (ii) gewichtsreduzierend, wenn ein Homomorphismus w : M ! N existiert, mit w?1(0) = f1g und w(l) > w(r) für alle Regeln l ! r 2 R, (iii) noethersch, wenn es keine unendlichen Derivationen t0 =)R t1 =)R t2 =)R : : : gibt und (iv) konfluent, wenn für alle difluenten Situationen t0 R ? (= t ? =)R t00 sich auf ein Element ^t reduzieren lassen, t0 ? =)R ^t R ? (= t00. (v) Ein Spurersetzungssystem besitzt die Church-Rosser-Eigenschaft, wenn ? ()R ? ? =)R ffi R ? (= . (vi) Es ist lokal konfluent, wenn R(= ffi =)R ? ? =)R ffi R ? (= . 11 Die Menge der reduziblen Spuren S (l;r)2R M ? l ? M bezeichnen wir mit Red(R), und die Menge ft 2 M j :9s : t =)R sg = M n Red(R) der irreduziblen Spuren bezeichnen wir mit Irr(R). Wir nennen das System normalisiert, wenn jede rechte Seite irreduzibel ist und jede linke Seite bzgl. aller anderen linken Seiten irreduzibel ist. Wir nennen das System vollständig, falls es konfluent und noethersch ist. Eine Links-Derivation ist eine Sequenz t = u1l1v1 =)R u1r1v1 = u2l2v2 =)R : : : : : : u =)R n?1rn?1vn?1 = unlnvn =)R t0 mit ui 2 Irr(R), (li; ri) 2 R für alle i 2 [n]. Es ist bekannt, daß Konfluenz lokale Konfluenz impliziert. Es ist unentscheidbar, ob ein Spurersetzungssystem noethersch ist. Ist ein (abstraktes) Ersetzungssystem noethersch, dann ist Konfluenz sogar mit lokaler Konfluenz äquivalent. Zu jedem vollständigen Ersetzungssystem existiert ein äquivalentes normalisiertes vollständiges Ersetzungssystem. Wir untersuchen die folgenden zentralen Fragestellungen, das Konfluenzproblem und das Normalformproblem. Problem 1 (Konfluenzproblem) Gegeben sei ein festes Spurersetzungssystem R über einem Spurmonoid M . Ist R konfluent? Das konstruktive Problem: " Gegeben sei ein Spurersetzungssystem R über einem Spurmonoid M . Konstruiere ein äquivalentes vollständiges Ersetzungssystem.\ wurde bereits von Diekert durch Verallgemeinerung des Algorithmus von Knuth und Bendix auf den partiell kommutativen Fall bearbeitet [Die87]. Dieser Algorithmus benutzt intensiv Normalformberechnungen, was uns zu der folgenden Fragestellung führt. Problem 2 (Normalformproblem) Welche Komplexität hat das berechnen irreduzibler Elemente? Sei R ein noethersches Spurersetzungssystem über einem Spurmonoid M und eine Spur t 2 M gegeben. In welcher (nicht-uniformen) Zeitkomplexität ist es möglich eine irreduzible Spur ^t 2 Irr(R) mit t ? =)R ^t zu ermitteln. Um später Komplexitätsaussagen treffen zu können definieren wir `R(t) = maxfn 2 N j t n =)R t0g als die Anzahl der maximal möglichen Ableitungsschritte (von t aus). Mit dR(n) bezeichnen wir den Wert maxf`R(t) 2 N j jtj = n; t 2 M g. Dann ist dR total, falls R noethersch ist und dR 2 ?(n), falls R 6= ;. Für nicht-leere gewichtsreduzierende Systeme ist dR 2 ?(n). Fortan sei jedes Spurersetzungssystem noethersch, da sonst Derivationen existieren, in denen kein irreduzibles Element in endlich vielen Schritten erreicht wird, und wir effektive Verfahren betrachten. 12 4 Konfluenz von Spurersetzungssystemen Die Konfluenz von längenreduzierenden Wortersetzungssystemen modulo Kommutationsregeln ist im allgemeinen nicht entscheidbar, wie Narendran und Otto [NO88] feststellten. Wir geben hier einen neuen einfachen und direkten Beweis für die Unentscheidbarkeit, der nicht unmittelbar auf der Unentscheidbarkeit der Präperfektheit basiert und illustriert, wie eine Berechnung einer Turingmaschine durch einen Konfluenztest simuliert werden kann. Genauer konstruieren wir zu einer Turingmaschine M und einem Wort w ein endliches längenverkürzendes Ersetzungssystem R über fa; b; $; fig?=$fi = fi$ mit der Eigenschaft, daß w = 2 L(M) genau dann gilt, wenn R konfluent ist. Insbesondere gelang es zu zeigen, daß das betrachtete Problem bereits für ein Alphabet mit vier Buchstaben und einer Kommutationsregel unentscheidbar ist. 4.1 Unentscheidbarkeit Unter einer deterministischen Turingmaschine mit einem einseitig unendlichem Band verstehen wir ein Tupel M = (Q; ?; ?; ffi; q0; F; b) , wobei ? ? ? das Eingabealphabet, ? das Bandalphabet und Q die Zustandsmenge ist. ffi ist eine partiell definierte Transitionsfunktion Q ? ? ?! Q ? (? n f bg) ? fC; Bg, q0 2 Q ist der Startzustand und F ? Q sind die Finalzustände. b 2 ?n? bezeichnet das Blanksymbol. Dabei beschreibt ffi(q; a) = (q0; a0; B), daß die Maschine bei Lesen des Zeichen a in Zustand q das Zeichen a0 schreibt, in Zustand q0 wechselt und den Kopf ein Zeichen nach rechts bewegt. ffi(q; a) = (q0; a0; C) beschreibt eine analoge Aktion mit einer Linksbewegung des Kopfes. Eine Konfiguration ist ein Tupel (u; q; v), wobei die Maschine in Zustand q ist, sich der Kopf auf dem ersten Symbol von v befindet und die Bandinschrift uv 2 (?nf bg)? gefolgt von einer Blanksequenz ist. Mit 7??M bezeichnen wir die Einschritttransitionsrelation (u; q; av) 7??M (ua0; q0; v) falls ffi(q; a) = (q0; a0; B); (ub; q; av) 7??M (u; q0; ba0v) falls ffi(q; a) = (q0; a0; C); b 2 ? und mit ? 7??M den reflexiven transitiven Abschluß. Mit L(M) bezeichnen wir die akzeptierte Sprache fw 2 ?? j (1; q0; w) ? 7??M(u; qf ; v); qf 2 Fg. Ohne Einschränkung haben genau die akzeptierenden Konfigurationen (u; qf ; v), qf 2 F keine Folgekonfiguration, d.h. wir normieren die Maschine so, daß sie auf nichtakzeptierten Eingaben nicht terminiert, indem wir einen neuen Zustand f = 2 Q einführen und die Transitionsfunktion für Zustände q = 2 F wie folgt erweitern: ffi(q; a) = ? ffi(q; a) falls schon definiert (f; a0; B) anderenfalls, a0 6= b, a0 beliebig 13 Wir erhalten eine Maschine, die ein Wort w 2 L(M) durch Halten in endlich vielen Schritten akzeptiert und für w = 2 L(M) nicht terminiert. Ferner nehmen wir an, daß keine Blanksymbole geschrieben werden. Zu einer solchen Turingmaschine M konstruieren wir ein simulierendes längenreduzierendes Ersetzungssystem R über dem Alphabet Q _[ ? _[f$g. Für Rechtsbewegungen führen wir die Regeln bqa$$ !R ba0q0; ffi(q; a) = (q0; a0; B); bq b$$ !R ba0q0 b; ffi(q; b) = (q0; a0; B) ein, und für Linksbewegungen fügen wir die Regeln bqa$$ !R qba0; ffi(q; a) = (q0; a0; C) bq b$$ !R qba0 b; ffi(q; b) = (q0; a0; C) für alle a; b 2 ? n f bg hinzu. Weiter enthält das Ersetzungssystem die Regeln ab$$ !R a$b und a$b$$ !R a$$b für a; b 2 ?. Sie erlauben einen Transport der $-Symbole in einem Wort nach links. Bei der Simulation eines Berechnungsschrittes werden immer zwei $-Symbole konsumiert und ein Transport eines $-Symbols um ein Zeichen kostet ein $. Lemma 4 (i) R ist konfluent über (Q [ ? [ f$g)?. (ii) Es gilt (u; q; v) ? 7??M(u0; q0; v0) genau dann, wenn eine Zahl n 2 N existiert, mit uqv b$n ? =)R u0q0v0 1$v0 2$ : : : v0 k b$ und v0 = v0 1v0 2 : : : v0 k, v0 1; : : : ; v0 k 2 ? n f bg. (iii) Es ist w 2 L(M) genau dann, wenn eine natürliche Zahl n 2 N existiert mit q0w b$n ? =)R uqfv b$$ 2 Irr(R); qf 2 F und v b$$ 2 Irr(R). Beweis: Es ist wohlbekannt, wie man für noethersche Wortersetzungssysteme die Konfluenz mit Hilfe kritischer Paare testen kann, siehe [Jan88]. Im vorliegenden Fall ist die Menge der kritischen Paare offensichtlich leer. (Beachte: Die Maschine ist deterministisch.) Die zweite Aussage folgt unmittelbar aus der Konstruktion mit Induktion. Die dritte Behauptung ist evident, da in uqfv b$$ wegen der Normierung der Turingmaschine kein $ konsumiert werden kann. Seien 0, ff, fi und fl vier neue Symbole. Das neue Alphabet sei also ? = fff; fi; fl; 0; $g [ ? [ Q. Erweitern wir jetzt R noch um die Regeln x0 !R 0 und 0x !R 0 für alle Symbole x 2 ? so bleibt das System konfluent, da w ? =)R 0 für alle w 2 ??0??. 0 ist ein absorbierendes Symbol. Zu einem Wort w 2 ?? definieren wir das Regelsystem R(w) durch Erweiterung von R um die drei Regeln ffjwj+2fi !R q0w b fifl !R 0 bfl !R 0: 14 Bemerkung 1 (i) R(w) ist konfluent, da sich alle kritischen Situationen auflösen lassen: 0 R ? (= q0w0 R(= q0w bfl R(= ffjwj+2fifl =)R ffjwj+20 ? =)R 0 (ii) w = 2 L(M) genau dann, wenn für alle n 2 N q0w b$nfl ? =)R uqv bfl =)R uqv0 ? =)R 0 gilt. Sei jetzt fi und $ unabhängig, d.h. fi$ = $fi. Betrachten wir die kritischen Situationen über dem erzeugten Spurmonoid M (?; D?) mit ? = Q [ ? [ fff; fi; fl; $; 0g und D? = ?2 n f($; fi); (fi; $)g ffjwj+2fi$nfl = ffjwj+2$nfifl; so läßt sich die rechte Seite zu 0 via ffjwj+2$nfifl =)R ffjwj+2$n0 ? =)R 0 ableiten. Die linke Seite läßt sich via ffjwj+2fi$nfl =)R q0w b$nfl ableiten. Das entstandene Element läßt sich nur dann zu 0 für alle n 2 N ableiten, falls w = 2 L(M ): q0w b$nfl ? =)R uqv bfl =)R uqv0 ? =)R 0: Andernfalls existiert eine natürliche Zahl n 2 N und eine Derivation ffjwj+2fi$nfl =)R q0w b$nfl ? =)R uqfv b$2fl 2 Irr(R) zu einem irreduziblen Wort verschieden von 0. Wir erhalten: Lemma 5 Wenn R ? M ? M konfluent ist, dann gilt w = 2 L(M). Für die Umkehrung benötigen wir eine konkrete Darstellung von Faktorisierungen, um weiter Aussagen machen zu können. Diese entnehmen wir aus dem Anhang. Ein Faktorvorkommen i : l = hMl; <=li ?! t = hMt; <=ti von l in der Spur t ist eine ordnungserhaltende Inklusion i : Ml ,! Mt so, daß sich t durch u ? i(l) ? v faktorisieren läßt2. Das folgende im Anhang bewiesene Lemma stellt eine Charakterisierung für Faktorisierungen bereit. Lemma 6 Seien t; l 2 O(?; D) Spuren mit t = hMt; <=ti und l = hMl; <=li. Weiter sei Ml ? Mt eine Teilmultimenge und <=l die auf Ml induzierte partielle Ordnung <=t \ (Ml ?Ml). Dann ist l ein Faktor in t (t = ulv für u; v 2 M (?; D)) genau dann, wenn für alle Elemente a; b 2 Ml und c 2 Mt gilt a <=t c <=t b =) c 2 Ml. 2Viele dieser Begriffe werden im Anhang näher erläutert. Dort befinden sich auch visuelle Veranschaulichungen und technische Beweise. 15 Beweis: Sei l ein Faktor in t = ulv 2 O(?; D) mit Spuren u = hMu; <=ui, v = hMv; <=vi und t = hMt; <=ti. Daraus folgt Mt = Mu _[Mv _[Ml. Seien a; b 2 Ml und c 2 Mt mit a <=t c <=t b. Dann gilt a <=t c =) c = 2 Mu und c <=t b =) c = 2 Mv. Also liegt c in Ml. Sei nun l = hMl; <=li eine durch <=t partiell geordnete Teilmenge von t so, daß für alle a; b 2 Ml a <=l c <=l b =) c 2 Ml gilt. Liegen alle minimalen und maximalen Elemente von t in Ml, so ist t = l ein Faktor (u = v = 1). Anderenfalls existiert ein minimaler (oder ein maximaler) Buchstabe a in t, der nicht in l vorkommt. Damit faktorisiert sich t = at0 (oder t = t0a) und t0 enthält (mit Induktion über die Kardinalität von Mt) den Faktor l. Das heißt t = au0lv0 (oder t = u0lv0a). Man beachte, die Divisionsrelation ist noethersch. Seien l und t wie im Lemma und sei i wie oben beschrieben, dann führt die Charakterisierung zu einer Aufteilung der Spuren in (i) den Teil hi(l); <=0 ti, der das Vorkommen enthält (ii) den Teil, der vor dem Vorkommen liegt pret(i) = hfa 2 Mt j a = 3 eine natürliche Zahl. Dann repräsentiert ein C?-Baum T das Wort w = w1 : : : wn mit wi 2 C, i 2 [n], wenn die Blätter die Buchstaben wi 2 C sind und der geordnete Baum den folgenden Struktureigenschaften genügt. (i) Jeder innere Knoten besitzt mindestens 2 und höchstens m Kinder. (ii) Jedes Blatt besitzt dieselbe Distanz zum Wurzelknoten. (iii) Die Ordnung der Blätter entspricht der Ordnung der Buchstaben in w. Die lineare Ordnung O(w) (w1 < w2 < : : : < wn) der Buchstaben wi 2 ?, i 2 [n], in w = w1 : : : wn legt in natürlicher Weise die Ordnung auf den Blättern fest und läßt sich auf zu einer partiellen Ordnung auf den inneren Knoten wie folgt fortsetzen. Ein innerer Knoten ist kleiner als ein anderer, wenn alle nachfolgenden Knoten des ersten Knoten kleiner als die des zweiten sind. Weiter besitzt ein C?-Baum mit Knotenmenge V zwei Beschriftungen >=1 : V ?! P(C) und >=2 : V ?! P(LR): Sie sollen eine effiziente Berechnung von Faktorisierungen, Faktorvorkommen und Konkatenationen ermöglichen. Dazu genügen die Beschriftungen den folgenden Bedingungen: (i) Jeder Knoten v in T ist via >=1 mit dem Alphabet des durch den Unterbaum (mit Wurzel v und Blattsequenz w) induzierten Alphabets >=1(v) = ?(w) ? C beschriftet. (ii) Jeder Knoten v in T ist via >=2 mit einer Teilmenge der linken Seiten l 2 LR beschriftet, deren Projektion ßC(l) 2 C? nf1g in dem durch v induzierten Teilwort beginnt. Genauer besitzt der durch v induzierte Teilbaum ein zum Buchstaben a korrespondierendes Blatt, so daß das durch den gesamten Baum repräsentierte Wort w sich wie folgt faktorisieren läßt w = u ? al0 C ? v mit ßC(l) = lC = al0 C . Eine Spur t 2 M wird durch eine Baumfamilie (TC)C2C repräsentiert, wenn für alle C 2 C der C?-Baum TC in der Familie das Wort tC repräsentiert. Die >=2-Beschriftungen sollen dann genau die linken Seiten l 2 LR enthalten, bei denen sich die Faktorisierungen auf der repräsentierten Projektion zu einer Faktorisierung der repräsentierten Spur fortsetzen läßt. D.h. für die repräsentierte Projektion w = tC 2 C? existiert ein Faktorvorkommen i : l ?! t mit w = w0i(a)l0 Cw00 genau dann, wenn jeder Vorfahre des Blattes, das zum Buchstaben i(a) korrespondiert, mit Mengen, die l enthalten, beschriftet ist. 21 Die Idee ist, daß die Baumstruktur mit der >=1-Beschriftung eine effiziente Rekonstruktion der transitiven Abhängigkeiten erlaubt und, daß die Baumstruktur mit der >=2- Beschriftung eine effiziente Berechnung von Faktorisierungen ulv mit l 2 LR ermöglicht. Formal sei TC ein Baum aus der Familie. Sei w0 das von dem Unterbaum mit Wurzel v induzierte Teilwort von w, dann definieren wir >=1(v) = ?(w0) >=2(v) = fl 2 LR j 9i : l ?! t Faktorvorkommen mit i(ßC(l)) = al0 C [(l0 C = l00 C l000 C ^ w0 = xal00 C ^ w = x0w0l000 Cy0) _ w0 = xal0 Cy]g Wir zitieren an dieser Stelle ein Korollar, in dem Faktorisierungen charakterisiert werden (siehe Anhang A). Korollar 3 Seien t; l 2 M (?; D). Dann ist l = hMl; <=li ein Faktor in t = hMt; <=ti genau dann, wenn (i) l ein Vorkommen in t ist, d.h. für alle Cliquen C; C 0 2 C mit C \ ?(l) 6= ; und C 0 \ ?(l) 6= ; existieren Wörter uC ; vC 2 C? mit tC = uC lCvC und ß0 C(uC) = ßC(uC0), sowie (ii) für alle verbleibenden Cliquen C 2 C, ?(l) \ C = ; existieren Faktorisierungen uCvC = tC so, daß die Beziehung ßC(uC0) = ßC0(uC) für alle C; C 0 2 C erfüllt ist. Sei t 2 M , l 2 LR und C = fC1; : : : ; Ckg mit ?(l) \ Cj 6= ; für 1 <= j <= i und ?(l) \ Cj = ; für i + 1 <= j <= k. Dann gilt t = x ? l ? y genau dann, wenn 0 B B B B B B B @ tC1 ... tCi tCi+1 ... tCk 1 C C C C C C C A = 0 B B B B B B B @ xC1 ... xCi xCi+1 ... xCk 1 C C C C C C C A ? 0 B B B B B B B @ lC1 ... lCi 1 ... 1 1 C C C C C C C A ? 0 B B B B B B B @ yC1 ... yCi yCi+1 ... yCk 1 C C C C C C C A = 0 B B B B B B B @ xC1 ? aC1 l0 C1 ? yC1 ... xCi ? aCi l0 Ci ? yCi xCi+1 ? yCi+1 ... xCk ? yCk 1 C C C C C C C A und jeder Vorfahre v in der repräsentierenden Datenstruktur eines zu einem der Buchstaben aC1 ; : : : ; aCi korrespondierenden Blattes mit einer Menge >=2(v), die l enthält, beschriftet ist, und für 1 <= j; j 0 <= i die Bedingung jxCj ja = jxCj0 ja für alle a 2 C\C 0 \?(l) erfüllt ist. Die folgende Abbildung illustriert die Baumstruktur. 22 w0 = w0 1 : : : w0 m w0 n w0 1 : : : wn TC l 2 >=2(v), falls i : l ! t Faktorvorkommen ist und v w = w1 : : : wn = xw0y tC = w = w00w0w000 mit w0w000 = x0lCy0, lC = al0 C und w0 = x0i(a)y00 v >=1(v) = fw0 1; : : : ; w0 ng w1 : : : : : : Die Höhe HEIGHT(v) = HEIGHT(T ) eines Baumes T mit Wurzel v ist rekursiv definiert. Jedes Blatt v besitzt die Höhe HEIGHT(v) = 1 und die Höhe eines inneren Knoten v berechnet sich rekursiv HEIGHT(v) = 1 +maxc2children(v) HEIGHT(c). (Entsprechend sind Tiefe und Distanz definiert.) Aus den strukturellen Eigenschaften des Baumes folgt eine Schranke für die Pfadlängen zur Wurzel. Lemma 9 Sei T ein C?-Baum der Höhe h, dann liegt die Anzahl der Knoten von T zwischen 2h+1 ? 1 und mh+1?1 m?1 . Die Länge des repräsentierten Wortes liegt zwischen 2h und mh. Damit ist die Distanz von einem Buchstaben zur Wurzel proportional zu log n. Beweis: Sei n = n(h) die Anzahl der Knoten. Die Anzahl der Knoten mit Wurzeldistanz i liegt zwischen 2i und mi. Es gilt 2h+1 ? 1 = h X i=0 2i <= n(h) <= h X i=0 mi = mh+1 ? 1 m? 1 Sei C, wie oben beschrieben, eine Cliquenüberdeckung. Dann repräsentiert das C?- Baumtupel (TC)C2C die Spur t dann, wenn für alle C 2 C der Baum TC das Wort ßC(t) repräsentiert (mit korrekter Beschriftung). Blätter, die zu Buchstaben korrespondieren, die das gleiche Urbild bezüglich des Projektionshomomorphismus ß : M ?! Q C2C C? haben, sollen sich referenzieren. Diese strukturellen Eigenschaften ermöglichen es beispielsweise in logarithmischer Zeit zu entscheiden, ob ein durch Positionen in den Wörtern tC , C 2 C bzw. via Blättern in TC beschriebenes Vorkommen ein Faktor ist. Für den Beweis beschreiben wir die Methoden, um einige (primitive) Prädikate entscheiden zu können. Der erste Algorithmus berechnet zu einem gegebenen mit dem Buchstaben a beschrifteten Blatt das, falls existent, größte sich links von v befindliche mit b beschriftete Blatt. D.h. für einen das Wort w = w0aw00 repräsentierenden C?-Baum T und einen den Buchstaben a repräsentierenden Knoten v soll der Knoten, der das letzte b in w0 repräsentiert, 23 berechnet werden. (Man beachte, daß ein lineares sondieren auch lineare Zeit- und nicht logarithmische Zeitkomplexität besitzt.) Ein geeignetes Auf- und wieder Absteigen in der Baumstruktur ist jedoch in der angestrebten Zeitschranke möglich. Algorithm pred(T; v; b) Comment Input: a nonempty C?-tree T and a leaf v representing a letter a. Output: the right-most b labeled leaf to the left of v. Method if v is the root of T then return no predecessor else v0 v v the father of v0 while b = 2 >=1(v00) for a brother to the left of v and v is not the root do v0 v v father of v0 end while if v0 has no b-labeled brother to the left then return no b-labeled predecessor else while v is no leaf do let v be the right-most b-labeled brother to the left return (v) end if end if end Method Lemma 10 Sei T ein C?-Baum, v ein mit a beschriftetes Blatt und b 2 C ein Buchstabe. Dann ist pred(T; v; b) das mit b beschriftete Blatt (falls existent), das sich links von v befindet, so daß kein weiteres mit b beschriftetes Blatt sich zwischen v und pred(T; v; b) befindet. Beweis: Repräsentiere der C?-Baum T das Wort w 2 C? und sei v der Blattknoten, der den Buchstaben a in w = w0aw00 repräsentiert. Ist v die Wurzel, so gilt w = a und das Resultat existiert nicht. In der ersten Schleife wird der Pfad (v; v1; v2; : : : ; vk) von v in Richtung Wurzel so lange erforscht, bis entweder die Wurzel erreicht ist oder die Beschriftung des letzten Knoten >=1(vk) den Buchstaben b enthält. Es gilt, daß die Variable v den Wert vi beim i-ten Durchlauf hat, wenn vi der i-te Vorfahr von dem Eingabeknoten v ist. Weiter ist v0 der (i ? 1)-te Vorfahr. Existiert kein Vorfahr vk so, daß einer der linken Brüder von vk?1 mit einer Menge, die b enthält, beschriftet ist, dann gilt b = 2 ?(w0) und der Algorithmus berechnet das richtige Resultat. Existiert ein solcher Bruder, so gelten die folgenden Invarianten für die zweite Schleife: b 2 >=1(v) und, wenn v0 k?i der Wert von v in der i-ten Iteration ist, dann gilt HEIGHT(vi) = HEIGHT(v0 i), v0 i ist Vater von v0 i?1 und es existiert kein Knoten x mit der 24 gleichen Höhe, der sich links von v0 i und rechts von vi befindet und mit einer Menge die b enthält beschriftet ist. Ansonsten wäre x ein Nachkomme eines Bruders von vk?1, der sich rechts von v0 k?1 befindet, was im Widerspruch zur Wahl von v0 k?1; : : : ; v0 k?i+1 steht. Man beachte b = 2 >=1(vi) für alle i < k. Damit ist nach k Iterationen das Resultat der der Semantik entsprechende b repräsentierende Knoten mit w0 = u0bu00 und b = 2 ?(u00). Mit dieser Technik sind wir in der Lage, in einer Spur t = ubvaw 2 M das b-Vorkommen (a; b) 2 D zu finden mit b = maxfb 2 Mt j b =1 Beschriftungen) fag fag fag fbg fbg fbg fbg fag fa; bg fa; bg fa; bg fa; bg a b a a b a b b Die >=1 Beschriftungen von Tfa;bg und Tfa;eg (nur mit >=2 Beschriftungen) 28 a a Die >=2 Beschriftungen von Tfa;bg a e a e e fl1g fl3g fl1; l3g fl3g fl3g fl1g fl3g ; ; ; ; 5.3 Der Datentyp Wir beweisen konstruktiv durch Angabe von Algorithmen, daß es effektiv und effizient möglich ist, diese Bäume aufzubauen, Teile zu löschen, sie zu zerlegen und wieder zusammenzufügen. Dazu führen wir die Operationen CONCATENATE, SPLIT, DELETE und INSERT ein, die vorerst nur die Beschriftung >=1 und die strukturellen Eigenschaften erhalten. Hiernach stellen wir eine Methode bereit, um die verbleibende Beschriftung zu korrigieren. Dieses Vorgehen ermöglicht den Entwurf des Reduktionsalgorithmus. INSERT Um einen Buchstaben a 2 C in einen das Wort w repräsentierenden C?-Baum an der Stelle, die durch das Präfix w0 von w beschrieben sei, einzufügen, verwenden wir die folgende Methode. Sei b das zum letzten Buchstaben in w0 korrespondierende Blatt. Falls kein solches Blatt existiert (w0 = >=), so ist das neue Blatt der erste (kleinste) Buchstabe. Dann fügen wir neben b das neue Blatt an und restaurieren die strukturellen Eigenschaften entlang des Pfades zur Wurzel. Besitzt ein Knoten zu viele Kinder, so wird er in zwei Knoten geteilt und rekursiv weiter verfahren. Das Einfügen des neuen Blattes geschieht damit bottom-up. Das ermöglicht die effiziente Wiederherstellung der strukturellen Eigenschaften. Algorithm INSERT (T; a; b) Comment Input: a nonempty C?-tree T and a new letter a that should be inserted at the right of b. Output: a revisted C?-tree with the new leaf a. Method if T consists of a single leaf c then create a new root r if there exists b with b <= a, i.e., a will not be minimal then make a the left child of r and c the right child else make c the left child of r and a the right child end if label r by >=1(r) = S c2children(r) >=1(c) else if there exists b with b <= a, i.e., a will not be minimal then let f be the father of the leaf b make a be a child of f immedeately to the right of b else let c be the left-most leaf in T 29 let f be the father of the leaf c make a be a child of f immedeately to the left of c end if relabel f by >=1(f) = S c2children(f) >=1(c) if f has less than m children then propagate the labeling by PROPAGATE1(f;T ) else f has m children incorporate the vertex f with its m + 1 children with INCORPORATE(f;T ) end if end if end Method Für ein a repräsentierendes Blatt v gilt (ohne das es in den Beschreibungen ausgeführt ist) >=1(v) = a. Die Prozedur INCORPORATE stellt die strukturellen Eigenschaften rekursiv wie folgt her. Procedure INCORPORATE (v; T ) Comment Input: a nonempty ordered and labeled tree T containing one vertex v with m + 1 children. Output: a corresponding C?-tree. Method create a new vertex v0 make the two right-most children of v the left and the right child of v0 relabel v0 by >=1(v0) S c2children(v0) >=1(c) relabel v by >=1(v) S c2children(v) >=1(c) if v has no father in T then create a new root r make v0 the left child and v the right child of r label r by >=1(r) S c2children(r) >=1(c) else let f be the father of v make v0 a child of f immedeately to the right of v relabel f by >=1(f) S c2children(f) >=1(c) if f now has m children then INCORPORATE(T; f) else propagate the labeling by PROPAGATE1(T; f) end if end if end Method Lemma 14 Sei T ein geordneter Baum und v ein innerer Knoten in T der Tiefe t. Weiter sollen alle Knoten, die sich nicht auf dem Pfad von v zur Wurzel von T befinden, C?-Bäume induzieren und alle inneren Knoten außer v zwischen 2 und m Kinder besitzen. Der Knoten v besitzt genau m + 1 Kinder. Dann liefert die Prozedur INCORPORATE(v;T ) einen C?-Baum, der das selbe Wort wie T repräsentiert, mit korrekter >=1-Beschriftung in O(t) Zeiteinheiten. 30 Beweis: Die Prozedur spaltet den Knoten v mit m + 1 Nachfolgern in zwei Knoten mit mindestens 2 und höchstens m ? 1 Knoten auf. Dabei wird ein neues Kind des Vaterknoten f von v generiert. Hatte dieser Knoten bereits m Kinder, so restauriert diese Prozedur rekursiv die Struktureigenschaft und die Beschriftung. Hat dieser Knoten weniger als m Nachfolger, so besitzt der Baum bereits die Struktureigenschaft und die Prozedur PROPAGATE1 aktualisiert die >=1-Beschriftung des Baumes. Die Ordnung auf den Blättern bleibt erhalten. Die Prozedur PROPAGATE1 vererbt die korrekte Beschriftungsinformation auf dem Pfad zur Wurzel. Procedure PROPAGATE1 (T; v) Comment Input: a wrong labeled C?-tree T with a vertex v. Output: a revisted C?-tree. Method if v is the root then terminate else let f be the father of v relabel f by >=1(f) = S c2children(f) >=1(c) PROPAGATE1(T; f) end if end Method Lemma 15 Sei T ein geordneter Baum und v ein innerer Knoten in T mit Tiefe t. Weiter sollen alle Knoten v0, die sich nicht auf dem Pfad von v zur Wurzel von T befinden, mit dem Blattalphabet >=1(v0) des durch v0 induzierten Baumes beschriftet sein. Dann liefert die Prozedur PROPAGATE1(T; v) einen C?-Baum mit gleicher Ordnung und korrekter >=1-Beschriftung in O(t) Zeiteinheiten. Beweis: Wir zeigen die folgende Invariante für die Datenstruktur: Für alle inneren Knoten v gilt >=1(v) = [ c2children(v) >=1(c): Sei children(v) = fv1; : : : ; vkg und sei wi 2 C? das von Knoten vi induzierte Teilwort von w = xiwiyi, i 2 [k], und w0 das von v induzierte Teilwort w1 : : : wk. Dann gilt ?(wi) = >=1(vi), w0 = w1 : : : wk und damit ?(w0) = S i2[k] ?(wi) = S i2[k] >=1(vi). Korollar 4 Sei T ein das Wort w repräsentierender C?-Baum, w0 ein Präfix von w = w0w00 und b der letzte Buchstabe von w0 oder w0 = 1. Dann berechnet der Algorithmus INSERT(T; a; b) einen C?-Baum, der das Wort w0aw00 repräsentiert in O(log jwj) Zeiteinheiten. Man beachte, daß die >=2-Beschriftungen bis jetzt noch nicht betrachtet wurden. 31 DELETE Analog ist der Algorithmus DELETE zum Entfernen des Blattes a formuliert. Algorithm DELETE (T; a) Comment Input: a nonempty C?-tree T with a leaf letter a that should be removed. Output: a revisted C?-tree without the leaf a. Method if T consists of a single leaf c then delete this leaf and return the empty tree else let f be the father of a delete the leaf a relabel f by >=1(f) = S c2children(f) >=1(c) if f has less than 2 children then REMOVE(f;T ) else propagate the labeling by PROPAGATE1(f;T ) end if end if end Method Die Prozedur REMOVE stellt die strukturellen Eigenschaften invers zu INCORPORA- TE wieder wie folgt her. Procedure REMOVE (v; T ) Comment Input: a nonempty ordered and labeled tree T containing one vertex v with only 1 child. Output: a corresponding C?-tree. Method if v is the root of T then delete v and return the empty tree else let f be the father of v if v has a immediate brother v0 with more than 2 children then if v0 is the left brother of v then let the right-most child of v0 be now the left-most child of v else let the left-most child of v0 be the right-most child of v end if relabel v by >=1(v) S c2children(v) >=1(c) relabel f by >=1(f) S c2children(f) >=1(c) relabel v0 by >=1(v0) S c2children(v0) >=1(c) propagate the labeling by PROPAGATE1(v;T ) and PROPAGATE1(v0;T ) else let v0 be a brother of v with 2 children if v0 is the left brother of v then let the child of v be now the left-most child of v0 else let the child of v be the right-most child of v0 32 end if delete the vertex v relabel v0 by >=1(v0) = S c2children(v0) >=1(c) relabel f by >=1(f) = S c2children(f) >=1(c) if f now has only one child then REMOVE(T; f) else propagate the labeling by PROPAGATE1(T; f) end if end if end if end Method Lemma 16 Sei T ein geordneter Baum und v ein innerer Knoten in T der Tiefe t. Weiter sollen alle Knoten, die sich nicht auf dem Pfad von v zur Wurzel von T befinden, C?-Bäume induzieren und alle inneren Knoten außer v zwischen 2 und m Kinder besitzen. Der Knoten v besitzt genau einen Kind. Dann liefert die Prozedur REMOVE(v;T ) einen C?-Baum, der dasselbe Wort repräsentiert, mit korrekter >=1-Beschriftung in O(t) Zeiteinheiten. Beweis: Analog dem Beweis zu Lemma 14. Korollar 5 Sei T ein das Wort w repräsentierender C?-Baum und w0a ein Präfix von w = w0aw00. Dann berechnet der Algorithmus DELETE(T; a) einen C?-Baum, der das Wort w0w00 repräsentiert in O(log jwj) Zeiteinheiten. CONCAT Betrachten wir als nächste Operation die Primitive CONCAT. Seien T1 und T2 zwei C?-Bäume, die die Wörter w1 und w2 repräsentieren. Die Primitive CONCAT soll einen C?-Baum T berechnen, der das Wort w = w1w2 repräsentiert. Sei h1, die Höhe von T1 und h2 die von T2. Die Prozedur IMPLANT baut T1 in T2 oder T2 in T1 ein, abhängig von der Höhendifferenz der Bäume. Sei h = minfh1; h2g die Höhe von dem Knoten v im Randpfad des höheren Baumes. Ein Randpfad ist der Pfad beginnend beim minimalen Blatt (bezüglich der Blattordnung) von T2 zur Wurzel von T2 beziehungsweise der Pfad, der beim maximalen Blatt von T1 beginnt und an der Wurzel von T1 endet. Ist der Knoten der Höhe h auf dem (längeren) Pfad gefunden, wird der Wurzelknoten des kleineren Baums als neues Kind eingefügt. Die Alphabetbeschriftung und die Struktureigenschaften werden wie beim Einfügen eines Knotens restauriert. Sind beide Bäume gleich hoch, so wird einfach eine neue Wurzel mit richtiger Beschriftung und den alten Wurzeln als Kindern kreiert. Den trivialen Fall, wenn einer der beiden Bäume leer ist, betrachten wir nicht. Algorithm IMPLANT(T1;T2) Comment Input: two nonempty C?-trees T1 and T2. 33 Output: a revisted C?-tree representing the concatenation of the yields of T1 and T2. Method if HEIGHT(T1) = HEIGHT(T2) then create a new root r make the root of T1 the right children of r and make the root of T2 the left children of r relabel r by >=1(r) S c2children(r) >=1(c) else assume HEIGHT(T1) > HEIGHT(T2) otherwise interchange T1 and T2 and interchange " left\ with " right\ in let v be the right-most path of T1 such that DEPTH(v) = HEIGHT(T1) ? HEIGHT(T2) let f be the father of v make the root of T2 to the right-most child of f relabel f by >=1(f) = S c2children(f) >=1(c) if f has more than m children then INCORPORATE(f;T ) else propagate the labeling by PROPAGATE1(f;T ) end if end if end Method Lemma 17 Sei T1 ein das Wort w1 repräsentierender C?-Baum der Höhe h1 und T2 ein das Wort w2 repräsentierender C?-Baum der Höhe h2. Dann kombiniert diese Prozedur die Bäume zu einem C?-Baum, der das Wort w1w2 repräsentiert, in O(jh1 ? h2j) Zeiteinheiten unter der Annahme, daß v nicht bestimmt werden muß. Beweis: Die Korrektheit ergibt sich aus der Semantik der Prozeduren INCORPORATE und PROPAGATE1. Die Zeitschranke ist offensichtlich, da je Knoten auf dem Pfad, der bei v beginnt und an der Wurzel des höheren Baumes endet, nur O(1) Elementaroperationen getätigt werden. Die Anzahl dieser Knoten ist jh1 ? h2j. Damit läßt sich die Primitive CONCAT, die zwei C?-Bäume konkatenieren soll, realisieren. Korollar 6 Sei T1 ein das Wort w1 repräsentierender C?-Baum und T2 ein das Wort w2 repräsentierender C?-Baum. Dann existiert ein Algorithmus IMPLANT(T1;T2), der die Bäume zu einem C?-Baum T , der das Wort w1w2 repräsentiert, in der Zeit O(log jw1j+ log jw2j) kombiniert. Beweis: Die Suche auf den Randpfaden nach dem Knoten v (wie in Lemma 17 beschrieben) ist in O(log jw1j+log jw2j) Zeitschritten möglich. Damit ergibt sich die Behauptung mit Lemma 17. 34 SPLIT Betrachten wir als letzte Primitive die Operation SPLIT. Für einen C?-Baum T , der das Wort w = w0aw00 repräsentiert, und dem zum Buchstaben a korrespondierenden Blatt liefert SPLIT eine Partition von T in zwei C?-Bäume T1 und T2 so, daß T1 das Wort w0 und T2 das Wort aw00 repräsentiert. Um einen C?-Baum T effizient zu spalten, betrachtet man den bei a beginnenden und bei der Wurzel endenden Pfad in T . Ein Schnitt entlang diesem Pfad zerlegt den Baum T in eine Menge von Teilbäumen, deren Wurzelknoten Kinder von Knoten sind, die sich auf dem Pfad befinden. Die Bäume, die sich links vom Schnitt befinden, werden mit dem vorher vorgestellten Algorithmus konkateniert. Analog werden der Knoten a und die Bäume, die sich rechts befinden ebenfalls konkateniert. T Tl Tr Der folgende Algorithmus enthält die Details. Algorithm DIVIDE (T; a) Comment Input: a nonempty C?-tree T and leaf letter a. Output: two C?-trees devided by the leaf a. Method let v be the a-labeled leaf. if v is the root of T return(h1; T i) else L [] R [v] while v is not the root do let f be the father of v and let v1; : : : ; vi?1; v; vi+1; : : : ; vk be the children of f in order from left to right L L[v1; : : : ; vi?1] R [vi+1; : : : ; vk]R purge v if v is not the leaf v f end while Comment At this point T has been devided into two forrests { the left forrest, which consists of all trees with leaves to the left of the leaf a, (in list L) and the right forest (in list R), which consists of all trees with leaves to the right of a including leaf a. 35 Nodes on the path from a to the root of T except leaf a are removed. while there is more than one tree in the left forrest do let T 0 and T 00 be the two right-most trees in the left forest insert the tree IMPLANT(T 0; T 00) at the right end end while while there is more than one tree in the right forrest do let T 0 and T 00 be the two left-most trees in the right forest insert the tree IMPLANT(T 0; T 00) at the left end end while return the two trees end if end Method Lemma 18 Sei T ein das Wort w = w0aw00 repräsentierender C?-Baum. Dann zerteilt der Algorithmus SPLIT(T; a) = DIVIDE(T; a) den C?-Baum T , in zwei C?-Bäume T1 und T2, von denen der erste das Wort w0 und der zweite das Wort aw00 repräsentiert. Der Algorithmus benötigt O(log jwj) Zeiteinheiten. Beweis: In der Aussage ist das den Buchstaben a repräsentierende Blatt mit dem Buchstaben selbst identifiziert. Die Listen L und R sind in der Länge durch O(log jwj) beschränkt, da je Knoten auf dem Pfad von v zur Wurzel höchstens m neue Elemente angefügt werden. (Man beachte, daß in einer Liste (einem Pfad) aufeinanderfolgende Knoten mit konstantem Abstand in O(jh1 ?h2j) = O(1) Zeiteinheiten gefunden werden kann, insbesondere wenn man noch zusätzlich Höheninformation mitführt.) Dann folgt die Aussage durch Aufaddieren der Zeiten mit Lemma 17. 5.4 Operationen auf der Darstellung Ziel dieses Abschnittes ist aus den vielen Primitiven die Operationen SPLITTRACE und CONCATTRACE für die Spurdarstellung bereitzustellen. Zur Erinnerung: Wir schränken uns auf Spurersetzungssysteme mit zusammenhängenden linken Seiten ein. Die Intention besteht darin, Spurrepräsentationen effizient faktorisieren bzw. konkatenieren zu können. Dazu benötigen wir einen neuen Begriff. Ein Schnitt in einer Spur t 2 M ist ein Tupel s = (wC)C2C mit der Eigenschaft, daß für alle C 2 C für die Projektionen tC = wCw0 C gilt und ß?1(s) 2 M . D.h. für alle C; C 0 2 C mit a 2 C \ C 0 gilt jwCja = jwC0ja. Wir stellen einen Schnitt durch ein Blättertupel (vC)C2C, wobei vC ein Blatt in TC ist, dar. Dieses Tupel repräsentiert die minimalen Buchstaben aus ß?1((w0 C)C2C). Damit entspricht ein Schnitt einer Faktorisierung t = ß?1((wC)C2C) ? ß?1((w0 C)C2C). ß ist der Homomorphismus im Projektionslemma. 36 5.4.1 CONCATTRACE Sei T i = (T i C)C2C eine Darstellung der Spur ti, i 2 f1; 2g. Dann soll die Prozedur CONCATTRACE auf den Argumenten T 1 und T 2 eine Darstellung T = (TC)C2C der Spur t = t1 ? t2 berechnen. Diese Berechnung erfolgt vorerst Komponentenweise auf den Projektionen. Danach werden die >=2-Beschriftungen rekonstruiert. Algorithm CONCATTRACE (T 1; T 2) Comment Input: two trace representations. Output: the representation of the catenation. Method ? ; for each C 2 C do TC CONCAT(T 1 C ; T 2 C) end for Comment At this point the >=2-labeling is violated. All other properties are OK. for each C 2 C do for all l 2 LR with ?(l) \ C 6= ; do let r be the maximal scann range jßC(l)j ? 1 let v1; : : : ; vr be the right-most leaves in T 1 C ? ? [ fv1; : : : ; vrg for i := 1 to r do while there is a factor l with minimal letter vi but l = 2 >=2(vi) do >=2(vi) >=2(vi) [ flg let P = fpC j factor l has minimal letter pC (leaf) at C-projection g for all p 2 P do >=2(p) >=2(p) [ flg end for ? ? [ P end while end for end for end for while ? 6= ; do let v 2 ? ? ? n fvg PROPAGATE2(v) end while return(T ) end Method Die Prozedur PROPAGATE2 vererbt analog zu PROPAGATE1 die Beschriftung ?2 eines Knoten v an seine Vorfahren. Procedure PROPAGATE2 (v) 37 Comment Input: a wrong labeled C?-tree T with a vertex v. Output: a revisted C?-tree. Method if v is the root then terminate else let f be the father of v relabel f by >=2(f) = S c2children(f) >=2(c) PROPAGATE2(f) end if end Method Um die Korrektheit dieses Verfahrens zu zeigen, benötigen wir eine strukturelle Aussage über Faktorisierungen, bei denen zusammenhängende Spuren involviert sind, die Schnittlemmata. Sie sichern die Korrektheit der >=2-Beschriftungen bis auf einen Teil konstanter Größe nach dem Konkatenieren bzw. Faktorisieren zu. Lemma 19 (Schnittlemma A) Sei t = t1 ? t2 2 M (?; D), l 2 M (?; D) eine zusammenhängende Spur und i : l ?! t ein Faktorvorkommen. Dann folgt aus i(l)\(max(t1)[ min(t2)) = ; entweder i(l) \ t1 = ; oder i(l) \ t2 = ;. Beweis: Sei t = hMt; <=ti. Angenommen i(l) \ t1 6= ; und i(l) \ t2 6= ;. Da t = t1 ? t2 gilt für alle Buchstaben a1 in t1 und b2 in t2 mit (a1; b2) 2 D die Relation a1 <=t b2, und da l zusammenhängend ist, existiert ein maximaler Buchstabe a in max(t1) und ein minimaler Buchstabe b in min(t2) mit (a; b) 2 D und zwei Buchstaben c in i(l) \ t1 und d in i(l) \ t2 mit c <=t a <=t b <=t d. Damit ist i : l ?! t aber kein Faktorvorkommen, ein Widerspruch (a oder b beeinträchtigen i). Analog läßt sich folgende Aussage beweisen. Lemma 20 (Schnittlemma B) Sei t = t1 ? t2 2 M (?; D), l 2 M (?; D) eine zusammenhängende Spur und sei i : l ?! t ein Faktorvorkommen mit i(l) \ t1 6= ; und i(l) \ t2 6= ;. Dann gilt i(l) \ max(t1) 6= ; und i(l) \ min(t2) 6= ;. Beweis: Angenommen i(l) \ max(t1) = ; und i(l) \ min(t2) = ;. Da i(l) \ t1 6= ;, existiert ein Buchstabe a in l mit i(a) in t1 und da i(l) \ t2 6= ;, existiert ein Buchstabe b in l mit i(b) in t2. Da l zusammenhängend ist, existiert ein ungerichteter Pfad von a nach b in l, also auch von i(a) nach i(b) in t. Aber dieser Pfad enthält (mindestens) einen Buchstaben aus max(t1) und einen aus min(t2) im Widerspruch zu i(l) \ max(t1) = ; und i(l) \ min(t2) = ;. Damit können wir das folgende Resultat zeigen. Lemma 21 Sei R ein endliches Spurersetzungssystem mit zusammenhängenden linken Seiten. Dann ist das Resultat CONCATTRACE(T1;T2) korrekt beschriftet, wenn die Eingaben T1; T2 korrekt beschriftet waren. 38 Beweis: Die Beschriftung >=1 wird bereits in CONCAT korrekt durchgeführt. Die Beschriftung >=2 ist nach der CONCAT-Operation evtl. fehlerhaft. Sei T i eine ti repräsentierende Struktur, i 2 f1; 2g. Dann wird durch die unbeschriftete Struktur die Spur t1 ? t2 repräsentiert (komponentenweise Konkatenation). Durch diese Konkatenation bleiben alle Faktorisierungen von t1 und t2 erhalten, denn aus t1 = u1lv1 bzw. t2 = u3lv2 folgt t = t1t2 = u1lv1t2 bzw. t = t1u2lv2. Es können aber durch die Konkatenation neue Faktorvorkommen l ?! t, l 2 LR entstanden sein. Jedes dieser neuen Faktorvorkommen enthält mindestens einen maximalen Buchstaben aus t1 (siehe Lemma 20). Für alle linken Seiten l 2 LR werden diese Vorkommen untersucht. Der betrachtete Bereich ist ausreichend, da nur Vorkommen, die an diesen Positionen beginnen, einen Buchstaben aus max(t1) besitzen können. Da diese Analyse für jede Projektion durchgeführt wird, sind danach alle Faktorvorkommen entdeckt, die einen nichtleeren Schnitt mit max(t1) besitzen, und da bei jedem neu entdeckten Faktor l in t = ulv alle Minimalpositionen pC , d.h. Verweise auf aC mit ßC(l) = aC l0 C , ßC(t) = tC = ßC(u)aCl0 CßC(v), für alle C 2 C mit >=2(v) [ flg, markiert werden (diese Positionen werden alle in ? gespeichert), sind nach der Ausführung der for-Schleifen alle Blätter korrekt >=2-beschriftet. Analog wie für die Beschriftung >=1 gilt die Invariante für die Datenstuktur: Für alle inneren Knoten v gilt >=2(v) = [ c2children(v) >=2(c): Die Prozedur PROPAGATE2 beschriftet alle neu beschrifteten Nachfolger (diese sind alle in ? abgelegt) und mit Induktion folgt, daß alle >=2-Beschriftungen hiernach korrekt sind. Theorem 5 Sei T 1 eine die Spur t1 repräsentierende Struktur und T 2 eine die Spur t2 repräsentierende Struktur. Dann kombiniert CONCATTRACE(T 1; T 2) die Strukturen zu einer t1 ? t2 repräsentierenden Struktur T in O(log jt1j + log jt2j) Zeiteinheiten. Beweis: Mit dem Resultat über die C?-Bäume ist ein Konkatenieren der einzelnen Komponenten T 1 C mit T 2 C in O(log jßC(t1)j + log jßC(t2)j) <= O(log jt1j + log jt2j) möglich. Die Bedingung der innersten Iteration läßt sich in O(log jt1j + log jt2j) = O(max(log jt1j; log jt2j) + 1) testen, und dieser Test wird höchstens c = P l2LR;C2C jßC(l)j = O(1) oft durchgeführt. Damit ist die Kardinalität von ? durch j?j = O(1) beschränkt. Jeder PROPAGATE2 Aufruf benötigt O(max(log jt1j; log jt2j) + 1) Zeiteinheiten und es gibt insgesamt j?j = O(1) viele Aufrufe. Zusammengefaßt ergibt sich die Zeitkomplexität O(log jt1j+log jt2j). Das vorhergehende Lemma sichert mit dem Korrektheitsresultat für die Methode CON- CAT die strukturellen Eigenschaften von T zu. 39 5.4.2 SPLITTRACE Invers zur Operation CONCATTRACE zerteilt die Operation SPLITTRACE eine Darstellung T = (TC)C2C der Spur t entlang eines Schnittes a = (aC)C2C in T . Als Resultat erhalten wir die Darstellungen T i = (T i C)C2C der Spuren ti, i 2 f1; 2g mit der Eigenschaft t1 ? t2 = t. Weiter korrespondiert das Tupel der minimalen Elemente von t2, ß(min(t2)) zum Schnitt (aC)C2C . Auch hier wird mit einer Basisoperation die Darstellung erst komponentenweise faktorisiert. Danach werden die fehlerhaften >=2-Beschriftungen korrigiert. Algorithm SPLITTRACE (T; a) Comment Input: a trace representation with cut a. Output: two representations devided by leaves in a. Method ? ; for each C 2 C do hT 1 C ; T 2 Ci SPLIT(TC ; aC) end for Comment At this point the >=2-labeling is violated. All other properties are OK. for each C 2 C do for all l 2 LR with ?(l) \ C 6= ; do let r be the maximal scann range jßC(l)j ? 1 let v1; : : : ; vr be the right-most leaves in T 1 C ? ? [ fv1; : : : ; vrg for i := 1 to r do while there is no factor l with minimal letter vi and l 2 >=2(vi) do >=2(vi) >=2(vi) n flg let P = fpC j the linked references of vi to the (leaves) at the other C-projections g for all p 2 P do >=2(p) >=2(p) n flg ? ? [ P end while end for end for end for while ? 6= ; do let v 2 ? ? ? n fvg PROPAGATE2(v) end while return(T ) end Method Analog zu Theorem 5 erhalten wir aus Lemma 19 das 40 Theorem 6 Sei R ein endliches Spurersetzungssystem mit zusammenhängenden linken Seiten. Weiter sei T eine die Spur t repräsentierende Struktur und a ein die Faktorisierung t = t1 ? t2 repräsentierender Schnitt. Dann partitioniert SPLITTRACE(T; a) die Struktur in eine Spurrepräsentation T1 von t1 und T2 von t2 in O(log jtj) Zeiteinheiten. 5.5 Der Reduktionsalgorithmus Mit den bis jetzt formulierten Primitiven können wir eine Prozedur FACTORIZE formulieren, mit der ein Faktorvorkommen via die zweite Beschriftung gefunden wird. Die Faktorisierung kann mit der oben vorgestellten Faktorisierungsmethode durchgeführt werden, nachdem ein Schnitt mit den primitiven Operationen berechnet wurde. Diese Datenstuktur enthält Zugriffspfade auf alle Faktorisierungen u ? l ? v. D.h. ersetzt man die Beschriftungen durch entsprechende Parikh-Bilder >=0 1 : tC ?! NC >=0 2 : tC ?! NLR ; so läßt sich die Wahl eines Faktorvorkommens i und der Faktorisierung von ind(i) vollständig festlegen. Unter anderem ist auch die Wahl einer kanonischen Links-Derivation möglich. Die Berechnung der Normalform erfolgt mit der Methode REDUCE. PROCEDURE REDUCE(t) Comment Input: C? tree trace representation. Output: the representation of the normal form. Method while 9l 2 >=2(t) do calculate two cuts c1 c2, factorizing t into u, l, and v hu; v0i SPLITTRACE(t; c1) hx; vi SPLITTRACE(v0; c2) t CONCATTRACE(u; r) t CONCATTRACE(t; v) end while return(t) end Method Aus der Vollständigkeit und Korrektheit der Beschriftungsinformation ergibt sich Theorem 7 Sei M = M (?; D) ein frei partiell kommutatives Monoid und R ein endliches noethersches Spurersetzungssystem mit nur zusammenhängenden linken Seiten, dann existiert ein Algorithmus, der eine beliebige, durch eine Wahl spezifizierbare, irreduzible Form einer Spur t 2 M in der Zeit O(jtj + dR log dR) berechnet. 41 Beweis: Mit den Beschriftungen und den oben vorgestellten Primitiven kann ein Faktor l 2 LR in einer Repräsentation einer Spur t in O(log jtj) identifiziert werden. Beispielsweise findet man einen Faktor, indem man von einer mit l 2 X beschriebenen Wurzel aus zu einem mit l 2 >=2(v) beschrifteten Blatt v absteigt. Dabei wird man durch die >=2-Beschriftung geführt. Hat man dieses Blatt gefunden, so kann das Vorkommen über den Zusammenhang von l vervollständigt werden. Die Schnitte lassen sich unter Verwendung der Methode PRED vervollständigen. Ist die Spur irreduzibel, so sind alle >=2-Beschriftungen der Wurzeln leer. Rechts- und Linksquotienten bzw. die Schnitte c1 und c2 lassen sich in O(log jtj) Zeiteinheiten konstruieren, und die anschließende Konkatenation ist auch in O(log jtj) Zeit möglich. Theorem 8 Sei M = M (?; D) ein frei partiell kommutatives Monoid und R ein noethersches Spurersetzungssystem mit nur zusammenhängenden linken Seiten, dann existiert ein Algorithmus, der eine Links-Derivation einer Spur t 2 M in der Zeit O(jtj + dR log dR) berechnet. Die Links-Derivation läßt sich auch bzgl. einer lexikographischen Ordnung definieren. Da die oben definierte Links-Derivation berechnet werden kann und nur konstannt viele unvergleichbare Reduktionsschritte existieren können Links-Derivation bzgl. aller Verfeinerungen dieser Ordnung (?, siehe Anhang A.2) auch in dieser Zeit berechnet werden. Korollar 7 Sei M = M (?; D) ein frei partiell kommutatives Monoid und R ein noethersches Spurersetzungssystem mit nur zusammenhängenden linken Seiten, dann existiert ein Algorithmus, der eine Links-Derivation bzgl. einer Verfeinerung der Ordnung ? einer Spur t 2 M in der Zeit O(jtj + dR log dR) berechnet. Theorem 9 Sei M = M (?; D) ein frei partiell kommutatives Monoid und R ein gewichtsreduzierendes Spurersetzungssystem mit nur zusammenhängenden linken Seiten, dann existiert ein Algorithmus, der eine beliebige, durch eine Wahl spezifizierbare, irreduzible Form einer Spur t 2 M in der Zeit O(jtj log jtj) berechnet. Bemerkung 2 Man beachte, daß alle Resultate nur nicht-uniforme Komplexitätsaussagen sind. Betrachtet man beispielsweise das Wortproblem für kommutative Semigruppen. Im uniformen Fall besteht eine Instanz aus einem Tupel (?; S; u; v), wobei S ein die Gruppe beschreibendes Gleichungssystem ist (modulo Kommutativität). u und v sind Vektoren aus N? und die Frage lautet: " Ist die Gleichung u ? v ( mod S ) wahr?\. Dieses Problem ist sogar exponentiell-platzhart [MM82]. Im nicht-uniformen Fall transformiert man das Gleichungssystem lediglich in ein äquivalentes konfluentes und gewichtsreduzierendes Ersetzungssystem S 0 ? N??N? , von dem wir in linearer Zeit mit einer der oben beschriebenen Algorithmen entscheiden können, ob u ? ()R v erfüllt ist. 42 Die Restriktion auf Spurersetzungssysteme mit zusammenhängenden linken Seiten ist in gewisser Hinsicht natürlich. Interpretiert man das Ersetzungssystem als operationelle Semantik eines nebenläufigen Systems, so erscheint es unnatürlich, wenn Komponenten, die in jedem Kontext vollständig parallel ablaufen können, durch eine einzige Interaktion ersetzt werden sollen. Eine Konsequenz aus der Bedingung der zusammenhängenden linken Seiten ist, daß sich dann alle interagierenden Faktoren in einer konstanten Umgebung befinden. Betrachtet man die durch die Kanten des Redukts von dem Abhängigkeitsgraphen induzierte Metrik, so befinden sich alle Faktoren l0, die von einer Ersetzung u0l0v0 = ulr =)R urv betroffen sind, in der Kugel DR(r) in urv mit dem Radius R = maxfjlj j l 2 LRg. Man beachte, daß sich die Abstände bzgl. dieser Metrik aber im Lauf einer Berechnung stark variieren können. Beispiel 2 Sei a b c2 d e c1 (?; D) = und R beschrieben durch folgende Ersetzungsregeln. b2c1d2 =)R b2d2; b2c2 =)R b2c1; d2c2b2 =)R bc2d; ae =)R c2 Alle linken Seiten sind zusammenhängend. Beginnen wir mit der Spur t = akb2nc1d2nek, k >= 1 und n >= 2. Man beachte, daß ae kein Faktor ist (Sprungsequenz4 abc1de), und daß die Buchstaben a; e in t die Distanz d >= 4n + 2 besitzen. Der erste Ersetzungsschritt führt zu b2n t1 = d2n ak ek und der nächste zu t2 = b2n d2n c2 ak?1 ek?1 Nach n weiteren Ersetzungen, erhalten wir t3 = ak?1bnc2dnek?1 und, da n >= 2, ersetzen wir das durch t4 = ak?1bnc1dnek?1. Dieses Beispiel illustriert wie sich die Abstände verändern. Dabei treten insbesondere sehr große und globale Abstandsänderungen auf, wenn Artikulationsknoten eliminiert werden und keine verbindenene Knoten eingefügt werden. Dann ändern sich Abstände von endlichen Werten auf unendliche. 4Sprungsequenzen sind im Anhang definiert. 43 6 Effizienzsteigerung durch Sichtbarkeit bei Ersetzungssystemen mit zusammenhängenden linken Seiten 6.1 Sichtbarkeit Die Baumstrukturen wurden wegen der fehlenden transitiven Relationen im Abhängigkeitsgraphen eingeführt. Für Abhängigkeitsalphabete, die nur " sichtbare\ Buchstaben enthalten, kann auf diese Zugriffsstrukturen verzichtet werden. Sei (?; D) wieder ein Abhängigkeitsalphabet und M = M (?; D) das erzeugte Monoid. C sei eine Cliquenüberdeckung von (?; D) und die Spuren t 2 M seien in der Projektionsdarstellung ß(t) 2 Q C2C C?. R sei, wie gehabt, das Ersetzungssystem und LR die Menge der linken Seiten, die alle zusammenhängend sein sollen. Wir nennen einen Buchstaben c 2 ? von X ? ? aus bezüglich der Cliquenüberdeckung C sichtbar5, wenn für alle Cliquen A; B 2 C mit c 2 A \ B eine Clique C 2 C, ein Buchstabe a 2 A \ X und ein Buchstabe b 2 B \ X mit fa; b; cg ? C existiert. Beispiel 3 Sei X ? ?. Dann ist jeder Buchstabe c 2 X von X aus sichtbar. Wir setzen a = b = c 2 X und wählen eine Clique C 2 C, die c enthält. In dem Abhängigkeitsalphabet c a X b B C A ist der Buchstabe c von X = fa; bg aus sichtbar für C = fA; B; Cg 5Man beachte, daß die Sichtbarkeit von der zugrundeliegenden Cliquenüberdeckung abhängig ist und daß damit jede Clique einen nichtleeren Schnitt mit X besitzt. 44 Seien C = fC1; : : : ; Ckg und t; l 2 M mit ß(t) = (tC)C2C 2 Q C2C C? und ß(l) = (lC)C2C 2 Q C2C C?. Sei weiter 0 B @ tC1 ... tCk 1 C A = 0 B @ uC1 ? lC1 ? vC1 ... uCk ? lCk ? vCk 1 C A = 0 B @ uC1 ... uCk 1 C A ? 0 B @ lC1 ... lCk 1 C A ? 0 B @ vC1 ... vCk 1 C A ; uCi ; vCi; lCi ; tCi 2 C? i für alle i 2 [k]. Dann entspricht nicht jede dieser Faktorisierungen (in Q C2C C?) einer Faktorisierung ß(u) ? ß(l) ? ß(v) mit ß(u) = (uC)C2C, ß(l) = (lC)C2C und ß(v) = (vC)C2C. Die notwendige und hinreichende Bedingung ist ein Korollar aus Lemma 42 bzw. folgt aus der Charakterisierung in Lemma 6 im vorigen Kapitel. Korollar 8 Sei C eine Cliquenüberdeckung von (?; D) und t; l 2 M (?; D). Dann gilt t = u ? l ? v genau dann, wenn es Wörter uC ; vC 2 C? für alle C 2 C gibt mit (i) ßC(t) = uCßC(l)vC für alle C 2 C und (ii) juAja = juBja für alle A; B 2 C und für alle a 2 A \ B. Es gilt dann ß(u) = (uC)C2C und ß(v) = (vC)C2C für eine Faktorisierung t = u ? l ? v in M (?; D). Das folgende Beispiel illustriert ein Problem, das durch unsichtbare Buchstaben auftreten an einer Derivation. Beispiel 4 Sei (?; D) = " a d e b c # das Abhängigkeitsalphabet und l = [adeb]. Es gibt genau eine Cliquenüberdeckung C = fA; B; C; D; Eg mit A = fa; cg, B = fb; eg, C = fb; cg, D = fa; dg und E = fd; eg. Der Buchstabe c ist unsichtbar von ?(l) = fa; d; e; bg, da keine Clique existiert, die fa; b; cg enthält. Betrachten wir die beiden einelementigen Spurersetzungssysteme R1 = fl ! 1g und R2 = fl ! cg und untersuchen eine Reduktion der Spur t = [adamadebbmeb]. Wir erhalten für t die Darstellung t = 0 B B B B @ aama ebbmeb bbmb adamad ddee 1 C C C C A ? = " a d am a d e b bm e b # Es existiert genau eine Faktorisierung t = ulv, die in der Darstellung durch Rechtecke in jeder Komponente hervorgehoben ist. 45 t = 0 B B B B B @ aam a eb bmeb b bmb adam ad d de e 1 C C C C C A ? = " a d am a d e b bm e b # Sei t =)R1 t1 und t =)R2 t2. Nach dem Reduktionsschritt erhalten wir ein neues Vorkommen sowohl in t1 als auch in t2, das ein Kandidat für eine Faktorisierung ist. t1 = 0 B B B B B @ a am bm eb bm b ad am de 1 C C C C C A ? = 2 6 6 4 e bm b a d am 3 7 7 5 In t1 ist der hervorgehobene Teil ein Faktor, was hier in konstanter Zeit überprüft werden kann. (Eine Konsequenz aus Theorem 12.) t2 = 0 B B B B B @ a amc bm eb bm cbm b ad am de 1 C C C C C A ? = " a d am bm e b c # In t2 sind die markierten Teile jedoch kein Faktor. Die Anzahl der cs vor dem a ist 0, hingegen ist die Anzahl der cs, die vor einem b liegen, 1. Das Problem besteht also darin, eine dynamische Struktur zu finden, mit der die Parikh- Bilder juCja und juC0ja für C; C 0 2 C und a 2 C \ C 0 einer Faktorisierung (uC lCvC)C2C schnell verglichen werden können. Leider sind diese Werte nicht durch Konstanten wie bei freien Monoiden beschränkt. Gleichzeitig sollen auch Ersetzungen effizient durchführbar sein. Beispielsweise könnte man zu jedem Buchstaben das Parikh-Bild des von ihm induzierten Präfix assoziieren. Das hätte aber zur Folge, daß ein Ersetzungsschritt globale Aktualisierungen nach sich ziehen würde. Für sichtbare Buchstaben gilt das folgende (für die Korrektheit des Algorithmus zentrale) Lemma Lemma 22 Sei l 2 M (?; D) und sei C eine Cliquenüberdeckung von (?; D). Weiter sei ß(t) = (tC)C2C = (uC)C2C ? (lC)C2C ? (vC)C2C in Q C2C C? das ß-Bild einer Spur t 2 M (?; D) so, daß juAja = juBja für alle a 2 ?(l) und für alle A; B 2 C mit a 2 A\B. Dann gilt für zwei Cliquen A; B 2 C und einen von ?(l) aus sichtbaren Buchstaben c 2 A \ B die Beziehung juAjc = juBjc. 46 Beweis: Seien A; B 2 C beliebige Cliquen und c von ?(l) aus sichtbar. Dann ist für c 2 ?(l) die Behauptung trivial. Sei c = 2 ?(l), a 2 ?(l) \ A und b 2 ?(l) \ B, so daß eine Clique C 2 C mit fa; b; cg ? C existiert (a; b; C existieren, da c sichtbar ist). Wir zeigen: juAjc = juBjc. Sei juAjc < juBjc. Aus der Voraussetzung folgt juCja = juAja und juC jb = juBjb sowie a; b 2 ?(l). Betrachten wir das erste a in l, d.h. das i-te a in t mit i = juAja + 1 = juCja + 1. Weiter betrachten wir das erste b in l, also das j-te b in t mit j = juBjb + 1 = juCjb + 1. Dann stehen vor dem j-ten b mehr cs als vor dem i-ten a in ßfa;b;cg(tC). Also steht ein c zwischen diesem a und diesem b in ßfa;b;cg(t) = ßfa;b;cg(tC) und damit steht auch ein c zwischen dem i-ten a und dem j-ten b in tC . Formal sei xa 2 C? das Präfix von tC , das mit dem i-ten a endet und xb 2 C? das Präfix von tC , das mit dem j-ten b endet. Dann gilt tC = uC lC vC = xa ya = uC t0 Cal00 Cbl000 C vC = xb yb für ergänzende ya; yb 2 C?. Da aber dann juAjC + 1 = jxajc < jxbjc, existiert z 2 C? mit xaz = xb und jzjc > 1. Also enthält l00 Cb = z mindestens ein c, im Widerspruch zu c = 2 ?(l). Entsprechendes gilt für juAjc > juBjc 6.2 Ein Linearzeit-Reduktionsalgorithmus Schränken wir uns auf sichtbare Buchstaben ein, so können wir auf die C?-Baumstruktur verzichten. Theorem 10 Sei C eine Cliquenüberdeckung von einem Abhängigkeitsalphabet (?; D), R ? M (?; D) ? M (?; D) ein Ersetzungssystem mit den linken Seiten LR. Jede linke Seite sei zusammenhängend und alle Buchstaben a 2 ? seien von ?(l) aus sichtbar für jede linke Seite l 2 LR. Dann kann eine Derivation t n =)R t0 in O(n+ jtj) Zeiteinheiten berechnet werden. Beweis: Wir beweisen das Theorem durch Angabe eines Algorithmus, der eine Deriva- tion ulv 1 =)R urv, l ! r 2 R, in konstanter Zeit nach O(jtj) Initialisierungsschritten berechnen kann. Wir repräsentieren in diesem Algorithmus eine Spur t 2 M (?; D) als Worttupel ß(t) = (tC)C2C. Weiter sollen wieder Referenzen zwischen den Buchstaben a 2 ? in den Komponenten von ß(a) in ß(t0)ß(a)ß(t00) existieren, die beispielsweise durch Zeigerstrukturen realisiert werden können, und es soll eine Liste Ll der Faktorvorkommen l ?! t für alle l 2 LR berechnet sein. Alle diese Strukturen lassen sich durch eine Vorwegberechnung in O(jtj) mit dem folgenden Algorithmus konstruieren. Die Idee des Algorithmus ist die Verwaltung von Längeninformation, d.h. für jede Clique und jedes Präfix uC von tC sollen das Parikh-Bild (juCja)C2C;a2C = (n(C; a; juCj))C2C;a2C berechnet werden. Dabei Identifizieren wir das Präfix mit seiner Länge. Alle " synchronen\ Muster, d.h. Faktorisierungen tC = uClCvC aller Komponenten mit der Eigenschaft juC ja = juC0ja für alle A; B 2 C mit a 2 A \ B sollen durch entsprechende Verweise als 47 Faktorvorkommen in eine Liste Ll aufgenommen werden. Diese können beispielsweise durch Tupel (juCj)C2C;C\?(l)6=; repräsentiert werden. PROCEDURE PREPROCESSING(t) Comment Input: a trace in word representation. Output: the internal representation of the trace. Method for all (C; a) 2 C ? ? do ?C;a 0 end for for all l 2 LR do Ll [] end for for all C 2 C do tC 1 end for while t = at0 do t t0 for all (b; C) 2 ? ? C do if a 2 C and b = a then tC tCa ?C;a ?C;a + 1 n(C; a; jtCj) ?C;a else n(C; b; jtC j) n(C; b; jtC j ? 1) end if end for end while for all l 2 LR do let a 2 ?(l) and C 2 C with a 2 C w tC while w = bw0 do if w = ßC(l)w00 then scan along an undirected path through l the factorizations tC = uC lCvC via cross references if there exists a factorization (tC)C2C = (uClCvC)C2C with ?(a; A; juAj) = ?(a; B; juBj) for all A; B 2 C and all a 2 A \ B then append the positions (juCj)C2C;C\?(l)6=; to Ll end if end if end while end for return ((tC)C2C; (Ll)l2LR) end Method Innerhalb der ersten drei Schleifen werden die Datenstrukturen initialisiert. Die darauf folgende while-Schleife ermittelt die einzelnen Projektionen tC und die Längeninformation juCja für die Präfixe uC von tC für alle a 2 C. In der zweiten while-Schleife werden " synchrone\ Faktorisierungen als Vorkommen entdeckt und in den Listen Ll gespeichert. Die Korrektheit folgt aus der Invariante juC ja = n(a; C; juCj) für alle A 2 C und a 2 C. Da die Spuren l 2 LR zusammenhängend sind, läßt sich der Scan vor der letzten Se- 48 lektion in konstanter Zeit auf der Verweisstruktur durchführen. Die Referenzen ermöglichen die eineindeutige Zuordnung der Faktoren in anderen Komponenten (l ist zusammenhängend, alle Buchstaben sind von ?(l) aus sichtbar). Die Zeitkomplexität summiert sich zu O(jCj ? jLRj ? jtj ? P l2LR jlj) = O(jtj). Eine effizientere Methode liefert ein Fortschreiten mit Fehlerfunktionen wie im Algorithmus von Knuth, Morris und Pratt. Das Beispiel illustriert die Vorgehensweise für einen Scan. Beispiel 5 Sei (?; D) = a ? b ? c, t = ? ababa bcb ? und l = ? aba cb ? . Das erste Vor- kommen von aba in der ersten Komponente von ? aba ba bcb ? , ist nicht die Projektion eines Faktors l, denn das b in in diesem Vorkommen korrespondiert zum ersten b in t, also auch zum ersten in der zweiten Komponente. Vor diesem b steht aber kein c. Das zweite Vorkommen von aba, ab aba b cb ! , in der ersten Komponente ababa induziert ein Faktorvorkommen von l, denn das b in diesem Vorkommen korrespondiert zu dem b in der zweiten Komponente, vor dem ein c steht. Sind die Listen der Faktorvorkommen initialisiert, können wir einen Ersetzungsschritt in konstanter Zeit so durchführen, daß die Vollständigkeit dieser Listen eine Invariante ist. D.h., nach dem Ersetzungsschritt enthält die Liste Ll wieder genau alle Faktorvorkommen von l in der modifizierten Spur t für alle l 2 LR. Wie im vorigem Kapitel bezeichnen wir mit max(t) die maximalen Buchstaben in t, d.h. die Buchstaben a 2 C für die die Projektion tC = t0 Ca auf eine Clique C 2 C mit a endet. Dual dazu bezeichnet min(t) die minimalen Buchstaben. PROCEDURE REDUCEnSTEPS(t;n) Comment Input: trace in representations. Output: the decendant in representation. Method while n > 0 and 9i 2 Ll for some l 2 LR with l ! r 2 R do n n ? 1 factorize t by the tuple of positions i into u = (uC)C2C, l = (lC)C2C and v = (vC)C2C purge l and purge all occurrences j : l0 ?! t in Ll0 having an overlap with i(l) [ max(u) [ min(v). t u ? r ? v insert all new occurrences j : l0 ?! t, l 2 LR having some nonempty overlap with r [ max(u) [ min(v) end while return(ht; L0i) end Method Die erste Komplexanweisung 49 factorize t by i into u = (uC)C2C, l = (lC)C2C and v = (vC)C2C purge l and all occurrences j : l0 ?! t in Ll0 having an overlap with i(l) [ max(u) [ min(v). läßt sich in konstanter Zeit abarbeiten. Eine Faktorisierung tC = uC ? lC ? vC kann für alle C 2 C in konstanter Zeit über die maximalen bzw. minimalen Buchstaben des Vorkommens von l berechnet werden. Jedes der Faktorvorkommen, die entfernt werden sollen, korrespondiert zu einer Faktorisierung tC = u0 C ? l0 C ? v0 C für alle C 2 C so, daß ein A 2 C existiert mit jjuAj ? ju0 Ajj < jl0 C j (vgl. Lemma 19 und 20). Diese können in O( P l2LR;C2C jlCj2) = O(1) Zeit aus den Listen Ll0 , l0 2 LR über entsprechende Referenzen entfernt werden. Das Eliminieren von l und das Einsetzen von r geht offensichtlich in konstanter Zeit. Analog zum Entfernen der überlappenden Faktoren werden von der Komplexanweisung insert all new occurrences j : l0 ?! t, l 2 LR having some nonempty overlap with r [ max(u) [ min(v) alle noch in den Listen fehlenden Faktorvorkommen in konstanter Zeit eingetragen. Die Konkatenation geschieht komponentenweise durch Verkettung der einzelnen Strings. Für alle in Ll0 fehlenden Faktorvorkommen, l 2 LR, existiert eine Clique so, daß sich t = urv = u0l0v0 faktorisieren läßt mit jjuCj?ju0 Cjj < jl0 C j (vgl. Lemma 19). Diese Faktorisierungen lassen sich über die Zusammenhangsbedingung in O( P l2LR;C2C jlCj2) = O(1) Zeiteinheiten auffinden bzw. die Liste Ll0 läßt sich in dieser Zeit vervollständigen. Über die gegenseitigen Referenzierungen der Buchstaben aC in t = t0at00 mit ß(t) = ß(t0)(aC)C2Cß(t00) werden nur Faktorisierungen 0 B @ tC1 ... tCk 1 C A = 0 B @ u0 C1 ... u0 Ck 1 C A ? 0 B @ l0 C1 ... l0 Ck 1 C A ? 0 B @ v0 C1 ... v0 Ck 1 C A mit C = fC1; : : : ; Ckg und ju0 Aja = ju0 Bja für alle A; B 2 C, a 2 A \ B \ ?(l) betrachtet. Da alle Buchstaben von allen Mengen ?(l) ? ? aus sichtbar (bzgl. C) sind, folgt mit Lemma 22, daß jede so berechnete Faktorisierung die Bedingung ju0 Ajc = ju0 Bjc für alle A; B 2 C und c 2 A \ B erfüllt. Nach Lemma 8 induziert dann dieses Vorkommen die Faktorisierung t = ß?1((u0 C)C2C) ? l0 ? ß?1((v0 C)C2C). Wir erhalten als Invariante die Semantik der Datenstruktur. Damit ist das Resultat des Algorithmus ein Derivat der Eingabe. Die Zeitkomplexität für die gesammte Berechnung ist O(jtj + n), da der Rumpf der Iteration konstante Zeit benötigt. Ein iteriertes Anwenden der oben beschriebenen Methode führt zu dem folgenden Resultat. Theorem 11 Sei C eine Cliquenüberdeckung von einem Abhängigkeitsalphabet (?; D), R ? M (?; D) ? M (?; D) ein Ersetzungssystem mit den linken Seiten LR. Jede linke Seite sei zusammenhängend und alle Buchstaben a 2 ? seien von ?(l) aus sichtbar für 50 jede linke Seite l 2 LR. Dann kann eine irreduzible Form ^t 2 Irr(R) von t 2 M (?; D) in O(dR) Zeit berechnet werden. Beweis: Die Spur ist irreduzibel, wenn alle Listen Ll für l 2 LR leer sind. Ein Reduktionsschritt läßt sich in O(1) Zeiteinheiten durchführen. Korollar 9 Sei C eine Cliquenüberdeckung von einem Abhängigkeitsalphabet (?; D), R ? M (?; D) ? M (?; D) ein Ersetzungssystem mit den linken Seiten LR. Jede linke Seite sei zusammenhängend, es existiert eine Clique C 2 C mit ßC(l) 6= 1 für alle l 2 LR und alle Buchstaben a 2 ? seien von ?(l) aus sichtbar für jede linke Seite l 2 LR. Dann kann eine Links-Derivation t ? =)R ^t 2 Irr(R) in O(dR) Zeit berechnet werden. Beweis: Seien i und j zwei Vorkommen von zusammenhängenden Spuren l. Wir definieren die Vorkommenordnung ?: i ? j :() Post(j) ? Post(i): Die Listen Ll, l 2 R, sind kanonisch durch ? linear geordnet (siehe Lemma 44) und diese Ordnung kann lokal durch konstante Operationen aufrecht erhalten werden. Die relative Position eines Vorkommen i : l ?! t zu einem Vorkommen j : l0 ?! t ist auf der Projektion tC überprüfbar. Seien i und j durch die Faktorisierungen uClCvC = u0 C l0 Cv0 C induziert. Dann impliziert juCj < ju0 C j die Relation i ? j. Bei Gleichheit kann eine entsprechende Analyse auf einer anderen Komponente erfolgen. Damit ist i ? j innerhalb einer durch die Konstante maxfjlj j l 2 LRg beschränkten Umgebung in konstanter Zeit entscheidbar. Stellt man alle Vorkommen in einer Liste L durch Verweise auf Positionen in tC dar, dann läßt sich eine Links-Derivation durch iteriertes reduzieren eines minimalen Faktors berechnen. Ein minimaler Faktor kann in dieser Datenstruktur in konstanter Zeit bestimmt werden. Korollar 10 Sei C eine Cliquenüberdeckung von einem Abhängigkeitsalphabet (?; D), R ? M (?; D) ? M (?; D) ein gewichtsreduzierendes Ersetzungssystem mit den linken Seiten LR. Jede linke Seite sei zusammenhängend und alle Buchstaben a 2 ? seien von ?(l) aus sichtbar für jede linke Seite l 2 LR. Dann kann eine irreduzible Form ^t 2 Irr(R) von t 2 M (?; D) in O(jtj) Zeit berechnet werden. Bemerkung 3 Die Voraussetzungen sind insbesondere für längenverkürzende Semi- Thue Systeme erfüllt. Damit verallgemeinert dieses Resultat die Aussage von Book [Boo82]. Wie im vohergehenden Kapitel in Korollar 7 lassen sich auch Links-Derivation bzgl. lexikographischen Ordnung in linearer Zeit berechnen. Andere Anwendungen des Sichtbarkeitskonzeptes führen zu ähnlichen Komplexitätsresultaten. So wurde beispielsweise in [BD93] gezeigt: Theorem 12 Für eine Cliquenüberdeckung C, ein längenverkürzendes Einregelsystem fl ! rg = R mit l zusammenhängend, ßC(l) 6= 1 für alle C 2 C, so daß (nur) alle Buchstaben a 2 ?(r) von ?(l) aus sichtbar sind, existiert ein Linearzeitalgorithmus, der eine Normalform berechnet. 51 7 Dekomposition von Spurmonoiden Die Darstellung von Spuren durch die Cliquenprojektionen bzw. die Sichtbarkeitsbedingung führt zu effizienten Algorithmen. Der Ansatz zur Darstellung von einer Subklasse von Spuren, der in diesem Kapitel entwickelt wird, liefert weitere effiziente Algorithmen. Wir entwickeln eine Methode, die es erlaubt, für eine große Klasse frei partiell kommutativer Monoide eine fixe " Zerfaserung\ der Monoidstruktur anzugeben, die es ermöglicht, modular " zerfaserte\ Faktoren zu rekombinieren. Seien (?; D?) und (?; D?) zwei disjunkte Abhängigkeitsalphabete (? \ ? = ;). Dann definieren wir die direkte Summe via (?; D?) ? (?; D?) := (? [ ?; D? [ D?); und das Komplexprodukt mit (?; D?) ? (?; D?) := ? ? [ ?; D? [ D? [ (? ? ?) [ (? ? ?) ? : Definition 2 Wir bezeichnen die kleinste Subklasse der Abhängigkeitsalphabete, die unter direkter Summe und Komplexprodukt abgeschlossen ist, und die einelementigen Abhängigkeitsalphabete enthält, als Cographen-Abhängigkeitsalphabete. Die Spurmonoide, die von diesen Abhängigkeitsalphabeten erzeugt werden, nennen wir Cographen-Monoide. Es gibt eine graphentheoretische Charakterisierung für Cographen-Abhängigkeitsalphabete. Interpretiert man das Abhängigkeitsalphabet (?; D) als ungerichteten Graph und entfernt alle Schlingen, so ist das Abhängigkeitsalphabet (?; D) genau dann ein Cographen-Abhängigkeitsalphabet, wenn der Graph (?; D n f(a; a) j a 2 ?g) keinen induzierten Untergraph der Form ? fa; b; c; dg; f(a; b); (b; c); (c; d)g ? = [a ? b ? c ? d] enthält, fa; b; c; dg ? ?, d.h. falls (?; D) nicht P4 als induzierten Untergraph enthält. Eine Deskription eines Abhängigkeitsalphabetes ist ein linearer Term, der aus disjunkten Abhängigkeitsalphabeten und den (Infix-)operatoren + und ? besteht. Die Dekomposition eines Abhängigkeitsalphabets (?; D) berechnet sich wie folgt. Ist der Graph (?; D) nicht zusammenhängend, so ist die Dekomposition Dec(?; D) die Menge der Zusammenhangskomponenten von (?; D). Ist (?; D) zusammenhängend, dann besteht die Menge Dec(?; D) aus den Komplementen der Zusammenhangskomponenten des Komplements von (?; D). Dabei verstehen wir unter dem Komplement von (?; D) den Graphen (?; (? ? ?) n D). 52 Proposition 1 Eine Dekomposition f(?i; Di) j i 2 [n]g von (?; D) entspricht der kanonischen Deskription. Ist (?; D) nicht zusammenhängend, so gilt (?; D) = ?i2[n](?i; Di). Anderenfalls gilt (?; D) = ?i2[n](?i; Di). Weiter bezeichnen wir mit Dec?(?; D) die Menge aller Subalphabete (?; D?) ? (?; D), die durch Deskriptionen über Elementen aus Z(?; D) darstellbar sind. Z(?; D) ist dabei die rekursive Zerlegung in nicht-dekompositionierbare Alphabete, d.h. - Z(?; D) = f(?; D)g, wenn Dec(?; D) = f(?; D)g. - Anderenfalls gilt Z(?; D) = S fZ(?; D?) j (?; D?) 2 Dec(?; D)g. Proposition 2 Für ein Abhängigkeitsalphabet ist die Menge Dec?(?; D) mit den Operationen (?1; D1) _ (?2; D2) = \ f(?; D) 2 Dec?(?; D) j ?1 ? ?; ?2 ? ?g (?1; D1) ^ (?2; D2) = [ f(?; D) 2 Dec?(?; D) j ? ? ?1; ? ? ?2g ein Verband. Die graphentheoretischen Mengenoperationen sind komponentenweise definiert. Für ein Abhängigkeitsalphabet (?; D) und eine Teilmenge ? ? ? definieren wir das von ? induzierte Abhängigkeitsalphabet h?; Di(?) durch h?; Di(?) = _ f(?0; D0) 2 Dec(?; D) j ? ? ?0g: Das ist das kleinste mit der Cographen-Dekomposition verträgliche Abhängigkeitsalphabet, daß ? umfaßt. Lemma 23 Seien M ? = M (?; D?) und M ? = M (?; D?) zwei frei partiell kommutative Monoide, erzeugt von den disjunkten Abhängigkeitsalphabeten (?; D?) und (?; D?). Dann gilt M ((?; D?) ? (?; D?)) ? = M ? ? M ? M ((?; D?) ? (?; D?)) ? = M ? ? M ? ; wobei M ? ? M ? das freie Produkt und M ? ? M ? das direkte Produkt von M ? und M ? notiert. 7.1 Der Term-Morphismus Sei Term(?; D) die Menge der wohlgeformten Terme über der Signatur D ?i j i 2 N ; ?j j j 2 N ; t j t 2 M (?; D) E ; 53 d.h. die aus den Funktionssymbolen ? und ? beliebiger Arität und den Atomen (nullstellige Terme) t 2 M (?; D) bestehenden Terme. Formal benötigen wir eigentlich eine mit Deskriptionen und Aritäten indizierte Signatur, aber der Lesbarkeit wegen verzichten wir auf diese syntaktisch schwerfällige Notation6. Wir definieren eine Abbildung h(?;D) : M (?; D) ?! Term(?; D); die jeder Spur einen solchen Term zuordnet. - Ist (?; D) nuklear, d.h. Dec(?; D) = f(?; D)g , dann ist die Abbildung die Einbettung h(?;D) : x 7?! x. - Anderenfalls sei (?; D) zerlegbar mit der Dekomposition Dec(?; D) = f(?i; Di) j i 2 [k]g und k > 1. (i) Ist das Abhängigkeitsalphabet (?; D) = ?i2[k](?i; Di) eine direkte Summe, so definieren wir für M (?; D) ? = Q i2[k] M (?i ; Di) h(?;D) : M (?; D) ?! T (t1; : : : ; tk) 7?! ?(h(?1;D1)(t1); : : : ; h(?k;Dk)(tk)) (ii) Ist (?; D) das Komplexprodukt ?i2[k](?i; Di), d.h. M (?; D) ? = ? i2[k] M (?i ; Di), dann definieren wir h(?;D) : M (?; D) ?! T t1 ? : : : ? tn 7?! ?(h(?i1;Di1 )(t1); : : : ; h(?in;Din )(tn)); wobei t1 ? : : : ? tn die gewöhnliche (alternierende) Faktorsequenz notiert mit fi1; : : : ; ing ? [k] und ij 6= ij+1 für j 2 [n ? 1] und tj 2 M (?ij ; Dij) für j 2 [n]. Ist (?; D) ein Cographen-Abhängigkeitsalphabet, so sind die Bilder Terme über der oben beschriebenen Signatur, die nur Wörter an 2 a? ? = Nfag ? = N , n 2 N , als Atome enthalten. Abhängigkeitsalphabete (?; D), die sich nicht auf diese Weise zerlegen lassen, d.h. Dec(?; D) = f(?; D)g, nennen wir nuklear. Wir nennen ein Abhängigkeitsalphabet atomar, wenn es nur einen Buchstaben besitzt. Sei T(?; D) das h(?;D)-Bild von M (?; D), also T(?; D) = h(?;D)(M (?; D)): Dann ist die Menge T(?; D) ? Term(?; D) mit dem neutralen Element h(?;D)(1) und der wie folgt induktiv definierten Verknüpfung ffi = ffi(?;D) ein Monoid. Auch hier verzichten wir auf die Indizierung. 6Bei der Implementierung der Algorithmen hat sie sich jedoch als hilfreich erwiesen, da mit dieser Indizierung festgestellt werden kann, welche Rekursionsinvokation abgearbeitet werden muß. 54 (i) Sind s = ?(s1; : : : ; sk) und t = ?(t1; : : : ; tk), so gilt s ffi t = ?(s1 ffi t1; : : : ; sk ffi tk): (ii) Sind s = ?(s1; : : : ; sm) und t = ?(t1; : : : ; tn), dann gilt s ffi t = ?(s1; : : : sm?1; sm ffi t1; t2; : : : ; tn); falls sm; t1 2 T(?i; Di) für ein i 2 [k] und die Verknüpfung setzt sich rekursiv fort. Falls sm 2 T(?i; Di) und t1 2 T(?j ; Dj) aus verschiedenen Monoiden T(?i; Di) 6= T(?j ; Dj) stammen, d.h. i 6= j, so ist das Ergebnis der Konkatenation s ffi t = ?(s1; : : : ; sm; t1; : : : ; tn) die einfache Verkettung der Argumente. (iii) Anderenfalls ist (?; D) nuklear und wir definieren die Verknüpfung via die Monoidkonkatenation s ffi t = st. Wir erhalten eine weitere Repräsentation für Spuren. Theorem 13 Die Abbildung h : M (?; D) ?! T(?; D) ist ein injektiver Homomorphismus. Beweis: Sei s; t 2 M (?; D) und h = h(?;D). Wir zeigen die Beziehung h(s ? t) = h(s) ffi h(t) mit Induktion. Ist (?; D) nuklear, so ist die Aussage trivial. Anderenfalls zerfällt (?; D) in eine Summe oder ein Komplexprodukt. Sei Dec(?; D) = f(?i; Di) j i 2 [k]g. Wir unterscheiden die Fälle (?; D) = ?i2[k](?i; Di) und (?; D) = ?i2[k](?i; Di). Ist (?; D) = ?i2[k](?i; Di), so gilt nach Lemma 23 die Isomorphie M (?; D) ? = Y i2[k] M (?i ; Di): Wir stellen ein Element x 2 Q i2[k] M (?i ; Di) als Vektor x = 0 B @ x1 ... xk 1 C A dar. Die Konkate- nation und das h-Bild berechnen sich komponentenweise. Wir schreiben für h(?i;Di) kurz hi. Damit ergibt sich mit Induktion h(s ? t) = 0 B @ h1(s1 ? t1) ... hk(sk ? tk) 1 C A = 0 B @ h1(s1) ffi h1(t1) ... hk(sk) ffi hk(tk) 1 C A = h(s) ffi h(t): Ist (?; D) = ?i2[k](?i; Di) und s = s1 ? : : : ? sn und t = t1 ? : : : ? tm mit si 2 M (?ni ; Dni) und tj 2 M (?mj ; Dmj ) n f1g, i 2 [n], j 2 [m] und ni; mj 2 [k]. Dann gilt sn 2 M (?nn ; Dnn) und t1 2 M (?m1 ; Dm1). Wir unterscheiden die zwei Fälle nn 6= m1 und nn = m1. 55 Ist nn 6= m1, so erhalten wir h(s ? t) = h(s1 ? : : : ? sn ? t1 ? : : : ? tm) = ?(hn1(s1); : : : ; hnn(sn); hm1(t1); : : : ; hmm(tm)) = ?(hn1(s1); : : : ; hnn(sn)) ffi ?(hm1(t1); : : : ; hmm(tm)) = h(s) ffi h(t) Im Fall nn = m1 erhalten wir eine alternierende Sequenz der Länge n +m? 1 s ? t = s1 ? : : : ? sn?1 ? (sn ?M (?m1 ;Dm1) t1) ? t2 ? ? : : : ? tm: Die Multiplikation sn ?M (?m1 ;Dm1 ) t1 in dem Monoid M (?nn ; Dnn) = M (?m1 ; Dm1) ist hervorgehoben, und das Resultat ist von 1 verschieden. Wir erhalten h(s ? t) = h(s1 ? : : : ? sn?1 ? (sn ? t1) ? t2 ? : : : ? tm) = ?(hn1(s1); : : : ; hm1(sn ? t1); : : : ; hmm(tm)) = ?(hn1(s1); : : : ; hnn(sn) ffi hm1(t1); hm2 ; : : : ; hmm(tm)) = ?(hn1(s1); : : : ; hnn(sn)) ffi ?(hm1(t1); : : : ; hmm(tm)) = h(s) ffi h(t) mit Induktion über die Verbandsstruktur von Dec?(?; D). Die Injektivität beweist man analog. Sei s 6= t und s; t 2 M (?; D). Ist (?; D) die Summe ?i2[k](?i; Di), so existiert eine Komponente i 2 [k] mit si 6= ti und h(s) 6= h(t) ergibt sich induktiv. Für (?; D) = ?i2[k](?i; Di) sind entweder die alternierenden Sequenzen s1 ? : : : ? sn und t1 ? : : : ? tm verschieden lang, d.h. n 6= m, oder es existiert ein Index i 2 [n] mit si 6= ti. In beiden Fällen ergibt sich die Behauptung h(s) 6= h(t) induktiv. Die Induktionsverankerung ist trivial. 7.2 Charakterisierung von Faktoren Im nächsten Lemma charakterisieren wir Faktoren in Spuren aus zerfaserten Monoiden. Lemma 24 Sei f(?i; Di) j i 2 [k]g die Dekomposition des Abhängigkeitsalphabetes (?; D). Wir notieren M i = M (?i ; Di), für i 2 [k]. Weiter sei t; l 2 M (?; D). (i) Im Fall (?; D) = ?i2[k](?i; Di) liegt t; l in Q i2[k] M i ? = M (?; D) (direktes Produkt) und es gilt t = ulv für u; v 2 M (?; D) genau dann, wenn - 8i 2 [k] : ßi(t) = ßi(u)ßi(l)ßi(v), worin ßi den Projektionshomomorphismus M (?; D) ? = Y i2[k] M (?i ; Di) ?! M i notiert. 56 (ii) Falls (?; D) = ?i2[k](?i; Di) liegt t; l in ?i2[k]M i ? = M (?; D) (freies Produkt) mit den alternierenden Sequenzen t = t1 ? : : : ? tn und l = l1 ? : : : ? lm. Dann gilt t = ulv für u; v 2 M (?; D) genau dann, wenn entweder - 9 j 2 f0g [ [n ? 2] : tj+2 = l2 ^ : : : ^ tj+m?1 = lm?1, und 9 x; y : xl1 = tj+1 ^ lmy = tj+m, oder - 9i 2 [k] : l 2 M i mit tj = xly für x; y 2 M i und ein j 2 [n]. Beweis: Die Aussage ist eine unmittelbare Konsequenz aus der Termdarstellung, siehe Theorem 13 bzw. Lemma 23. Kombinatorisch kann sie direkt aus dem Lemma von Levi hergeleitet werden. Die folgenden Abbildungen illustrieren die Situation am Abhängigkeitsgraphen. Im Falle eines direkten Produktes zerfällt der Abhängigkeitsgraph in Zusammenhangskomponenten. Tritt in den Komponenten jeweils eine Projektion von l als ein Faktor auf, so lassen sich die einzelnen Faktorprojektionen zu einem Faktor l rekombinieren. = t l = Die Faktoren l = (l1; : : : ; lk) sind in der Illustration grau hervorgehoben. Jedes Vorkommen i : lm ?! t der Projektionen lm, m 2 [k] läßt sich mit jedem anderen Vorkommen j : lm0 ?! t, m0 2 [k] kombinieren7. Im Falle eines freien Produktes unterscheiden wir die beiden Möglichkeiten n = 1 und n > 1 mit l = l1 ? : : : ? ln. Ist n > 1, so existiert in der Sequenz t = t1 ? : : : ? tm eine Position, ab der das Vorkommen beginnt und mit einem Teil der Sequenz wie in der Zeichnung angedeutet übereinstimmt. Ist n = 1, so existiert eine Position i, und ti hat den Faktor l. = t l = l = = t 7In Notation imrjm0 , d.h. die Relation r ist ein Quader I1 ? : : : ? Ik , siehe Anhang A. 57 8 Auf Dekompositionen basierende Algorithmen 8.1 Dekomposition von Ersetzungssystemen In diesem Abschnitt betrachten wir wie Dekompositionen von Ersetzungssystemen ererbt werden und wie sie bei dem Entwurf von Reduktionsalgorithmen genutzt werden können. Faktoren, die isomorph zu Elementen aus dieser Dekompositionsmenge sind, werden eine entscheidende Rolle einnehmen. Sei R ein endliches noethersches Spurersetzungssystem über einem Cographen-Monoid M = M (?; D). Wir schränken uns hier auf Cographen-Monoide ein, um die komplizierteren Betrachtungen bei Rekursionsabbrüchen zu vermeiden. Wieder bezeichnen wir mit LR die Menge der linken Seiten fl 2 M j l ! r 2 Rg. Für eine Spur t 2 M bezeichnet Pref(t) = fff 2 M j fffi = tg die Präfixe und Suff(t) = ffi 2 M j fffi = tg die Suffixe. Für Mengen S ? M definieren wir Pref(S) = [ s2S Pref(s) und Suff(S) = [ s2S Suff(s): Die Dekomposition einer linken Seite l 2 LR ist durch Dec(l) = Dec(h(l)) via Dec(?(l1; : : : ; lk)) = [ i2[k] Dec(li) [ f(l1; : : : ; lk)g Dec(?(l1; : : : ; ln)) = ? fl1 ? : : : ? lng falls n > 1 Dec(l1) [ fl1g falls n = 1 definiert. In der obigen Definition fassen wir l1 in der letzten Zeile als Subterm auf und berechnen die Dekomposition rekursiv. Läßt sich keine der obigen Gleichungen anwenden, so ist l ein Element eines nuklearen Monoids. In diesem Fall setzen wir Dec(l) = flg. Für ein Ersetzungssystem R legen wir die folgenden Mengen fest: Dec(R) = S fDec(l) j l 2 LRg die Dekomposition, Pref(R) = Pref(LR) die Präfixe und Suff(R) = Suff(LR) die Suffixe. 58 8.2 Term-Beschriftung Sei t 2 M eine Spur. Dann beschriften wir den Term h(t) mit drei Mengen. Die ersten beiden Beschriftungen P (h(t)) und S(h(t)) sind die Mengen P (h(t)) = Suff(t) \ Pref(R) und S(h(t)) = Pref(t) \ Suff(R): Die dritte Beschriftung L(h(t)) beschreibt die Positionen, an denen potentielle Faktorvorkommen von d 2 Dec(R) gefunden werden können so, daß dort eine Ersetzung möglich wird. Für freie Produkte soll diese Beschriftung auf die Stellen in der alternierenden Sequenz hinweisen, an denen eine Spur aus Dec(R) beginnt. Bei direkten Produkten soll lediglich bekannt sein, ob sich Subfaktoren von einer Spur aus Dec(R) zu einem Faktor kombinieren lassen. Formal definieren wir L(?(t1; : : : ; tk)) = [ i2[k] fd 2 M j 8i 2 [k] : ßi(d) 6= 1 ) Ldi(ti) 6= ;g L(?(t1; : : : ; tn)) = ? Ld(h(t)) ? d2Dec(R) ; wobei Ld(t) ? [n] die (geordnete) Menge natürlicher Zahlen fi1; : : : ; indg mit der Eigenschaft ij 2 Ld 8 > > > < > > > : - falls h(d) = ?(d1; : : : ; dm); m > 1 und h(t) = ?(t1; : : : ; tij?1; u ffi d1; d2; : : : ; dm?1; dm ffi v; tij+m : : : ; tn) - oder falls h(d) = ?(d1) und h(t) = ?(t1; : : : ; tij?1; u ffi d1 ffi v; tij+1; : : : ; tn) für u; v 2 h(M ). Im ersten Fall beschreibt die Position ij ein Faktorvorkommen d1 ? : : : ? dm ?! t, so daß ein echtes Präfix d1 existiert, das gleichzeitig ein Suffix des Subterms tij ist. Im zweiten Fall wird eine nicht-leere Menge von Faktorvorkommen d1 ?! t durch ij beschrieben, die in dem Subterm tij vorkommen. Ist das Monoid nuklear, d.h. t = h(t), so beschriften wir den Term mit der Menge L(t) = fi : d ?! t j d 2 Dec(R)g aller Faktorvorkommen. Da wir nur Cographen-Monoide betrachten, erhalten wir als nukleare Terme nur atomare. D.h. wir erhalten den Spezialfall (?; D) = (fag; f(a; a)g), also M (?; D) = M = fag? ? = Nfag . Das bedeutet die Menge der Faktorvorkommen am ?! an läßt sich durch L(an) = fi 2 N j 1 <= i <= n ?m + 1g = [n ?m+ 1] repräsentieren. Mit Lemma 24 existiert für h(t) = ?(t1; : : : ; tn) eine Faktorisierung t = x ? d ? y mit d 2 Dec(R) genau dann, wenn ein Index i in der Beschriftung Ld(h(t)) vorhanden ist. Für h(t) = ?(t1; : : : ; tk) gilt d 2 L(h(t)) genau dann, wenn x; y 2 M existieren mit t = x ? d ? y. 59 Wir verwenden nicht die Menge aller Kombinationen n (i1; : : : ; ik) 2 [n1] ? : : : ? [nk] fi fi fi 8j 2 [k] : ßj(d) 6= 1 =) ij 2 Ltj o ; da diese im allgemeinen von quadratischer Ordnung ist. Beispielsweise besitzt für M = fag? ? fbg?, t = ? an bn ? und d = ? a b ? die Menge aller möglichen Kombinationen von a- und b-Faktoren, [n] ? [n], die Kardinalität n2, wohingegen die Anzahl der Elemente in der Beschriftung jL(?(t1; : : : ; tk))j <= jfd2 j d1d2d3 2 Dec(R)gj = O(1) von kleiner Ordnung ist. Für ?-Terme gilt jLd(?(t1; : : : ; tn))j <= n für alle d 2 Dec(R). Wir nennen einen Term h(t) = f(s1; : : : ; sn), f 2 f?; ?g, korrekt beschriftet, wenn alle Subterme s1; : : : ; sn korrekt beschriftet sind und der Term selbst mit P (t), S(t) und L(t) beschriftet ist. 8.3 Der abstrakte Datentyp Wir repräsentieren eine Spur t 2 M als einen knotenbeschrifteten, dem Term h(t) entsprechenden Baum8. Die Knoten dieses Baums sind mit den Beschriftungen P (s), S(s) und L(s) für die repräsentierten Subterme s von h(t) versehen. Für die Datenstruktur definieren wir die Operationen SPLIT, PROJECT, COMPOSE und CONCAT so, daß die Konsistenz der Beschriftung invariant unter Anwendung dieser Operationen ist, und daß die Resultate wieder Bäume mit derselben Struktur sind. Diese Operationen ermöglichen ein Zerlegen und Zusammenfügen von Spuren in dieser Repräsentation. Diese Vorgehensweise ermöglicht es schließlich einen rekursiven Algorithmus zur Faktorisierung bzw. Normalformenberechnung zu entwerfen. Die Primitiven besitzen die folgende Semantik. (i) SPLIT(i; ?(t1; : : : ; tn)) | faktorisiert den ?-Term ?(t1; : : : ; tn) an der Stelle i 2 [n] in zwei ?-Terme ?(t1; : : : ; ti?1) und ?(ti; : : : ; tn). Die Katenation der Resultatterme ist wieder der ursprüngliche Term. (ii) PROJECT(i; ?(t1; : : : ; tk)) | extrahiert den Term ti, i 2 [k]. (iii) COMPOSE(t1; : : : ; tk) | rekombiniert die Terme ti der Spuren t0 i = h?1(ti) 2 M i , i 2 [k] so, daß der Resultatterm ?(t1; : : : ; tk) die Spur (t0 1; : : : ; t0 k) 2 Q i2[k] M i darstellt. Die Anzahl der Argumente hängt nur vom zugrundeliegenden induzierten Abhängigkeitsalphabet ab. Da wir nicht-uniforme Algorithmen untersuchen ist diese Anzahl durch eine konstante beschränkt. Es gilt k 2 O(j(?j) = O(1). Die Terme ti sind ?-Terme oder Atome, und es sollen nur solche Invokationen auftreten, so daß der berechnete Term wieder ein h-Bild ist. 8Ein geordneter Baum stellt einen Term dar, wenn die Blätter die nullstelligen Symbole sind und die inneren Knoten (mit den entsprechenden Funktionssymbolen markiert) den Funktionssymbolen von nicht-atomaren Subtermen entsprechen. 60 (iv) CONCAT(t1; t2) | berechnet die Katenation t1 ffi t2 der Argumentterme. Zur Komplexitätsanalyse der unten vorgestellten Algorithmen benötigen wir noch das folgende Lemma. Lemma 25 Seien t; l 2 M (?; D) Spuren, die durch den Baum h(t), bzw. h(l) repräsentiert sind. Atomare Terme an seien durch Strings repräsentiert. Dann können die Prädikate (i) l 2 Pref(t), (ii) l 2 Suff(t) und (iii) l = t in O(min(jtj; jlj)) Zeiteinheiten entschieden werden. Beweis: (iii) folgt aus (i) und (ii) mit t = l () (l 2 Pref(t)) ^ (t 2 Pref(l)). PREDICATE PREF(l; t) Comment Input: two traces in representation. Output: boolean (l 2 Pref(t)). Method if h(t) = ?(t1; : : : ; tm) and h(l) = ?(l1; : : : ; ln) then if m < n then return (false) else for all 1 <= i <= n ? 1 do if ti 6= li then return (false) end if end for return(PREF(ln; tn)) end if else if h(t) = ?(t1; : : : ; tm) and h(l) = ?(l1; : : : ; ln) then if m 6= n then error else for all (1 <= i <= m) do if not PREF(li; ti) then return (false) end if end for return(true) end if else if t; l 2 a? are basic representations then if jtj < jlj then return (false) else return (true) end if otherwise error end Method Mit der Charakterisierung in Lemma 24 folgt, daß PREF(t; l) = true genau dann, wenn l 2 Pref(t). Genauer gilt für t = ?(t1; : : : ; tm) und l = ?(l1; : : : ; ln) t = l ffi u () 8i 2 [n ? 1] : ti = li ^ dn 2 Pref(tn); 61 und für t = ?(t1; : : : ; tm) und l = ?(l1; : : : ; ln) t = l ffi u () m = n ^ 8i 2 [m] : li 2 Pref(ti): Der Fall l; t 2 a? ist offensichtlich korrekt. Die Komplexität ist O(min(jlj; jtj)), da bei jeder Invokation beide Argumentstrukturen | aufsummiert über alle rekursiven Aufrufe | entweder sich um mindestens ein Funktionssymbol verkleinern oder das Resultat nach dem Lesen der kleineren der beiden Strukturen feststeht. Sei T (l; t) der Zeitaufwand zum Entscheiden der drei Prädikate. Dann gilt für die Präfixberechnung T (?(t1; : : : ; tm); ?(l1; : : : ; ln)) T (?(t1; : : : ; tm); ?(l1; : : : ; ln)) ö = O(1) + X i<=min(m;n) T (ti; li) T (at; al) = O(1) + T (l; t), wenn l; t 2 a?. Da P i2[m] jh?1(ti)j = jtj für alle t mit h(t) = ?(t1; : : : ; tm) oder h(t) = ?(t1; : : : ; tm) gilt, folgt (i) und dual (ii) mit Induktion. Bemerkung 4 Dieses Resultat gilt nicht nur für Spuren aus Cographen-Monoiden. Für alle Darstellungen gilt die rekursive Beziehung al 2 Pref(at) () l 2 Pref(t); die für nukleare Terme verwendet werden kann. Minimale Buchstaben a in beispielsweise einem Hasse-Diagramm oder die diese Buchstaben repräsentierenden Buchstaben in den Wörtern tC = at0 C , a 2 C 2 C, eines Worttupels (tC)C2C lassen sich in O(j?j) = O(1) finden. Diese t 2 M repräsentierenden Strukturen besitzen maximal O(j?j ? jtj) = O(jtj) Knoten bzw. Kanten bzw. Funktionssymbole. 8.3.1 Algorithmische Primitive Es folgen die Beschreibungen der Methoden zu den oben aufgeführten Operationen. Die Algorithmen werden im Laufe einer Berechnung nur strukturverträgliche Terme, d.h. Terme h(?;D?)(t) und h(?;D?)(t) mit (?; D?) = (?; D?), so verknüpfen, daß die resultierende Terme wieder wohlstrukturiert sind. SPLIT Die zulässigen Eingaben von SPLIT sind korrekt beschriftete Terme ?(t1; : : : ; tn) und Zahlen i 2 [n + 1]. Das Resultat ist das Termpaar h?(t1; : : : ; ti?1); ?(ti; : : : ; tn)i mit korrekter Beschriftung. 62 FUNCTION SPLIT(i; ?(t1; : : : ; ti; : : : ; tn)) Comment Input: a natural number and a trace representation. Output: the representation of two traces according to the semantic. Method if (1 < i <= n) then ht0 1; t0 2i h?(t1; : : : ; ti?1); ?(ti; : : : ; tn)i P (t0 1) P (ti?1) [ fl1 ? : : : ? lj 2 Pref(R) jt1 ? : : : ? ti?1 = ffl1 ? : : : ? lj; j > 1g P (t0 2) P (tn) [ fl1 ? : : : ? lj 2 Pref(R) j ti ? : : : ? tn = ffl1 ? : : : ? lj; j > 1g S(t0 1) S(t1) [ fl1 ? : : : ? lj 2 Suff(R) j t1 ? : : : ? ti?1 = l1 ? : : : ? ljfi; j > 1g S(t0 2) S(ti) [ fl1 ? : : : ? lj 2 Suff(R) j ti ? : : : ? tn = l1 ? : : : ? ljfi; j > 1g for all d 2 Dec(R) do Ld(t0 1) (Ld(t) \ [i ? 1]) ? fi ? j ? 1 jd1 2 P (t0 1); d2 2 S(t0 2); d1 6= 1 6= d2 h(d1) = ?(d0 1; : : : ; d0 j); with h = hh?;Di(?(t)) d1d2 = dg Ld(t0 2) Ld(t) \ fi; : : : ; ng end for return (ht0 1; t0 2i with labeling S; P; L, resp.) else if i = 1 then return(h1; ?(t1; : : : ; tn)i) end if else if i = n + 1 then return(h?(t1; : : : ; tn); 1i) end if with empty labeling (S = P = ;) for 1 and the old labeling for ?(t1; : : : ; tn) otherwise error end Method Durch die Zuweisungen P (t0 1) P (ti?1) [ fl1 ? : : : ? lj 2 Pref(R) j t1 ? : : : ? ti?1 = ffl1 ? : : : ? lj; j > 1g P (t0 2) P (tn) [ fl1 ? : : : ? lj 2 Pref(R) j ti ? : : : ? tn = ffl1 ? : : : ? lj; j > 1g S(t0 1) S(t1) [ fl1 ? : : : ? lj 2 Suff(R) j t1 ? : : : ? ti?1 = l1 ? : : : ? ljfi; j > 1g S(t0 2) S(ti) [ fl1 ? : : : ? lj 2 Suff(R) j ti ? : : : ? tn = l1 ? : : : ? ljfi; j > 1g werden die Präfix- und Suffixbeschriftungen für beide Resultatterme berechnet. Dabei wird die rekursive Struktur, die auch im Entscheidungsalgorithmus PREF verwendet wird, genutzt. In der for-Schleife werden anschließend die L-Beschriftungsfamilien ermittelt, indem die Listen Ll in Teile gespalten werden, die zu den resultierenden Termen korrespondieren, und die Markierungen, die in dem ersten Term beginnen und im zweiten enden, entfernt werden. Offensichtlich gilt folgendes Lemma. Lemma 26 Sei t = ?(t1; : : : ; tn) ein korrekt beschrifteter Term und i 2 [n + 1]. Dann ist das Resultat SPLIT(i; t) ein Paar (t0; t00) von korrekt beschrifteten Termen mit t0 = ?(t1; : : : ; ti?1) und t00 = ?(ti; : : : ; tn). Die Beschriftungen P und S können in O( P l2Dec(R) jlj) = O(1) mit Lemma 25 bruteforce berechnet werden. Der Algorithmus nützt jedoch die hierarchische Struktur der Dekompositionen, um Mehrfachberechnungen zu vermeiden. 63 Der Rumpf in der for-Schleife zur Berechnung der L-Beschriftungen kann ohne weitere Datenstrukturen nicht in konstanter Zeit bearbeitet werden. Das Aufspalten der (geordneten) Mengen erfordert bei einer Implementierung durch beispielsweise eine Familie von Listen im worst-case O(n) Zeiteinheiten. Eine Effizienzsteigerung erreicht man durch Verwenden der in Kapitel 5.2 beschriebenen C?-Baume mit C = N . D.h. die Mengen Ll werden durch Bäume dargestellt, deren Blätter zu Positionen i 2 N korrespondieren. Jede der Mengen Ld läßt sich dann in O(log jLdj) = O(log n) Zeit mit der Splitoperation für C?-Bäume separieren, woraus die (nicht-konstante) Laufzeit O(log n) resultiert. Wir erhalten Lemma 27 Sei t = ?(t1; : : : ; tn) ein korrekt beschrifteter Term und i 2 [n + 1]. Dann terminiert die effiziente Implementierung nach Aufruf mit SPLIT(i; t) in O(log n) Zeiteinheiten. Man beachte, daß das Argument i als Zeiger interpretiert werden kann. Dann entfällt die logarithmische Suche in der komplexen Zuweisung ht0 1; t0 2i h?(t1; : : : ; ti?1); ?(ti; : : : ; tn)i; aber die Partitionierungen der Mengen (Listen) Ld(t0 1) (Ld(t) \ [i ? 1]) ? fi ? j j d1 2 P (t0 1); d2 2 S(t0 2); d1 6= 1 6= d2; hh?;Di(?(t))(d1) = ?(d0 1; : : : ; d0 j); d1d2 = dg Ld(t0 2) Ld(t) \ fi; : : : ; ng benötigen ohne zusätzliche Information logarithmische Zeit mit N-Bäumen. Man beachte, daß der Homomorphismus h = hh?;Di(?(t)) derselbe wie bei h(t) = ?(t1; : : : ; tn) ist. Eine Verbesserung der Konstanten erhält man, indem nur verträgliche Faktorisierungen von d = ?(d0 1; : : : ; d0 n) betrachtet werden. Das sind die n ? 1 Faktorisierungen in n? ? (d0 1); ?(d0 2; : : : ; d0 n) ? ; ? ? (d0 1; d0 2); ?(d0 3; : : : ; d0 n) ? ; : : : ; ? ? (d0 1; : : : ; d0 n?1); ?(d0 n) ?o : Durch Verzichten auf die Operation SPLIT werden wir später einen Linearzeitalgorithmus angeben können. PROJECT Die Methode PROJECT ergibt sich aus der rekursiven Definition der Beschriftung. FUNCTION PROJECT(i; ?(t1; : : : ; ti; : : : ; tk)) Comment Input: a natural number and a trace representation. Output: the representation of a trace according to the semantic. 64 Method if (1 <= i <= k) then return(ti) otherwise error end Method Offensichtlich benötigt die Methode O(k) = O(1) Zeiteinheiten, da wir das Abhängigkeitsalphabet (?; D) als fest annehmen. Wir erhalten Lemma 28 Sei t = ?(t1; : : : ; tk) ein korrekt beschrifteter Term und i 2 [k]. Dann ist das Resultat von PROJECT(i; t) der korrekt beschriftete Term h(ßi(h?1(t))) wobei ßi die i-te Projektion M ? = Q j2[k] M j ?! Mi ist. COMPOSE Invers zu PROJECT fügt COMPOSE Terme zu einem Produktterm zusammen. FUNCTION COMPOSE(t1; : : : ; tk) Comment Input: a tupel of trace representations. Output: the representation of a trace according to the semantic. Method if ?(t1; : : : ; tk) is a well formed term w.r.t. the corresponding submonoid then t ?(t1; : : : ; tk) S(t) Q 1<=i<=k S(ti) \ Suff(R) P (t) Q 1<=i<=k P (ti) \ Pref(R) L(t) ; for all d 2 Dec(R) do let h(d) = ?(d1; : : : ; dk) a term corresponding to the structure of t B true for all 1 <= i <= k do B B ^ (Ldi 6= ;) end for if B then L(t) L(t) [ fdg end if end for return(t with labeling S; P; L) otherwise error end Method Die Semantik der zwei komplexen Zuweisungen S(t) Y 1<=i<=k S(ti) \ Suff(R) P (t) Y 1<=i<=k P (ti) \ Suff(R) 65 ist eine komponentenweise Analyse der Kombination der Prä- bzw. Suffixvorkommen. Die Korrektheit folgt wieder aus Lemma 24. Für Präfixe gilt bei strukturgleichen Termen ?(d1; : : : ; dk) 2 Pref(?(t1; : : : ; tk)) () 8i 2 [k] : di 2 Pref(ti): Auch hier ist eine brute-force Berechnung möglich, verschlechtert aber die Konstanten. Für Suffixe gilt Duales. Die Korrektheit der L-Beschriftung folgt aus Lemma 24 ?(t1; : : : ; tk) = u ffi ?(d1; : : : ; dk) ffi v () 8i 2 [k] : h(ßi(h?1(u))) ffi di ffi h(ßi(h?1(v))) mit Induktion. Man beachte, die induzierten Abhängigkeitsalphabete sind paarweise disjunkt. Wir erhalten Lemma 29 Seien ti korrekt beschriftete Spurterme mit den induzierten paarweise disjunkten Abhängigkeitsalphabeten (?i; Di) = h?; Di(?(ti)), i 2 [k]. Ist ?i2[k](?i; Di) 2 Dec?(?; D), dann berechnet COMPOSE(t1; : : : ; tk) den Term ?(t1; : : : ; tk) mit korrekter Beschriftung. Auch diese Methode benötigt O(j?j ? (jDec(R)j + jSuff(R)j + jPref(R)j)) = O(1) Zeit. CONCAT Unter Verwendung der bereits vorgestellten Methoden können wir einen Algorithmus für die Katenation ableiten. Wir verfahren dabei wie in der Definition von ffi im vorigem Kapitel. FUNCTION CONCAT(t1; t2) Comment Input: two trace representations. Output: the representation of the catenation. Method if t1 = ?(t0 1; : : : ; t0 k) and t2 = ?(t00 1; : : : ; t00 k) then for all (1 <= i <= k) do ht1 i ; t2 i i hPROJECT(i; t1), PROJECT(i; t2)i t000 i CONCAT(t1 i ; t2 i ) end for return (COMPOSE(t000 1 ; : : : ; t000 k )) else if t1 = ?(t0 1; : : : ; t0 n1) and t2 = ?(t00 1; : : : ; t00 n2) then if t0 n1 2 M i 6= M j 3 t00 1, where M = ?i2[k]M i then s ?(t0 1; : : : ; t0 n1; t00 1; : : : ; t00 n2) let s = ?(s1; : : : ; sn) P (s) P (sn) [ fl1 ? : : : ? lj 2 Pref(R) j 66 s1 ? : : : ? sn = ffl1 ? : : : ? lj; j > 1g S(s) S(s1) [ fl1 ? : : : ? lj 2 Suff(R) j s1 ? : : : ? sn = l1 ? : : : ? ljfi; j > 1g for all d 2 Dec(R) do Ld(s) Ld(t1) [ Ld(t2)[ fn1 ? i j hh?;Di(?(s))(d) = ?(d1; : : : ; dm); m > 1 ?(d1; : : : ; di) 2 P (t1); ?(di+1; : : : ; dm) 2 S(t2)g end for else hs0 1; s0 2i SPLIT(n1; t1) hs00 1; s00 2i SPLIT(2; t2) s CONCAT(s0 1;CONCAT(CONCAT(s0 2; s00 1); s00 2)) end if return s with labeling P; S; L else if t1 2 a? and t2 2 a? then let t1 = an and t2 = am t an+m for all d 2 Dec(R) \ a? do Ld [n +m+ 1 ? jdj] end for end if return s with labeling P; S; L otherwise error end Method Sind die zwei Eingabeparameter korrekt beschriftete Spurterme der Form ?(x1; : : : ; xk), so führen wir die Konkatenation auf k Konkatenationen der durch PROJECT berechneten Subterme zurück. (Diese sind natürlich nur definiert, falls t1 = h(?;D)(~t1) und t2 = h(?;D)(~t2) dieselbe Struktur besitzen. Die Resultate werden anschließend mit COM- POSE zu einem korrekt beschrifteten Spurterm zusammengefügt. Besitzen die Terme die Form ?(x1; : : : ), so wird entsprechend der Definition der Konkatenation ffi verfahren. Der rekursive Fall wird entsprechend der Definition unter Verwendung der Operationen SPLIT und CONCAT (für ein Monoid, das von einem Abhängigkeitsalphabet, das sich unter (?; D) bzgl. der Verbandsordnung in Dec?(?; D) befindet) bearbeitet. Der verbleibende Fall wird durch Fusionieren der beiden Bäume an der Wurzel bearbeitet. Ist das Abhängigkeitsalphabet (?; D) atomar, so verwendet man die Konkatenationsoperation auf der Wortrepräsentation. D.h. die beiden Strings an und am müssen konkateniert werden. Existiert ein d 2 Dec(R), das vollständig in einem atomaren Submonoid a? liegt, so muß die L-Beschriftung durch die Menge [n +m+ 1 ? jdj] bzw. die diese Menge repräsentierende Zahl n +m + 1 ? jdj aktualisiert werden. Lemma 30 Seien t1 und t2 zwei korrekt beschriftete Spurterme aus h(M ). Dann berechnet die Funktion CONCAT den korrekt beschrifteten Spurterm t1 ffi t2. Man beachte COMPOSE, PROJECT, SPLIT und auch mit Induktion CONCAT berechnen korrekt beschriftete Terme. 67 Lemma 31 Seien t1 und t2 korrekt beschriftete Terme. Dann terminiert der Algorithmus CONCAT in O(log jt1j + log jt2j + 1) Zeiteinheiten. Beweis: Sei Dec(?; D) = f(?i; Di) j i 2 [k]g. Im Fall t1 = ?(t0 1; : : : ; t0 k) und t2 = ?(t00 1; : : : ; t00 k) erhalten wir für die Komplexität TCONCAT(t1; t2) O ?X i2[k] ? TCONCAT(t0 i; t00 i ) + TPROJECT(t1) + TPROJECT(t2) ? + TCOMPOSE(t000 1 ; : : : ; t000 k ) + 1 ? = O(log jt1j + log jt2j + 1) Für t1 = ?(t0 1; : : : ; t0 n1) und t2 = ?(t00 1; : : : ; t00 n2) erhalten wir TCONCAT(t1; t2) = O(1 + TSPLIT(t1) + TSPLIT(t2) + TCONCAT(t0 n1 ; t00 1)) = O(log jt1j + log jt2j + 1) mit der effizienteren Implementierung von SPLIT. Für die Basisfälle gilt in dieser Repräsentation die Beziehung TCONCAT(t1; t2) = O(j?j + jDec(R)j) = O(1): 8.3.2 Quotientenberechnung Sei t = uv 2 M . Dann bezeichnen wir u?1t = v als Linksquotienten und tv?1 = u als Rechtsquotienten. Ersetzungen werden wir durch Berechnen der Quotienten d?1 2 t2 und t1d?1 1 für Faktorisierungen d1d2 2 LR und t1t2 = t durchführen. Analog wie bei CONCAT verwenden wir auch zur Quotientenberechnung die primitiven Operationen zur Formulierung eines rekursiven Berechnungsverfahrens. FUNCTION rightQUOTIENT(t; l) Comment Input: two trace representations. Output: the representation of the quotient tl?1. Method if l = 2 P (t) then error else if t = ?(t1; : : : ; tk) and l = ?(l1; : : : ; lk) then for all (1 <= i <= k) do si rightQUOTIENT(PROJECT(i; t), PROJECT(i; l)) end for return (COMPOSE(s1; : : : ; sk)) else if t = ?(t1; : : : ; tn) and l = ?(l1; : : : ; lm) 68 then if m = 1 then hs1; s2i SPLIT(n; t) interprete s2 as ?-term return (CONCAT(s1;rightQUOTIENT(s2; l1))) else hs; t0i SPLIT(n ?m+ 1; t) hl0; l00i SPLIT(2; l) return (rightQUOTIENT(s; l0)) end if else if t 2 a? and l 2 a? and jlj <= jtj then let t = an and l = am t an?m for all d 2 Dec(R) \ a? do Ld [n ?m+ 1 ? jdj] end for return t with labeling P; S; L otherwise error end Method Wir erhalten das folgende Lemma. Lemma 32 Seien t; l 2 h(M ), l 2 Dec(R zwei korrekt beschriftete Spurterme und h?1(l) sei ein Suffix von h?1(t), d.h. h?1(l) 2 P (t). Dann berechnet die Funktion right- QUOTIENT einen korrekt beschrifteten Spurterm tl?1. Die Komplexität wird von der Zeit für ein SPLIT zu O(log jtj + log jlj) (mit der effizienteren Implementierung von SPLIT) bestimmt. Da wir uns auf Quotientenberechnungen tu?1, u 2 Pref(LR) beschränken, würde konstante Zeit ausreichen, denn für alle modifizierenden Operationen existieren Zugriffspfade auf die entsprechenden Teile der Datenstruktur. So ließen sich die Beschriftungslisten durch lineares Sondieren von maximalen Elementen aus in konstanter Zeit aktualisieren. Aber, da wir die Zugriffsstruktur für SPLIT noch verwalten, besitzt diese Realisierung die Komplexität O(log jtj). 8.4 Dekomponierbarkeit Um die komplizierten Basisfälle zu umgehen haben wir nur Cographen-Monoide betrachtet. Mit den gleichen Methoden lassen sich Algorithmen für eine größere Klasse von Spurmonoiden angeben. Die Basisfälle, bei denen die Rekursionen terminieren, lassen sich entsprechend verallgemeinern, so daß die Algorithmen die selbe Zeitkomplexität besitzen. Ein Abhängigkeitsalphabet ist bzgl. des Ersetzungssystems R dekomponierbar oder zerlegbar, wenn die Menge Z(R) nur atomare Spuren d 2 a?, a 2 ?, oder Spuren, die sich über ein freies Produkt faktorisieren, enthält. D.h. für alle d 2 Z(R) gilt h(d) = ?(d1; : : : ; dn) mit n > 1 oder d 2 a?. Dabei ist Z(R) = S l2LR Z(h(l)) und 69 Z(h(l)) ist rekursiv wie folgt definiert: Z(?(l1; : : : ; lk)) = S i2[k] Z(li) Z(an) = fang a 2 ?; n 2 N Z(?(l1; : : : ; lk)) = ? f?(l1; : : : ; lk)g n > 1 Z(l1) n = 1 Damit gilt für d 2 Dec(R) entweder, daß die entsprechende Beschriftung von Subtermen ererbt werden kann, oder d 2 Z(R). Die Laufzeit der Algorithmenteile für die Basisfälle aus Z(R) bei zerlegbaren Abhängigkeitsalphabeten liegt in O(1). Bemerkung 5 Cographen-Abhängigkeitsalphabete sind bzgl. jedem (noetherschen) Ersetzungssystem dekomponierbar. Wir betrachten fortan trotzdem nur Cographen-Monoide, da die Formulierung der Basisfälle komplizierter ist. 8.5 Ein O(n log n)-Reduktionsalgorithmus Die dem folgenden Algorithmus zugrundeliegende Idee ist ein iteriertes Durchführen von Reduktionen " von links nach rechts\, wie in dem folgenden Algorithmenskelett dargestellt. v 1; while t 6= 1 do let t = at0 for some a 2 ?; t0 2 M ; v := va; t := t0; if v = v0l for some l ! r 2 R then v v0; t rt end if end while return v Die Algorithmenskelett berechnet ein Derivat v der Spur t, t ? =)R v. Die Spur v ist aber nach Verlassen der Schleife nicht notwendigerweise irreduzibel, wie das Beispiel zeigt. Beispiel 6 Sei (?; D) = [a ? b ? c ? d], t = abanabcddmcd und R = fabcd ! 1g. Dann berechnet der Algorithmus die Derivation t = aban ? abcd ? dmcd =)R abandmcd = t0 = 2 Irr(R); denn die Spur t = " a b an a b c d dm c d # 70 wird auf t0 = 2 6 6 4 c dm d a b an 3 7 7 5 reduziert. Die Faktoren aus LR sind mit Polygonzügen markiert. Dieses Beispiel illustriert auch, daß durch Zurücksetzen über einen gelesenen Teil konstanter Größe die Irreduzibilität nicht zugesichert werden kann. Die folgende Methode CONCATandREDUCE vermeidet diesen Effekt durch Nutzen der Termstruktur. Die Auswahl einer Faktorisierung Die Methode FACTORIZE berechnet eine Faktorisierung t1 ? t2 von t so, daß t einen Faktor l 2 Dec(R) an der Schnittstelle enthält, d.h. t = t0 1lt0 2, wobei ein Präfix von l ein Suffix von t1 ist, und das ergänzende Suffix von l ein Präfix von t2 ist. D.h. l = l1l2, t1 = t0 1l1 und t2 = l2t0 2. Dabei werden Faktorisierungen betrachtet, die sich an der Termstruktur orientieren. Die L-Beschriftungen ermöglichen ein zielgerichtetes navigieren in dem Term darstellenden Baum. PROCEDURE FACTORIZE(l; t) Comment Input: a trace representation. Output: the factorization according to the semantic. Method if t = ?(t1; : : : ; tn) and Ll(t) 6= ; then choose j 2 Ll(t) e.g. j minLl(t) if l = ?(l1; : : : lm) with m > 1 then return (SPLIT(t; j + 1)) else l = ?(l1) ht0; t00i SPLIT(t; j) hu; vi SPLIT(t00; 2) interprete u as ?-term hx; yi FACTORIZE(l; u) return(hCONCAT(t0; x);CONCAT(y; v)i) end if else if t = ?(t1; : : : ; tk) and l = (l1; : : : ; lk) 2 L(t) for all (1 <= j <= k) do tj PROJECT(t; j) huj; vji FACTORIZE(lj; tj) end for return(hCOMPOSE(u1; : : : ; uk);COMPOSE(v1; : : : ; vk)i else if t 2 a? and L(t) 6= ; then return(ha; ajtj?1i) 71 (with maintained labeling) else if l = 1 then return (h1; ti) otherwise there is no factorization possible end Method Wieder führt eine zu oben analoge Fallstudie zu dem folgenden Lemma. Lemma 33 Sei t 2 h(M ) ein korrekt beschrifteter Spurterm mit h?1(t) = u ? l ? v für ein l 2 Dec(R). Dann berechnet FACTORIZE(l; t) ein Paar von korrekt beschrifteten Spurtermen ht1; t2i mit t = t1 ffi t2, l = l1l2, sowie l1 2 P (t1) und l2 2 S(t2). Insbesondere berechnet FACTORIZE für jede linke Seite l 2 LR, die als Faktor in einer Spur t = ulv vorkommt, eine Faktorisierung t = t1t2 mit t1 = ul1 und t2 = l2v für zwei Spuren l1; l2 mit l1l2 = l. Die Komplexität beträgt O(log jtj) (mit der effizienteren Implementierung von SPLIT). Die Datenstruktur C?-Baum ermöglicht den Zugriff auf das minimale Element minLl(t) in logarithmischer Zeit. Da die Positionen über die C?-Bäume vergleichbar sind, können so Faktorisierungen t = t1 ? t2 mit t1 2 M n M lM für Links-Derivationen berechnet werden. Eine Reduktionsmethode für Links-Derivationen Die Intention dieses Entwurfs ist es, daß die folgenden Zusicherungen invariant gegenüber Reduktionsschritten sind. (i) Der Resultatterm ist ein korrekt beschrifteter Spurterm. (ii) Der Resultatterm ist ein Links-Derivat von der Konkatenation der Eingabe. (iii) Ist die erste Komponente der Eingabe irreduzibel, so ist auch das Resultat irreduzibel. In natürlicher Weise erhält man einen Reduktionsalgorithmus vom Book-Typ. PROCEDURE CONCATandREDUCE(s; t) Comment Input: two trace representations. Output: a descendant of st. Method if exists l = l1l2 ! r 2 R with l1 2 S(s) and l2 2 P (t) then then let l be minimal choosen s0 rightQUOTIENT(s; l1) t0 leftQUOTIENT(t; l2) return(CONCATandREDUCE( CONCATandREDUCE(s0; r); t0)) 72 else if s = ?(s1; : : : ; sk) and t = ?(t1; : : : ; tk) and there exists l ! r with l = (l1; : : : ; lk) 2 L(s ffi t) let l be minimal choosen then for all i 2 [k] do si PROJECT(s; i) ti PROJECT(t; i) if Lli(si) 6= ; then hs0 i; s00 i i FACTORIZE(li; si) si s0 i ti CONCAT(s00 i ; ti) else if li = l0 il00 i with l0 i 2 P (si), l00 i 2 S(ti) then do nothing else ht0 i; t00 i i FACTORIZE(li; ti) si CONCAT(si; t0 i) ti t00 i end if end if end for s COMPOSE(s1; : : : ; sk) t COMPOSE(t1; : : : ; tk) let l = l1 ? l2 with l1 2 P (s) and l2 2 S(t) s0 rightQUOTIENT(s; l1) t0 leftQUOTIENT(t; l2) return(CONCATandREDUCE( CONCATandREDUCE(s0; r); t0)) else if s = ?(s1; : : : ; sn) and t = ?(t1; : : : ; tm) .... Comment analogous as in the direct product case | we skip this part otherwise st 2 Irr(R) return(CONCAT(s; t)) end Method Seien s und t die Eingaben. Existiert eine Faktorisierung, so daß ein Präfix einer linken Seite ein Suffix von s und das zugehörige Suffix dieser linken Seite ein Präfix von t ist, dann werden die entsprechenden Quotienten und Konkatenationen durchgeführt, um dieses Vorkommen zu ersetzten. Existiert keine solche Faktorisierung, so wird eine entsprechende berechnet, indem Teile von t an s bzw. Teile von s an t konkateniert werden. Im Falle eines direkte Produktes ist die Beschreibung dieser Berechnung ausgeführt. Der atomare Fall ist trivial, und bei freien Produkten verfährt man entsprechend. Existiert keine Faktorisierung dieser Art, so ist der Spurterm s ffi t irreduzibel und wir können die Konkatenation als Resultat ausgeben. Lemma 34 Seien s; t 2 h(M ) und R ein noethersches Ersetzungssystem. M ist ein Cographen-Monoid. 73 (i) Der Resultatterm h(t0) von CONCATandREDUCE(s; t) ist ein korrekt beschrifteter Spurterm. (ii) Es gilt h?1(s) ? h?1(t) ? =)R t0. (iii) Aus h?1(s) 2 Irr(R) folgt t0 2 Irr(R). Beweis: Seien s und t wie oben Spurterme gleicher Struktur. Da nur die oben eingeführten Operationen und CONCATandREDUCE auf s und t angewendet werden ist das Resultat mit Induktion über die Anzahl der Transformationen CONCAT, SPLIT, PROJECT, COMPOSE, FACTORIZE, rightQUOTIENT und leftQUOTIENT mit den vorhergehenden Lemmata wieder ein korrekt beschrifteter Spurterm. Die verbleibenden Behauptungen zeigen wir simultan. Ist die Bedingung der ersten Verzweigung erfüllt, so ist das Resultat ein Derivat von s ffi t: st = s0l1l2t0 = s0lt0 =)R s0rt0 ? =)R ^t Der Übersichtlichkeit wegen identifizieren wir t mit h(t). Da jeder Rechtsquotient einer irreduziblen Spur wieder irreduzibel ist, bleibt das erste Argument irreduzibel, und wir erhalten die dritte Aussage. Besteht die Eingabe aus zwei ?-Termen s = ?(s1; : : : ; sk) und t = ?(t1; : : : ; tk). Dann finden wir nach Lemma 24 einen Faktor (l1; : : : ; lk) genau dann, wenn für alle i 2 [k] sich die Komponenten h?1(si ffi ti) = uilivi faktorisieren lassen. Nach Wahl der linken Seite wird eine Faktorisierung gefunden so, daß das erste Argument irreduzibel bleibt. Das kann beispielsweise via FACTORIZE geschehen. Durch eine erschöpfende Suche, in der über alle linken Seiten, die als Faktoren vorkommen, variiert wird, läßt sich in logarithmischer Zeit eine Faktorisierung u ? l ? v mit u 2 Irr(R) finden. Man Beachte, daß in konstanter Zeit entschieden werden kann, ob ein beschrifteter Term irreduzibel ist. Damit bleibt das erste Argument irreduzibel, wenn s und t ?-Terme sind. Das Resultat ist ebenfalls ein Derivat: 0 B @ s1 ... sk 1 C A 0 B @ t1 ... tk 1 C A = 0 B @ v1 ... vk 1 C A = 0 B @ v0 1 ... v0 k 1 C A 0 B @ v00 1 ... v00 k 1 C A = 0 B @ v0 1(l1 1)?1 ... v0 k(l1 k)?1 1 C A l 0 B @ (l2 1)?1v00 1 ... (l2 k)?1v00 k 1 C A =)R 0 B @ v0 1(l1 1)?1 ... v0 k(l1 k)?1 1 C A r 0 B @ (l2 1)?1v00 1 ... (l2 k)?1v00 k 1 C A Für ?-Terme und atomare Terme führen wir den Beweis nicht aus. Korollar 11 Sei t 2 M eine Spur, dann gilt für den resultierenden Spurterm h(^t) = CONCATandREDUCE(1; h(t)); t ? =)R ^t 2 Irr(R). 74 Bemerkung 6 Wir hätten die Spuren zuerst konkatenieren können, und auf der so entstandenen Spur wäre ein sukzessives Reduzieren möglich gewesen. Diese Darstellung verdeutlicht jedoch die Problematik des Auffindens eines einer Faktorisierung u ? l ? v im Falle eines direkten Produkts. Man beachte die rekursiven Verflechtungen bei der Berechnung einer Faktorisierung . Die " gierige\ Vorgehensweise bei diesem Entwurf ähnelt der von Books Algorithmus. Außerdem kann die selbe Methode auch zur Konstruktion der Datenstruktur genutzt werden. Verwendet man die Methode FACTORIZE, so wird der Algorithmus sehr viel übersichtlicher und der Korrektheitsbeweis nahezu trivial. PROCEDURE REDUCE+(t) Comment Input: trace representation. Output: the representation of the normal form. Method while 9l 2 LR with (l = l1 ? : : : ? lm and Ll(t) 6= ; or l = (l1; : : : ; lk) and l 2 L(t) 6= ;) and l ! r 2 R do hu; vi FACTORIZE(l; t) let l = l1l2 with l1 2 P (u) and l2 2 S(v) s CONCAT(leftQUOTIENT(u; l1); r) t CONCAT(rightQUOTIENT(s; l2); v) end while return(t) end Method Lemma 35 Die Methode CONCATandREDUCE(h(s); h(t)) = h(t0) benötigt maximal O(n) primitive Operationen, wobei n die maximale Anzahl der Ersetzungen st n =)R t0 ist. Beweis: Bei jedem Aufruf von CONCATandREDUCE wird, falls existent, l in st durch r für eine Regel l ! r 2 R ersetzt. Dazu sind nur konstant viele komplexe Elementaroperationen notwendig. Wir erhalten damit das folgende Komplexitätsresultat. Theorem 14 Sei (?; D) ein Cographen-Abhängigkeitsalphabet und R ein noethersches Ersetzungssystem über M = M (?; D). Dann kann für eine Spur t 2 M eine Links- Derivation t ? =)R ^t in O(dR log dR) berechnet werden. Korollar 12 Sei (?; D) ein Cographen-Abhängigkeitsalphabet und R ein gewichtsreduzierendes Ersetzungssystem über M = M (?; D). Dann kann für eine Spur t 2 M eine Links-Derivation t ? =)R ^t in O(jtj log jtj) berechnet werden. 75 Man beachte, daß mit diesem Algorithmus auch Ersetzungssystem mit nicht-zusammenhängenden linken Seiten bearbeitet werden können. Bemerkung 7 Dieses Resultat läßt sich auf dekomponierbare Abhängigkeitsalphabete verallgemeinern. Die Behandlung der Spuren über nuklearen Alphabeten ist bei allen Algorithmen in der Worttupel-Repräsentation dann innerhalb der angegebenen Zeitgrenzen möglich. Theorem 15 Sei (?; D) ein Abhängigkeitsalphabet und R ein noethersches Ersetzungssystem, so daß M = M (?; D) dekomponierbar ist. Dann kann für eine Spur t 2 M jede Links-Derivation t ? =)R ^t in O(dR log dR) berechnet werden. Wie schon oben bemerkt läßt sich diese Version des Reduktionsalgorithmus so modifizieren, daß jede beliebige Faktorisierungssequenz frei gewählt werden kann. D.h. spezifiziert durch Zugriffspfade ist die freie Auswahl der Vorkommen und die Auswahlfreiheit bei den durch die Vorkommen induzierten Faktorisierungen in einer Derivation t = u1l1v1 =)R u1r1v1 = u2l2r2 =)R ? ? ? ? ? ? =)R un?1rn?1vn?1 = unlnvn =)R ^t; möglich. Theorem 16 Sei (?; D) ein Abhängigkeitsalphabet und R ein noethersches Ersetzungssystem so, daß M = M (?; D) dekomponierbar ist. Dann kann für eine Spur t 2 M jede irreduzible Form t ? =)R ^t in O(dR log dR) berechnet werden. 8.6 Ein Linearzeit-Reduktionsalgorithmus Nutzen wir die spezielle Struktur der Abhängigkeitsalphabete bzw. die der Spurdarstellungen, so kann eine irreduzible Form in linearer Zeit berechnet werden kann. Genauer kann eine Derivation t n =)R ^t 2 Irr(R) in O(n) Zeiteinheiten berechnet werden kann. Bei dem vorhergehenden Ansatz besaßen die Operationen SPLIT sowie CONCAT, right- QUOTIENT, leftQUOTIENT und FACTORIZE logarithmische Zeitkomplexität. Diese resultierte aus der Laufzeit von SPLIT, wegen der Verwaltung der Beschriftungen Ld in N?-Bäumen. Das war notwendig, da die Listen geordnet aufgeteilt werden mußten, um die Invariante " Resultate sind korrekt beschriftet\ aufrecht erhalten zu können. Die zeitintensive Operation ist also das Zerteilen der Spur bzw. das Aufrechterhalten der Beschriftungen. Dieses Problem umgehen wir, indem die Beschriftungen noch enger an die Term- bzw. Baumstruktur gekoppelt werden. Der modifizierte abstrakte Datentyp Wir entwickeln in diesem Abschnitt Datenstrukturen und Primitiven, um einen linearen Normalform-Algorithmus zu formulieren. Dazu modifizieren wir die Beschriftung leicht. 76 Wir nennen einen Spurterm t schwach beschriftet, wenn alle Subterme schwach beschriftet sind und, falls t selber ein ?-Term ist, t die Beschriftung L(t) trägt (siehe Abschnitt 8.2). Die fehlenden Beschriftungen können in konstanter Zeit dynamisch berechnet werden, wenn Prädikate der Form Ld(?(t1; : : : ; tn)) 6= ; in konstanter Zeit entschieden werden können. Lemma 36 Sei t = ?(t1; : : : ; tk) ein schwach beschrifteter ?-Term so, daß die Prädikate Ld(ti) 6= ; für alle i 2 [k] und alle d 2 Dec(R) in konstanter Zeit entschieden werden können. Dann kann die Beschriftung L(t) in konstanter Zeit berechnet werden. Beweis: Die Menge L(t) = fd 2 Dec(R) j h(d) = ?(d1; : : : ; dk); 8i 2 [k] : di 6= 1 ) Ldi 6= ;g enthält höchstens O(jDec(R)j) = O(1) viele Elemente, deren Darstellung die konstante Größe O(maxfjlj j l 2 LRg) = O(1) besitzt. Der Test Ldi 6= ; kann iteriert für alle i 2 [k] in konstanter Zeit durchgeführt werden. Als Datenstruktur verwenden wir für Terme wieder Bäume. Präziser verwenden wir Bäume mit drei Knotensorten: Mit ? oder ? assoziierte innere Knoten und mit Wörtern aus a?, a 2 ? assoziierte Blätter. Die ?-Knoten haben eine durch das entsprechende direkte Produkt bestimmte konstante Anzahl von Kindern, denn die bei dem Produkt involvierten Alphabete sind disjunkt. Damit ist die maximale Anzahl der Kinder (in diesem Fall j?j) unabhängig von der zu reduzierenden Spur. ?-Knoten können mehr als O(1) Kinder besitzen. Die Anzahl dieser Kinder ist nur linear in der Länge der zu reduzierenden Spur beschränkt. Die Bäume besitzen wie die Terme konstante Tiefe und die Deskriptionen haben konstante Größe. Die Elemente i 2 Ld(t) einer L-Beschriftung eines Spurterms t = ?(t1; : : : ; tn) stellen wir als Verweise auf den i-ten Subterm ti dar. In der folgenden Abbildung ist die Zeigerstruktur für einen ?-Knoten illustriert. Man beachte, daß die Ordnung in der Liste Ld, d 2 Dec(R) verloren gehen kann, und daß ein Subterm, der den Faktor d enthält, in O(1) Zeiteinheiten gefunden werden kann. ? n Ld 3 1 ... ... (n ? 2) t1 t2 tn?1 tn 77 Um Faktoren in der Spur darzustellen, haben wir schon in früheren Kapiteln Vorkommen- Morphismen und Positionen in Worttupeln kennengelernt. Der Positionsbegriff für diese Repräsentation orientiert sich (wie auch die Darstellung durch Terme) an der Dekomposition des Abhängigkeitsalphabetes. Sei (?; D) das Abhängigkeitsalphabet und Dec(?; D) = f(?i; Di) j i 2 [k]g die Dekomposition. Unter einem Vorkommenbaum für d 2 Dec(R) (bzgl. (?; D)) verstehen wir den den Term h(d) repräsentierenden Baum p. D.h. der den folgenden Bedingungen genügende Baum. (i) Gilt (?; D) = ?i2[k](?i; Di) und besitzt d die Form ?(d1; : : : ; dk), so besitzt p eine Wurzel mit k Söhnen, und der i-te Sohn ist die Wurzel eines Vorkommenbaums von di bzgl. (?i; Di) für alle i 2 [k]. (ii) Gilt (?; D) = ?i2[k](?i; Di) und besitzt d die Form ?(d1; : : : ; dm), so besitzt p eine Wurzel mit m konsekutiven Söhnen (in t), und der j-te Sohn ist die Wurzel eines Vorkommenbaums von dj bzgl. des entsprechenden Abhängigkeitsalphabetes für alle j 2 [m]. (iii) Ist (?; D) nuklear (atomar), so besteht p aus einem Knoten. Ein (Baum-)Vorkommen i : l ?! t von d in einem Spurterm repräsentierenden Baum t ist ein Vorkommenbaum d, der via Referenzen zu einem zu ihm isomorphen Unterbaum von t gebunden ist, so daß bei l = ?(l1; : : : ; lm) l1 linkspassend und lm rechtspassend ist, falls m > 1. Dieser Teilbaum repräsentiert den Faktor d. d t Ein rechtspassendes Vorkommen ist ein Suffixvorkommen. Entsprechend ist ein linkspassends Vorkommen ein Präfixvorkommen. Damit besitzt ein rechtspassendes Baumvorkommen j : d ?! t keinen unreferenzierten ?-Knoten als Bruder, der sich rechts von einem referenzierten Knoten befindet. Alle Teilbäume, die sich rechts von einem referenzierten ?-Knoten befinden, sind dann vollständig referenziert. Genauer ist das Vorkommen ?(d1; : : : ; dm) ?! ?(t1; : : : ; tn) rechtspassend, wenn d1 = t1; : : : ; tm?1 = dm?1 und dm ?! tm rekursiv rechtspassend ist. Das Vorkommen ?(d1; : : : ; dk) ?! ?(t1; : : : ; tk) ist rechtspassend, wenn alle Vorkommen di ?! ti, i 2 [k] rechtspassend sind. Analog dazu behandelt man linkspassende Baumvorkommen j : d ?! t. Anders formuliert sei i : l ?! t ein Faktorvorkommen, dann korrespondieren die Blättern in diesem Teilbaum mit den Elementen aus i(l). Die Knoten von einem Vorkommen i : d ?! t sind mit entsprechenden L-Beschriftungen assoziiert. Genauer gilt 78 für d = ?(d1; : : : ; dk), daß ein Verweis auf i(dj) in Ldj (tj) mit t = ?(t1; : : : ; tk) existiert. Für einen ?-Term d = ?(d1; : : : ; dm) findet sich der Verweis auf die Wurzel von i(d) in Ld(t) wieder. Ist also ein Spurterm schwach beschriftet, dann läßt sich in konstanter Zeit ein Vorkommen von d 2 Dec(R) identifizieren. Lemma 37 Sei t ein schwach beschrifteter Spurterm in der oben beschriebenen Repräsentation. Dann kann ein Baumvorkommen i : d ?! t in konstanter Zeit ermittelt werden. Beweis: Gilt t 2 a? (der atomare Fall), so ist die Aussage trivial. Falls t = ?(t1; : : : ; tk) ein ?-Term ist mit d = ?(d1; : : : ; dk) 2 L(t), so besitzt t den Faktor d. Man beachte, daß unter Verwendung der Aussage aus dem vorhergehenden Lemma dieses Prädikat in konstanter Zeit entschieden werden kann. Dann besitzen die Terme ti die Faktoren di und es können in konstanter Zeit die Vorkommenbäume für di ?! ti berechnet werden. Diese lassen sich zu einem Vorkommenbaum in konstanter Zeit kombinieren, siehe Lemma 24. Falls t = ?(t1; : : : ; tn) ein ?-Term mit Ld(t) 6= ; ist, so enthält t den Faktor d. Wir unterscheiden die zwei Fälle d = ?(d1) und ?(d1; : : : ; dm) mit m > 1. Sei i 2 Ld(t) ein Verweis auf den Term ti. Im ersten Fall erzeugen wir eine Wurzel mit der entsprechenden Referenzierung, an der wir ein Vorkommenbaum von d ?! ti anhängen. Dieser läßt sich rekursiv mit konstantem Aufwand berechnen. Im zweiten Fall berechnen wir den Teilbaum von ti, der das Suffix d1 repräsentiert. Dieses muß existieren, da i 2 Ld(t). Das ist mit der Methode, die im Beweis von Lemma 25 beschrieben wird, in konstanter Zeit möglich. Analog identifizieren wir den Teilbaum, der zu dem Präfix dm in ti+m?1 korrespondiert. Damit erhalten wir den rechtspassenden und den linkspassenden Vorkommenteilbaum. Der Vorkommenteilbaum setzt sich dann aus einer Wurzel und den Bäumen, die den Termen tj für i < j < i+m?1 entsprechen, sowie dem rechts- und dem linkspassenden Vorkommenteilbaum, zusammen, siehe Lemma 24. Von den so ermittelten m konsekutiven Bäume werden Kopien erzeugt, die ihre Originale (knotenweise) referenzieren. Die Kopien werden ihrem Index nach geordnet unter die auf den Vater von tj verweisende Wurzel gehängt. Alle diese Operationen erfordern konstante Zeit, da Zeigerstrukturen zwischen Beschriftungen und Baumteilen die entsprechenden Zugriffe ermöglichen. Die berechnete Struktur besitzt ebenfalls konstante Größe. Die Anzahl der Invokationen ist durch j?j beschränkt. Beispiel 7 Sei (?; D) = a ? (b ? (c ? d)) = [a c ? b ? d]. und t = ?(a3; ?(b2; ?(c3; d2); b3; ?(c2; d4))): Weiter sei l = [abcd] eine linke Seite. Damit ist Dec(l) = fa; b; c; d; cd; bcd; abcdg: Wir erhalten den repräsentierenden Baum 79 d4 b3 b2 a3 ? ? ? ? c3 d2 c2 2 4 1 3 Lc Lbcd Es sind nicht alle Beschriftungen dargestellt. Der mit punktierten Linien markierte Teilbaum ist ein nicht linkspassendes Vorkommen von l. Man beachte das zweite b. Der mit gestrichelten Linien markierte Baum ist kein Vorkommen. Da wir nicht mit Konkatenations- bzw. Faktorisierungsoperationen arbeiten, benötigen wir einen Mechanismus, um die Datenstruktur (lokal) zu modifizieren. Hierzu führen wir ein Positionskonzept ein. Eine Position p in einer Baumrepräsentation t ist eine Baumstruktur, die eine Faktorisierung u ffi v beschreibt. Genauer ist eine Position ein Unterbaum in t mit folgenden Eigenschaften: (i) Gilt t = ?(t1; : : : ; tk), so ist die Wurzel von t die Wurzel von p, und p besitzt k Kinder, wobei für alle i 2 [k] das i-te Kind die Wurzel einer Position in ti ist. (ii) Gilt t = ?(t1; : : : ; tn), so besteht p aus einem Knoten, der die Wurzel eines Teilbaums ti, i 2 [n] referenziert, oder p ist eine Position in ti. (iii) Ist t nuklear (atomar), so ist p ein Blatt, das mit einer Faktorisierung u ? v von t beschriftet ist. Jede Position beschreibt eine Faktorisierung eindeutig. Präziser, jedes einen ?-Term ?(t1; : : : ; tn) referenzierende Blatt, das den Subterm ti, i 2 [n] referenziert, beschreibt die Faktorisierung ?(t1; : : : ; ti) ffi ?(ti+1; : : : ; tn). Jeder ?-Knoten beschreibt die Faktorisierung durch die Faktorisierungen der einzelnen Komponenten. Bei Cographen-Monoiden sind die Positionen in Atomen an Faktorisierungen ai ? bj mit i + j = n. Diese lassen sich einfach durch Stringpositionen repräsentieren. Die primitiven Operationen Bis jetzt haben wir die statische Termstruktur mit der Beschriftung betrachtet. In diesem Abschnitt beschreiben wir, wie diese Strukturen erzeugt und modifiziert werden können. Dazu führen wir die zwei Basisoperationen INSERT und DELETE mit der folgenden Semantik ein. Sei p eine Position in t, a 2 ? ein Buchstabe und t die zu modifizierende Datenstruktur. 80 (i) Dann berechnet INSERT(a; t; p) eine schwach beschriftete Struktur t0, in der nach der durch p beschriebenen Position ein a eingefügt wird. Genauer, wenn in der Position p ein Pfad zu einem Blatt an in t existiert, so wird dieses Blatt zu an+1 durch Anfügen eines Symbols a geändert, und die Beschriftungen sowie die Position werden entsprechend aktualisiert. Ist kein Blatt mit dieser Beschriftung vorhanden, so beschreibt die Position eineindeutig, an welche Stelle das a eingefügt werden muß. Ist ein neues Blatt generiert worden, so wird die Position entsprechend angepaßt, daß sie dieses neue Blatt auch referenziert. (ii) Dual berechnet DELETE(a; t; p) eine schwach beschriftete Struktur t0, in der an der durch p beschriebenen Position das Blatt an durch an?1 ersetzt wurde. Genauer existiert in p ein Pfad zu einem Blatt an in t. Dieses Blatt wird auf an?1 durch Entfernen eines as geändert, und die Beschriftungen werden entsprechend der Definition aktualisiert. Wir fordern, daß p ein Blatt an mit n > 0 referenziert. Muß ein Blatt entfernt werden, d.h. n = 1, so wird die Position entsprechend angepaßt. INSERT Wir beschreiben die Operation INSERT in der gewohnten Notation. Der Algorithmus geht wie folgt vor: Zuerst wird die Stelle über die Position identifiziert, an der das a eingefügt werden soll. Falls die Position nicht direkt auf ein Blatt verweist, so wird ein entsprechender Teilbaum erzeugt. Leere Teilbäume repräsentieren das neutrale Element im entsprechenden Submonoid. Ist das a eingebaut, so werden die Beschriftungen bottom-up korrigiert. PROCEDURE FIND(a; t; p) Comment Input: weakly labeled trace representation, a letter a and a position p. Output: an a?-labeled leaf in t and a position. Method let v be the root of p. if v has a child and the alphabet corresponding to this child contains the letter a then let v0 be this child let t0 the v0-referenced subtree of t hp0; li FIND(a; t0; p0) replace the v0-rooted subtree of p by p0 return(p; l) else if t = ?(t1; : : : ; tn) then let ti be the p-referenced subterm if the alphabet corresponding to ti+1, i < n contains a then create position v0 referencing on ti+1 hp0; li FIND(a; ti+1; v0) replace child of v by the tree p0 else create a new tree t0 i between ti and ti+1 81 create position v0 referencing on t0 i hp00; li FIND(a; t0; v0) let p be the position with root v0 where the root of p00 is the child of v0 end if return (hp; li) else if t = ?(t1; : : : ; tk) then let v0 be the child of v where the alphabet contains a let ti be the v0 referenced subtree of t let p00 be v0-rooted subtree of p hp0; li FIND(a; ti; p00) replace the subtree p00 by p0 in p return (hp; li) otherwise if there is no a? labeled leaf then create the leaf l labeled by a0 and let p be the position of this leaf else let l be this leaf end if return (hp; li) end if end Method Beim Abstieg in dem Positionsbaum wird man durch das vom Subterm induzierte Abhängigkeitsalphabet geführt. Dabei verstehen wir hier unter dem von einem Term h(t) induzierten Alphabet das Indexalphabet (?; D) des Homomorphismus h = h(?;D). Wenn eine Position einen Subterm ti in einem ?-Term t = ?(t1; : : : ; tn) referenziert und das von ti induzierte Alphabet den Buchstaben a enthält, so findet man das gesuchte Blatt in ti. Enthält das induzierte Alphabet den Buchstaben nicht, aber das von ti+1 induzierte Alphabet, so findet man das Blatt in ti+1. Ansonsten muß ein neuer Subterm bzw. Unterbaum t0 i nach ti und, falls ti+1 existiert, vor ti+1 eingebaut werden. Das Resultat ist dann ein ?-Term ?(t1; : : : ; ti; t0 i; ti+1; : : : ; tn) und die Position muß so verändert werden, daß sie t0 i referenziert. Die Erweiterung der Position um die Referenzen auf t0 i können rekursiv erfolgen. Referenziert die Position einen ?-Term ?(t1; : : : ; tk), so existiert ein Subterm ti, dessen induziertes Alphabet den Buchstaben a enthält. Dieser kann rekursiv nach dem Blatt durchsucht werden. Damit sind wir in der Lage, die Primitive INSERT zu formulieren. PROCEDURE INSERT(a; t; p) Comment Input: weakly labeled trace representation t, a letter a, and a position p. Output: trace weakly labeled representation where the a is inserted at position p and a modified position. 82 Method hp; vi FIND(a; t; p) replace the label an of leaf v by an+1 while v is not the root of t do v0 v v father of v0 if v is corresponding to a ?-term t0 = ?(t1; : : : ; ti; : : : ; tn) then let ti corresponding to v0 for all d 2 Dec(R) where h(d) = ?(d1; : : : ; dm) for the recursion of h corresponding to t0 do if m = 1 then reconstruct L(ti) with Lemma 36 if d 2 L(ti) then create a reference to ti in Ld(t0) if there is none else delete the reference to ti in Ld(t0) if there is one end if else (when m > 1) for all 1 <= j <= m do if d1 2 Suff(t1 ? : : : ? ti?j) and d2 ? : : : ? dm 2 Pref(ti?j+1 ? : : : ? tn) then create a reference to ti?j in Ld(t0) if there is none else delete the reference to ti?j in Ld(t0) if there is one end if end for end if end for end if end while return (ht; pi) end Method Die Beschriftungsinformation wird hier für alle Baumknoten, die sich in der " Nähe\ eines Pfadknoten befinden, aktualisiert. " Nähe\ bedeutet hier in einer Umgebung der Distanz m = O(1), wobei die Distanz die Entfernung von zwei Geschwistern in der repräsentierenden Baumstruktur ist. Wir stellen einen inneren Knoten durch eine geordnete doppelt verkettete Liste wie in der Zeichnung dar. D.h. die Distanz zwischen zwei Geschwistern ist die Länge der sie verbindenden Liste. Damit können in dieser Struktur quasi benachbarte Knoten im Redukt des Abhängigkeitsgraphen in der in Kapitel 5 erwähnten Metrik sehr weit voneinander entfernt sein, 83 ohne daß die Struktur quadratischen Platz benötigt. Wir können das folgende Resultat zeigen. Lemma 38 Sei t eine Spurrepräsentation mit einer Position p, die die Faktorisierung uv repräsentiert. Dann berechnet INSERT(a; t; p) eine schwach beschriftete Spurrepräsentation von uav = t0. Die modifizierte Position repräsentiert danach die Faktorisierung u0v mit u0 = ua. Beweis: Die Stelle, an der das a eingefügt werden soll, wird top-down mit FIND berechnet. Verweist die Position auf ein mit an beschriftetes Blatt in t, so wird diese Blatt in FIND durch Absteigen gefunden. Jedem Term in t 2 h(M ) in t kann eineindeutig das Abhängigkeitsalphabet (?; D) zugeordnet werden, das der Rekursionsinvokation des Homomorphismus h = h(?;D) entspricht. Damit ist auch mit jedem inneren Knoten v das vom Term, der durch den Teilbaum mit Wurzel v repräsentiert wird, induzierte Alphabet assoziiert. Existiert kein Pfad in der Position, der an einem a?-beschrifteten Blatt endet, so wird für die Kette von Abhängigkeitsalphabeten in Dec?(?; D), die bei (?; D) beginnt und zu (fag; f(a; a)g) absteigt, ein Pfad in t zu einem mit a0 beschrifteten Blatt kreiert. Dabei wird gleichzeitig der Termbaum und die Position entsprechend erweitert. Danach wird dem Blatt ein a angefügt. An dieser Stelle im Algorithmus repräsentiert der Baum t = uv die Spur, an der durch die Position p beschriebene Stelle, ein Blatt eingefügt wurde. Damit repräsentiert der Resultatterm uav. Nur die Beschriftung ist jetzt noch inkonsistent. In der while-Schleife in dem Algorithmus wird die L-Beschriftung wieder hergestellt. Wir zeigen dazu die folgende Invariante: Der dem Subterm t0 entsprechende Teilbaum, also der Teilbaum mit der Wurzel v, ist schwach beschriftet. Beim Betreten der Schleife ist die Invariante erfüllt, v ist dann ein Blatt, und Blätter sind nicht beschriftet. Ist t0 ein ?-Term, so ist t0 bereits schwach beschriftet. Wenn t0 = ?(t1; : : : ; tn), also t0 ein ?-Term ist, dann bleiben alle Beschriftungen Ld(t0) \ [i ?m] und Ld(t0) \ fj 2 [n] j j > ig erhalten, wobei ti der Subterm ist, in dem das a eingefügt wurde und m die Arität von d = ?(d1; : : : ; dm), dem betrachteten Element d 2 Dec(R), ist. Diese Subterme bzw. die korrespondierenden Bäume tk, k 2 [n] sind alle schwach beschriftet. Für die Stellen (i ? m); : : : ; i werden die Ld-Beschriftungsinformationen entsprechend der Definition von Ld für alle d 2 Dec(R), die vorkommen können, neu berechnet. Damit ist der ganze Term t0 schwach beschriftet. Beim Verlassen der while-Schleife ist v der Wurzelknoten. Damit ist der gesamte Baum, d.h. das Resultat, schwach beschriftet. Die verwendete Datenstruktur ermöglicht dies sogar in O(1) Zeiteinheiten, denn alle involvierten Prädikate lassen sich in O(1) Zeiteinheiten entscheiden und die Anzahl der Iterationen bzw. Inkarnationen ist durch O(j?j ? jDec(R)j ? maxfjlj j l 2 LRg) = O(1) beschränkt. 84 DELETE Analog formulieren wir die Operation DELETE. Hier verlangen wir jedoch, daß die Position einen Pfad besitzt, der in einem Blatt endet, das auf an in t verweist. PROCEDURE DELETE(a; t; p) Comment Input: weakly labeled trace representation, a letter a, and a position p. Output: weakly labeled trace representation where the a is deleted at position p and a modified position. Method decent the path in t (given by p) ending at an a?-labeled leaf replace the leaf an+1 by an let v be this leaf if n = 0 then while v is not the root of t and v has no child do v0 father of v purge v in t and the corresponding references in i v v0 end while restore the reference in i end if while v is not the root of t do v0 v v father of v0 if v is corresponding to a ?-term t0 = ?(t1; : : : ; ti; : : : ; tn) then let v0 corresponding to ti for all d 2 Dec(R) where h(d) = ?(d1; : : : ; dm) for the recursion of h corresponding to t0 do if m = 1 then reconstruct L(ti) with Lemma 36 if d 2 L(ti) then create a reference to ti in Ld(t0) if there is none else delete the reference to ti in Ld(t0) if there is one end if else (when m > 1) for all 1 <= j <= m do if d1 2 Suff(t1 ? : : : ? ti?j) and d2 ? : : : ? dm 2 Pref(ti?j+1 ? : : : ? tn) then create a reference to ti?j in Ld(t0) if there is none else delete the reference to ti?j in Ld(t0) if there is one 85 end if end for end if end for end if end while return (ht; pi) end Method Wir entfernen ein a aus t an der Position analog wie wir ein Blatt einfügen. Lediglich die Fortsetzung des Zugriffspfades muß durch eine Verkürzung dieses Pfades ersetzt werden, wenn Knoten aus t entfernt werden müssen. Lemma 39 Sei t eine Spurrepräsentation mit einer Position p, die auf ein mit an beschriftetes Blatt verweist und damit eine Faktorisierung uav darstellt. Dann berechnet DELETE(a; t; p) eine Spurrepräsentation t0 = uv, in der das a entfernt wurde. p wird entsprechend modifiziert, so daß die Position danach die Faktorisierung uv darstellt. Das Resultat t0 ist schwach beschriftet. Auch diese Methode besitzt eine konstante Zeitkomplexität. Fassen wir diese Teilresultate zusammen, so erhalten wir das folgende Theorem. Theorem 17 Sei (?; D) ein Cographen-Abhängigkeitsalphabet und R ein noethersches Ersetzungssystem über M = M (?; D). Dann existiert ein Algorithmus, der für eine Spur t 2 M eine Normalform ^t 2 Irr(R), t ? =)R ^t, in O(dR) Zeiteinheiten berechnet. Beweis: Wir haben bereits gezeigt, wie ein Faktorvorkommen in konstanter Zeit berechnet werden kann und wie einzelne Buchstaben aus der darstellenden Struktur entfernt bzw. eingefügt werden können. Es reicht also aus einen Algorithmus zu beschreiben, der in konstanter Zeit eine bereits durch einen Vorkommenbaum identifizierte linke Seite einer Regel l ! r 2 R durch die rechte Seite r ersetzt. Dabei gehen wir wie folgt vor. Zuerst entfernen wir buchstabenweise alle Teile der linken Seite, auf die der Vorkommenbaum verweist. Die zuletzt berechnete Position nutzen wir, um an dieser Stelle die rechte Seite einzufügen. Dieses Vorgehen wird so lange iteriert bis der Resultatterm bzw. Resulatbaum irreduzibel ist. Wir deklarieren die Operation REPLACE, die das Gewünschte leistet. FUNCTION REPLACE(i; l; r; t) Comment Input: a trace representation t = ulv, a tree occurrence i of l in t, and a right-hand side with l ! r 2 R, Output: the representation of a trace urv according to the semantic. 86 Method let p be the position of the minimal letters of the occurrence uniquely extended by minimal letters of t while l 6= 1 do let a be a minimal letter in l = al0 if there is no path in p ending in an a?-labeled vertex then extend the position to one pointing on such a leaf end if ht; pi DELETE(a; t; p) l l0 end while let r0 be a copy of r while r0 6= 1 do let a be a minimal letter in r0 = ar00 ht; pi INSERT(a; t; p) r0 r00 end while return (t) end Method Die Invarianten der Schleifen sind offensichtlich. Bei der ersten while-Schleife kann die die Position p nur auf minimale Buchstaben von l oder minimale Buchstaben von v mit t = ulv verweisen. Es werden nur Buchstaben entfernt, auf die i verweist. Es gilt damit t = u ? l0 ? v wenn t = u ? l ? v die Eingabe war und i das Vorkommen ist, das diese Faktorisierung induziert. Nach Verlassen der while-Schleife ist die Repräsentation von uv berechnet, und die Position stellt diese Faktorisierung dar. Die zweite while-Schleife besitzt die Invariante t = u ? r000 ? v, wobei r000 der Quotient r0?1r ist. Damit kann in konstanter Zeit ein Derivationsschritt nachvollzogen werden. Wir erhalten die Aussage. Korollar 13 Sei (?; D) ein Cographen-Abhängigkeitsalphabet und R ein gewichtsreduzierendes Ersetzungssystem über einem Cographen-Monoid M = M (?; D). Dann kann für eine Spur t 2 M eine Normalform ^t 2 Irr(R) in O(jtj) berechnet werden. Bemerkung 8 Mit dieser Version des Reduktionsalgorithmus kann nicht mehr jede Faktorisierung gewählt werden. (Es ist kein Zugriff mehr auf ein beliebiges Listenelement vorhanden.) Auch läßt sich keine Information über die Position der ersetzten Faktorvorkommen relativ zueinander ohne linearen Suchaufwand ermitteln. So kann man beispielsweise nicht zusichern, eine Links-Derivation t = u1l1v1 =)R u1r1v1 = u2l2r2 =)R ? ? ? ? ? ? =)R un?1rn?1vn?1 = unlnvn =)R ^t; mit ^t 2 Irr(R) und ui 2 Irr(R) für alle i 2 [n] zu berechnen. 87 Wir haben uns in der Darstellung auf Cographen-Monoide eingeschränkt. Aber auch hier ist die Verallgemeinerung auf dekomponierbare Monoide möglich. Das führt zur folgenden Verallgemeinerung von Books Resultat. Theorem 18 Sei (?; D) ein Abhängigkeitsalphabet und R ein noethersches Ersetzungssystem über M = M (?; D) so, daß M dekomponierbar ist. Dann existiert ein Algorithmus, der für eine Spur t 2 M eine Normalform ^t 2 Irr(R), t ? =)R ^t, in O(dR) Zeiteinheiten berechnet. 88 9 Ausblick Wir haben eine Vielzahl von Reduktionsalgorithmen für Spurersetzungssysteme vorgestellt. Darunter waren sogar einige linear | also optimal. Die auf den C?-Bäumen basierenden Algorithmen besitzen die etwas schlechtere Zeitkomplexität " O(dR log dR)\. Sie sind jedoch wesentlich effizienter als die auf endlichen Automaten basierenden quadratischen Methoden. Man kann sich diese Effizienzsteigerung am Beispiel " Sortieren durch Vergleichen\ veranschaulichen. Die Verbesserung der Zeitschranke entspricht der Effizienzsteigerung beim Ersetzten von Insertionsort durch beispielsweise Heapsort. Die linearen Reduktionsalgorithmen können beide als eine Verallgemeinerung des Reduktionsalgorithmus von Book betrachtet werden. Offen bleibt die Existenz von effizienteren bzw. allgemeineren Methoden. In den hier betrachteten Klassen basierte die Lösung auf einer adäquaten Repräsentation von Spuren. Eine Algorithmus, der den allgemeinen unzusammenhängenden Fall auch abdeckt könnte beispielsweise auf Darstellungen, wie sie im Anhang beschrieben sind, aufbauen. Die Kardinalitätsresultate und die Intervallbeschreibungen sind ein Indiz für subquadratische Algorithmen. Eine Verallgemeinerung des Reduktionsalgorithmus aus Kapitel 5 könnte auf Bäumen mit verteilten Intervallbeschriftungen, die zur Intervallrelation I korrespondieren, basieren. Vermutlich lassen sich diese Bäume so verwalten, daß die Kombinationsrelation r dynamisch rekonstruierbar bleibt (vermutliche Komplexität O(dR ? log dR ? log log dR)). Eine auch für die Applikationen nicht zu vernachlässigende Fragestellung ist: Welche konstanten Faktoren verbirgt die O-Notation oder inwieweit sind die angegebenen Resultate für Applikationen, wie sie in der Einführung beschrieben sind, aussagekräftig? Inwieweit sich die vorgestellten Algorithmen in den angedeuteten Bereichen realisieren lassen wird sich zeigen. Wir schließen mit dem letzten offenen Problem in diesem Kontext, der zentralen Frage nach der Komplexität: Welche uniforme und nicht-uniforme Zeitkomplexität besitzt das Normalformenproblem für Spurmonoide? 89 A Anhang: Faktoren und Faktorisierungen In diesem Kapitel sind die Definitionen und Resultate über Faktorisierungen zusammengefaßt. Viele der Sätze wurden bei der Konstruktion der Algorithmen implizit verwendet. Im Abschnitt über allgemeine Faktoren werden Methoden bereitgestellt, die eventuell zu einem effizienten Algorithmus führen, der das allgemeine Normalformenproblem löst. A.1 Darstellungen von Faktorisierungen Ein Faktor einer Spur t 2 M (?; D) ist eine Spur l 2 M (?; D), für die zwei Spuren u und v mit t = u ? l ? v existieren. Unter einer Faktorisierung von t verstehen wir das Tripel (u; l; v) 2 M (?; D) ? M (?; D) ? M (?; D) mit u ? l ? v = t. Wir bezeichnen den Faktor einer Spur t 2 M (?; D), der aus allen minimalen Buchstaben besteht, mit min(t) und der, der aus allen maximalen besteht, mit max(t). Aus der Darstellung von Spuren als partielle Ordnungen erhalten wir eine Charakterisierung von Faktoren. Lemma 40 Seien t; l 2O(?;D) Spuren mit t = hMt; <=ti und l = hMl; <=li. Weiter sei Ml ? Mt eine Teilmultimenge und <=l die auf Ml induzierte partielle Ordnung <=t \ (Ml? Ml). Dann ist l ein Faktor in t (t = ulv für u; v 2 M (?; D)) genau dann, wenn für alle Elemente a; b 2 Ml und c 2 Mt gilt a <=t c <=t b =) c 2 Ml. Beweis: Sei l ein Faktor in t = ulv 2 O(?; D) mit Spuren u = hMu; <=ui, v = hMv; <=vi und t = hMt; <=ti. Daraus folgt Mt = Mu _[Mv _[Ml. Seien a; b 2 Ml und c 2 Mt mit a <=t c <=t b. Dann gilt a <=t c =) c = 2 Mu und c <=t b =) c = 2 Mv. Also liegt c in Ml. Sei nun l = hMl; <=li eine durch <=t partiell geordnete Teilmenge von t so, daß für alle a; b 2 Ml a <=l c <=l b =) c 2 Ml gilt. Liegen alle minimalen und maximalen Elemente von t in Ml, so ist t = l ein Faktor (u = v = 1). Anderenfalls existiert ein minimaler (oder ein maximaler) Buchstabe a in t, der nicht in l vorkommt. Damit faktorisiert sich t = at0 (oder t = t0a) und t0 enthält (mit Induktion über die Kardinalität von Mt) den Faktor l. Das heißt t = au0lv0 (oder t = u0lv0a). Man beachte die Divisionsrelation ist noethersch. Sei t = hM; <=ti eine partiell geordnete Multimenge. Dann verstehen wir unter dem durch N ? M induzierten Ideal IN(t) die Spur i = hMi; <=ii mit Mi = fa 2 M j 9b 2 N : a <=t bg und <=i = <=t \ (Mi ?Mi). Dual definieren wir den von N induzierten Filter FN (t) als die Spur f = hMf ; <=fi mit Mf = fa 2 M j 9b 2 N : b <=t ag und <=f = <=t \ (Mf ?Mf ). Die Menge der Ideale einer Spur t zusammen mit den Verknüpfungen IN(t) u IN 0 (t) = IN\N 0 (t) und IN(t)tIN 0 (t) = IN(t)[IN 0 (t) bilden einen endlichen Verband. Dual bilden 90 die Filter einer Spur t zusammen mit den Verknüpfungen FN(t)tFN 0 (t) = IN[N 0 (t) und FN (t) u FN 0 (t) = FN (t) \ FN 0 (t) einen Verband9. Die Charakterisierung in Lemma 40 führt zu einer durch einen Faktor l induzierten Aufteilung. Sei l = hMl; <=li eine Subspur von t = hMt; <=ti 2 O(?; D), d.h. Ml ? Mt und <=l=<=t \ (Ml ?Ml). Dann definieren wir pret(l) = ta2MlIa(t) n l Pret(l) = ta2MlIa(t) postt(l) = ta2MlFa(t) n l Postt(l) = ta2MlFa(t) indt(l) = hMi; <=ii; wobei die letzte Spur der verbleibenden Teil ((pret(l))?1t(postt(l))?1)l?1 von t ist. In der Terminologie der Ideale und Filter läßt sich das vorhergehende Lemma wie folgt formulieren. Korollar 14 Seien t; l 2 O(?; D) Spuren mit t = hMt; <=ti und hMl; <=li. Weiter sei Ml ? Mt eine Teilmultimenge und <=l die auf Ml induzierte partielle Ordnung <=t \ (Ml?Ml). Dann ist l ein Faktor in t (t = ulv für u; v 2 M (?; D)) genau dann, wenn Pret(l) \ Postt(l) = l bzw. pre(l) \ post(l) = ;. Die Definition von pret(l), postt(l) und indt(l) ist in der folgenden Graphik illustriert. = l l pret(l) indt(l) indt(l) postt(l) Pret(l) Postt(l) t = Jede Faktorisierung (u; l; v) induziert eine Faktorisierung in M ((?; D)(l)) via Projektionen (ß?(l)(u); l; ß?(l)(v)). Diese Faktorisierungen von ß?(l)(t) nennen wir Vorkommen von l in t. Jedes durch Faktorisierungen induzierte Vorkommen entspricht einer Vielfalt von Zerlegungen in die Faktoren pret(l), postt(l), u0, v0 und l mit u0v0 = indt(l). Lemma 41 Für jede Faktorisierung (u; l; v) von t existieren Spuren u0 und v0 mit indt(l) = u0v0, u = pret(l)u0 und v = v0postt(l). Existiert umgekehrt eine Subspur l = hMl; <=t \ (Ml ? Ml)i mit indt(l) = u0v0 und u = pret(l)u0, v = v0postt(l), dann ist (u; l; v) eine Faktorisierung. Beweis: Aus t = ulv folgt pret(l) \ postt(l) = ;. Wir erhalten den Quotienten w = (pret(l))?1t(postt(l))?1 durch induktives Kürzen. Da l ein Faktor ist, gilt w = u0lv0. Insbesondere folgt aus (u0 [ v0) \ (pret(l) [ postt(l)) = ; die Unabhängigkeit von u0v0 und l, d.h. (?(u0) [ ?(v0)) ? ?(l) ? I. Die andere Implikation ist evident. 9Diese Eigenschaft ist eine direkte Folgerung aus dem Lemma von Levi. 91 Im folgenden sei M = M (?; D) das frei partiell kommutative von (?; D) erzeugte Monoid. Weiter bezeichne C eine Cliquenüberdeckung des erzeugenden Alphabets. Aus der Einbettung von M (?; D) in das direkte Produkt (freier Monoide) Q C2C C? erhalten wir Lemma 42 Sei (tC)C2C ein Worttupel in Q C2C C?. Dann existiert eine Spur t mit (tC)C2C = ß(t) genau dann, wenn für alle Cliquen C; C 0 2 C die Bedingung ßC(tC0) = ßC0(tC) erfüllt ist. Für eine Clique C 2 C und eine Spur t 2 M verwenden wir für die Projektion ßC(t) 2 C? auf das Cliquenalphabet C 2 C die Bezeichnung tC . Beweis: Da ß?, ? ? ?, ein Homomorphismus ist und ß? ffi ß? = ß?\? folgt aus (ßC(t))C2C = (tC)C2C = ß(t) für alle C; C 0 2 C die Gleichheit ßC(ßC0(t)) = ßC(tC0) = ßC0(tC) = ßC0(ßC(t)). Sei die Bedingung ßC(tC0) = ßC0(tC) für alle Cliquen C; C 0 2 C erfüllt. Gilt tC = 1 für alle C 2 C, so ist t = 1. Anderenfalls existiert eine Clique C 2 C mit tC = at0 C . Aus der Bedingung folgt, daß für alle Wörter tC0 mit a 2 C 0 2 C gilt tC0 = at0 C0 . Damit ist (tC)C2C = ß(a) ? (t0 C)C2C und a ein minimaler Buchstabe von t. Mit Induktion existiert eine Spur t0 mit ß(t0) = (t0 C)C2C und t = at0. Als Korollar erhalten wir eine weitere Charakterisierung von Faktoren. Korollar 15 Seien t; l 2 M (?; D). Dann ist l = hMl; <=li ein Faktor in t = hMt; <=ti genau dann, wenn (i) l ein Vorkommen in t ist, d.h. für alle Cliquen C 2 C mit C \ ?(l) 6= ; Wörter uC ; vC 2 C? existieren, mit tC = uC lCvC und für alle C; C 0 2 C mit C 0 \ ?(l) 6= ; und C \ ?(l) 6= ; ßC0(uC) = ßC(uC0) gilt, sowie (ii) für alle verbleibenden Cliquen C 2 C, C \ ?(l) = ; Faktorisierungen tC = uCvC existieren, so daß für alle C; C 0 2 C die Beziehung ßC(uC0) = ßC0(uC) erfüllt ist. Als Konsequenz ergibt sich aus (i) und (ii) ßC(vC0) = ßC0(vC) für alle C; C 0 2 C. Wir erhalten eine Faktorisierung ? ß?1((uC)C2C); l; ß?1((vC)C2C) ? : Bemerkung 9 Die Bedingung ßC(tC0) = ßC0(tC) für alle C 2 C ist äquivalent zu jtC ja = jtC0 ja für alle a 2 C \ C 0 und für alle C; C 0 2 C in diesem Kontext. A.2 Ordnungen für Vorkommen Betrachten wir ein Vorkommen (u; l; v), ß?(l)(t) = ulv, (von l in t) nicht mehr als ein Tupel, sondern als einen Vorkommen-Morphismus i : l ?! t zwischen zwei Spuren. 92 Dabei soll ein Vorkommen-Morphismus i : l = (lC)C2C ?! t = (tC)C2C ein Tupel von Wort-Morphismen (iC : lC ?! tC)C2C sein. Ein Wort-Morphismus j : v ?! w = xvy ist eine die Ordnung von v und die Nachbarschaft10 auf den Projektionen ß?(l)(tC) erhaltende Injektion, die jedem Buchstaben a in v einen Buchstaben a in w zuordnet. Sei v = v1 : : : vm, w = w1 : : : wn mit v1; : : : ; vm; w1; : : : ; wn 2 ? und j(v1) = wk+1, : : : , j(vm) = wk+m, dann sind die Wörter j(v) = j(v1) : : : j(vm) und v = v1 : : : vm (als Elemente des freien Monoids ??) identisch. Wir verwenden dieses Konzept, lediglich um verschiedene Vorkommen der gleichen Spur formalisieren zu können. v1 ? ? ? vm # ### # i(v1) ? ? ? i(vm) w1 ? ? ? wk+1 ? ? ? wk+m ? ? ? wn Da diese Morphismen Teilwörter identifizieren und somit nichts anderes als Positionsbeziehungsweise Längenangaben sind, verwenden wir als Namen Indizierungsbezeichner i und j. Ein Vorkommen-Morphismus ist also eine spezielle Inklusion einer Subspur. Ein Vorkommen i : l ?! t ist ein Faktorvorkommen, falls i = (iC)C2C ein Vorkommen ist, das eine Faktorisierung induziert. D.h. für alle C 2 C hat tC die Form uC iC(l) vC und es existieren Spuren u und v mit ß(u) = (uC)C2C und ß(v) = (vC)C2C. Ein Faktorvorkommen i : l ?! t legt somit die Ideale pre(i) = pret(i(l)) und Pre(i) = Pret(i(l)) und die Filter post(i) = postt(i(l)) und Post(i) = Postt(i(l)) eineindeutig fest. Bemerkung 10 In dieser Darstellung wird auch deutlich, daß Vorkommen (sowie Faktorvorkommen) zusammen mit den Spuren (als Objekte) eine Kategorie (Subkategorie) bilden. Dieser Fakt kann dazu verwendet werden, effizienten Faktorisierungsalgorithmen oder Algorithmen, die maximale Überlappungen bzw. kritische Paare berechnen, zu entwerfen. Seien i : li ?! t und j : lj ?! t zwei Faktorvorkommen. Wir definieren die Faktorordnung ? via i ? j :() Post(j) ? Post(i): Analog kann man eine Ordnung mit dem dualen Operator Pre definieren. j(l) i(l) Post(i) = t Post(j) 10Der Begriff Nachbarschaft setzt eine Topologie auf Worten voraus | die erzeugenden offenen Überdeckungen sind die Infixe. Wir verwenden diesen Begriff, um die kategorielle Struktur des Mustererkennungsproblems (Faktorisierungsproblems) zu unterstreichen. (Die Faktoren als Objekte mit der Faktorrelation als Morphismus ist wieder eine Kategorie.) 93 Offensichtlich ist ? nicht notwendigerweise eine lineare Ordnung. Lemma 43 Seien l; t 2 M (?; D) zwei Spuren, dann ist die Relation ? eine Ordnung auf der Menge der Faktorvorkommen i : l ?! t. Beweis: Offensichtlich ist ? reflexiv. Die Relation ? ist transitiv, da aus i ? j und j ? k folgt Post(k) ? Post(j) ? Post(i) und somit i ? k. Seien i ? j und j ? i, dann gilt u = Post(i) = Post(j). Da sowohl i als auch j Faktorvorkommen sind, gilt u = lu0 und kein Buchstabe a aus u0 ist bezüglich der partiellen Ordnung <=t von t = hMt; <=ti kleiner als ein Buchstabe aus l = hMl; <=li. Anderenfalls wäre Pret(l) \ Postt(l) 6= l und damit i kein Faktorvorkommen. Alle minimalen Buchstaben minPostt(l) liegen in i(l) bzw. j(l). Mit Induktion über die Anzahl der Elementarfaktoren von l erhalten wir i = j und damit die Antisymmetrie von ?. A.3 Zusammenhängende Faktoren Wir bezeichnen eine Spur t als zusammenhängend, wenn der Abhängigkeitsgraph zusammenhängend ist oder äquivalent, wenn das induzierte Abhängigkeitsalphabet (?; D)(l) ein zusammenhängender Graph ist. Wir analysieren in diesem Abschnitt die relativen Beziehungen zwischen Vorkommen bzw. Faktorvorkommen. Seien i; j : l ?! t zwei Vorkommen von einer zusammenhängenden Spur l. Wir definieren die Vorkommenordnung n=n(l;t) analog via i n j :() Post(j) ? Post(i): j(l) i(l) Post(i) = t Post(j) Lemma 44 Seien l; t 2 M (?; D) zwei Spuren und l zusammenhängend. Dann ist die Relation n=n(l;t) eine lineare Ordnung. Beweis: Die Reflexivität und die Transitivität folgt aus den vorhergehenden Betrachtungen. Die Linearität zeigen wir induktiv. Seien i; j : l ?! t zwei Faktorvorkommen (l zusammenhängend). Existieren zwei Buchstaben a und b in l = hMl; <=li mit a <=l b, so gilt auch i(a) <=t i(b), da i ordnungserhaltend ist. Sind a; b zwei Buchstaben so, daß kein Buchstabe c 2 ?(l) mit a <=l c <=l b existiert, so existiert auch kein Buchstabe c in t 94 mit i(a) <=t c <=t i(b). Würde ein Buchstabe c in t existieren mit i(a) <=t c <=t i(b), dann existiert in der Projektion ßfa;b;cg(u; l; v) = ? ßfa;b;cg(u); ßfa;b;cg(l); ßfa;b;cg(v) ? ein c zwischen i(a) und i(b), ßfa;b;cg(t) = w i(a) x c y i(b) z, im Widerspruch zu ßfa;b;cg(l) = ffßfa;b;cg(l)fi mit ff; fi 2 fa; b; cg? (preßfa;b;cg(i(l))(i(a)) = ff und postßfa;b;cg(i(l))(i(b)) = fi). Behauptung: Sei a lg und (ak; ak+1) 2 D, k 2 [n ? 1]. Wir bezeichnen die duale Ordnung zu <= mit >=. Mit dem vorhergehenden Resultat schließen wir mit Induktion über die Länge n des Pfades i(a1) ?0 1 i(a2) ?0 2 : : : ?0 n?1 i(an) ? ? ? j(a1) ?0 1 j(a2) ?0 2 : : : ?0 n?1 j(an); mit ?0 k; ?2 f<=t; >=tg, k 2 [n ? 1]. Damit gilt Post(i) ? Post(j) oder Post(j) ? Post(i) und n ist eine lineare Ordnung. Seien t; l 2 M (?; D) zwei Spuren. Wir sagen, ein Buchstabe a in t = hMt; <=ti beeinträchtigt ein Vorkommen i : l ?! t, falls a nicht zu i(l) gehört und zwei Buchstaben b; c in l mit i(b) <=t a <=t i(c) existieren. Wir notieren diesen Zusammenhang mit a B i. = t a i c b i(l) l = 95 Sei a 2 ? und sei i : l ?! t, l; t 2 M (?; D), ein Vorkommen. Wir bezeichnen mit (a) B i die Menge der das Vorkommen i beeinträchtigenden Buchstaben a in t, fa 2 Mt j 9b; c 2 Ml : i(b) <=t a <=t i(c); a = 2 i(l)g. Die Teilmenge aller Buchstaben a 2 ?, die in t = hMt; <=ti vorkommen, ist durch <=t linear geordnet. Lemma 45 Seien l; t 2 M (?; D) Spuren und i ein Vorkommen i : l ?! t. Dann ist die Menge (a) B i ein Intervall bezüglich <=t, t = hMt; <=ti. Beweis: Seien a1, a2 und a3 drei (Vorkommen des) Buchstaben a in t = hMt; <=ti mit a1 <=t a2 <=t a3, und das Vorkommen i : l ?! t werde von den Buchstaben a1 und a3 beeinträchtigt. (In Zeichen: a1 B i und a3 B i.) Dann beeinträchtigt auch der Buchstabe a2 das Vorkommen i, denn aus a1 B i folgt die Existenz eines Buchstaben b in l = hMl; <=li mit i(b) <=t a1 und aus a3 B i folgt die Existenz eines Buchstaben c in l mit a3 <=t i(c). Zusammengefaßt beeinträchtigt a2 das Vorkommen i via i(b) <=t a1 <=t a2 <=t a3 <= i(c): Analog zur Menge der beeinträchtigenden Buchstaben bezeichnen wir mit a B (l; t) die Menge der beeinträchtigten Vorkommen von l in t, fi : l ?! t j a B ig. Lemma 46 Seien l; t 2 M (?; D) Spuren und l zusammenhängend. Dann ist die Menge a B (t; l) ein Intervall bezüglich n=n(l;t). Beweis: Wir leiten aus der Existenz dreier Vorkommen i; j; k : l ?! t und eines Buchstabens a in t mit i n j n k und a B i, a B k aber a 7 j einen Widerspruch her. Aus a B k folgt die Existenz eines minimalen Buchstaben b in l mit k(b) <=t a. Da i n k gilt j(b) <=t k(b) <=t a. Aus a B i folgt die Existenz eines maximalen Buchstaben c in l mit a <=t i(c), und aus i n j folgt a <=t i(c) <=t j(c). Da a = 2 ?(l), beeinträchtigt der Buchstabe a das Vorkommen j, j(b) <=t a <=t k(c), ein Widerspruch. l = i(l) j(l) k(l) i j k = t a Interessanterweise ist die Anzahl der von einem Buchstaben beeinträchtigten durch eine von jtj unabhängige Konstante beschränkt. Lemma 47 Seien l; t 2 M (?; D) zwei Spuren und a ein Buchstabe in t. Dann ist die Kardinalität der Menge a B (l; t) der beeinträchtigten Vorkommen durch die Konstante jlj ? j?j beschränkt. 96 Beweis: Wir führen die Annahme ja B (l; t)j > jlj ? j?j zu einem Widerspruch. Sei ja B (l; t)j > jlj?j?j, dann existieren mindestens n >= j?j paarweise disjunkte Vorkommen i1 n i2 n : : : n in. Zwei Vorkommen i; j : l ?! t sind disjunkt, falls i(l) \ j(l) = ;. Wäre n < j?j, so würde ein Buchstabe b in l und zwei Vorkommen i; j 2 fi1; : : : ; ing existieren mit i 6= j und i(b) = j(b), ein Widerspruch (siehe Beweis zu Lemma 44). Sind i1; : : : ; in disjunkte Vorkommen, so folgt aus Lemma 44, für alle Buchstaben d in l und für alle i; j 2 fi1; : : : ing, i(d) lg für alle k 2 [m?1] im Abhängigkeitsgraphen von l = hMl; <=ti mit (ak; ak+1) 2 D für alle k 2 [n ? 1], n <= j?j. = l a1 a2 a4 a5 a2 am Da m minimal ist, kann kein Buchstabe in fa1; : : : ; an?1g ? Ml (Knoten im zugehörigen Abhängigkeitsgraphen) mehrmals vorkommen, d.h. k < j?j. Damit erhalten wir einen Widerspruch zur Antisymmetrie a <=t i1(am) c := 2nn0n00. Seien io : lk ?! t, o 2 [m], die Faktorvorkommen mit i 2 Ik(io) für alle o 2 [m] und Ik(io) 6= Ik(io0) für alle o 6= o0. Für alle Intervalle Ik(io) = [xo; yo], existiert dann - eine Rückwärts-Sequenz, die von einem Buchstaben aus j(lk0) startet und in x0 o(lk) endet, oder - eine Vorwärts-Sequenz, die von einem Buchstaben aus j(lk0) startet und in y0(lk) endet. j j y0 o lk lk0 Ik(io) x0 o Da NI(i) = m > c, existiert ein Sprungwort w 2 S(?; D) so, daß n00 >= jwj Vorwärts- Sprungsequenzen, die in verschiedenen Faktorvorkommen x0 o : lk ?! t beginnen. lk lk0 Sei Ik0(io) = [xo; yo]. Dann existieren Buchstaben b; c mit ? x1(a) <=t y1(b) (siehe Skizze), ein Widerspruch zu Ik(i1) 6= ; bzw. Ik(i1) \ Ik(im) 6= ;. 106 Literatur [Aho90] Alfred V. Aho. Algorithms for finding patterns in strings. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, pages 255{300. Elsevier, Amsterdam, 1990. [AR88] IJsbrand Jan Aalbersberg and Grzegorz Rozenberg. Theory of traces. Theoretical Computer Science, 60:1{82, 1988. [BD93] Michael Bertol and Volker Diekert. On efficient reduction-algorithms for some trace rewriting systems. In H. Common and J.-P. Jouannaud, editors, Proceedings of the Term Rewriting., number 909 in Lecture Notes in Computer Science, pages 114{126, Berlin-Heidelberg-New York, 1993. Springer. [BD96] Michael Bertol and Volker Diekert. Trace rewriting: Computing normal forms in time O(n log n). In C. Puech and R. Reischuk, editors, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science 1996, number 1046 in Lecture Notes in Computer Science, pages 269{280, Berlin-Heidelberg-New York, 1996. Springer. [Ber95] Michael Bertol. Efficient rewriting in cograph trace monoids. In H. Reichel, editor, Proceedings of the 10th Fundamentals of Computation Theory (FCT '95), Dresden (Germany) 1995, number 965 in Lecture Notes in Computer Science, pages 146{155, Berlin-Heidelberg-New York, 1995. Springer. [BL87] Ronald Book and Hai-Ning Liu. Rewriting systems and word problems in a free partially commutative monoid. Information Processing Letters, 26:29{ 32, 1987. [BMS83] Alberto Bertoni, Giancarlo Mauri, and Nicoletta Sabadini. Concurrency and commutativity. Technical report, Instituto di Cibernetica, Universit?a di Milano, 1983. Presented at the Workshop on Petri nets, Varenna (Italy), 1982. [BO93] Ronald Book and Friedrich Otto. String Rewriting Systems. Texts and Monographs in Computer Science. Springer Verlag, New York, 1993. [Boo82] Ronald Book. Confluent and other types of Thue systems. J. Assoc. Comput. Mach., 29:171{182, 1982. [CF69] Pierre Cartier and Dominique Foata. Probl?emes combinatoires de commutation et r?earrangements. Number 85 in Lecture Notes in Mathematics. Springer, Berlin-Heidelberg-New York, 1969. [Cho90] Christian Choffrut. A remark on the representation of trace monoids. Semigroup Forum, 40:143{152, 1990. 107 [CL84] Mireille Clerbout and Michel Latteux. Partial commutations and faithful rational transductions. Theoretical Computer Science, 34:241{254, 1984. [Cle84] Mireille Clerbout. Commutations Partielles et Familles de Langages. Th?ese, Universit?e des Sciences et Technologies de Lille (France), 1984. [CLRW95] Mireille Clerbout, Michel Latteux, Yves Roos, and Pierre-Andr?e Wacrenier. A result on confluence for one-rule trace-rewriting systems. Technical Report IT-95-275, Laboratoire d'Informatique Fondamentale de Lille, Universite des Sciences et Technologies de Lille, Apr. 1995. [CM88] Robert Cori and Yves M?etivier. Approximation of a trace, asynchronous automata and the ordering of events in a distributed system. In Proceedings of the 15th International Colloquium on Automata, Languages and Programming (ICALP'88), number 317 in LNCS, pages 147{161. Springer, 1988. [CMZ90] Robert Cori, Yves M?etivier, and Wies law Zielonka. Applications of trace approximation to asynchronous automata and message passing with bounded time-stamps in asynchronous networks. Technical report, Univ. Bordeaux, 1990. [Cou90] Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 193{242. Elsevier, Amsterdam, 1990. [CP85] Robert Cori and Dominique Perrin. Automates et commutations partielles. R.A.I.R.O. | Informatique Th?eorique et Applications, 19:21{32, 1985. [Dau88] Max Dauchet. Termination of rewriting is undecidable in the one-rule case. In M. Chytil et al., editors, Proceedings of the 13th Symposium on Mathematical Foundations of Computer Science (MFCS'88), Carlsbad (CSSR) 1988, number 324 in Lecture Notes in Computer Science, pages 262{288, Berlin- Heidelberg-New York, 1988. Springer. [Die87] Volker Diekert. On the Knuth-Bendix completion for concurrent processes. In Th. Ottmann, editor, Proceedings of the 14th International Colloquium on Automata, Languages and Programming (ICALP'87), Karlsruhe (FRG) 1987, number 267 in Lecture Notes in Computer Science, pages 42{ 53, Berlin-Heidelberg-New York, 1987. Springer. Appeared also in a revised version in Theoretical Computer Science 66:117-136, 1989. [Die89] Volker Diekert. Word problems over traces which are solvable in linear time. In B. Monien et al., editors, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS'89), Paderborn (FRG) 1989, number 349 in Lecture Notes in Computer Science, pages 168{180, Berlin-Heidelberg-New York, 1989. Springer. Revised and extended version in Theoretical Computer Science 74 (1990) 3-18. 108 [Die90a] Volker Diekert. Combinatorial rewriting on traces. In C. Choffrut et al., editors, Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science (STACS'90), Rouen (France) 1990, number 415 in Lecture Notes in Computer Science, pages 138{151, Berlin-Heidelberg-New York, 1990. Springer. [Die90b] Volker Diekert. Combinatorics on Traces. Number 454 in Lecture Notes in Computer Science. Springer, Berlin-Heidelberg-New York, 1990. [Die92] Volker Diekert. Mathematical aspects of trace theory. Mitt. Math. Ges. Hamburg, 12:1171{1181, 1992. Special issue of the tricentenary. [Die93] Volker Diekert. Rewriting, semi-commutations, and Möbius functions. In Z. ? Esik, editor, Proceedings of the 9th Fundamentals of Computation Theory (FCT'93), Szeged (Hungary) 1993, number 710 in Lecture Notes in Computer Science, pages 1{15, Berlin-Heidelberg-New York, 1993. Springer. Invited Lecture. [Die94] Volker Diekert. A partial trace semantics for Petri nets. Theoretical Computer Science, 134:87{105, 1994. Special issue of ICWLC 92, Kyoto (Japan). [DJ90] Noam Dershowitz and Jean-Pierre Jouannaud. Rewrite systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 243{320. Elsevier, Amsterdam, 1990. [DMR95] Volker Diekert, Anca Muscholl, and Klaus Reinhardt. On codings of traces. In E.W. Mayr and C. Puech, editors, Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS'95), 1995, number 900 in Lecture Notes in Computer Science, pages 385{396, Berlin- Heidelberg-New York, 1995. Springer. [DR95] Volker Diekert and Grzegorz Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995. [Dub85] Christine Duboc. Some properties of commutation in free partially commutative monoids. Information Processing Letters, 20:1{4, 1985. [Dub86] Christine Duboc. On some equations in free partially commutative monoids. Theoretical Computer Science, 46:159{174, 1986. [Fis86] W. Fischer. Über erkennbare und rationale Mengen in freien partiell kommutativen Monoiden. Report FBI-HH-B-121/86, Fachbereich Informatik der Universität Hamburg, Hamburg, 1986. (Diplomarbeit 1985). [Har78] Michael A. Harrison. Introduction to Formal Language Theory. Addison- Wesley Publishing Company, 1978. [Hoa78] C. A. R. Hoare. Communicating sequential processes. Communications of the Association of Computing Machinery, 21(8):666{677, 1978. 109 [Hoa85] C. A. R. Hoare. Communicating Sequential Processes. Prentice-Hall International, London, 1985. [HU69] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley publishing company, 1969. [Hue80] G?erard Huet. Confluent reduction: Abstract properties and applications to term rewriting systems. J. Assoc. Comput. Mach., 27:797{821, 1980. [HY92] Kosaburo Hashiguchi and Kazuya Yamada. String matching problems over free partially commutative monoids. Information and Computation, 101:131{ 149, 1992. [Jan84] R. Janicki. Mazurkiewicz traces semantics for communicating sequential processes. In Proceedings of the 5th European Workshop on Appl. and Theory of Petri Nets, pages 50 { 70, Aarhus, 1984. [Jan88] Matthias Jantzen. Confluent String Rewriting. EATCS Monographs on Theoretical Computer Science 14. Springer, Berlin-Heidelberg-New York, 1988. [Kel73] Robert M. Keller. Parallel program schemata and maximal parallelism I. Fundamental results. Journal of the Association of Computing Machinery, 20(3):514{537, 1973. [KMP77] Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6:323{350, 1977. [Lam78] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the Association of Computing Machinery, 21:558{564, 1978. [LL90] L. Lamport and L. Lynch. Distributed computing: Models and methods. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 1157{1200. Elsevier, Amsterdam, 1990. [Lot83] M. Lothaire. Combinatorics on Words. Addison-Wesley, Reading, M.A., 1983. [Maz77] Antoni Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977. [Maz84] Antoni Mazurkiewicz. Traces, histories, graphs: Instances of a process monoid. In M. P. Chytil et al., editors, Proceeding of the 11th Symposium on Mathematical Foundations of Computer Science (MFCS'84), Prague, (Czechoslovakia) 1984, number 176 in Lecture Notes in Computer Science, pages 115{133, Berlin-Heidelberg-New York, 1984. Springer. 110 [Maz87] Antoni Mazurkiewicz. Trace theory. In W. Brauer et al., editors, Petri Nets, Applications and Relationship to other Models of Concurrency, number 255 in Lecture Notes in Computer Science, pages 279{324, Berlin-Heidelberg- New York, 1987. Springer. [Mil80] Robin Milner. A Calculus of Communicating Systems. Number 92 in Lecture Notes in Computer Science. Springer, Berlin-Heidelberg-New York, 1980. [Mil90] Robin Milner. Operational and algebraic semantics of concurrent processes. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 1201{1242. Elsevier, Amsterdam, 1990. [MM82] Ernst W. Mayr and Albert R. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Math., 46:305{329, 1982. [MT90] K. Mehlhorn and A. Tsakalidis. Data structures. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, pages 301{ 335. Elsevier, Amsterdam, 1990. [NO88] Paliath Narendran and Friedrich Otto. Preperfectness is undecidable for Thue systems containing only length-reducing rules and a single commutation rule. Information Processing Letters, 29:125{130, 1988. [Ott89] Friedrich Otto. On deciding confluence of finite string rewriting systems modulo partial commutativity. Theoretical Computer Science, 67:19{36, 1989. [Ott95] Friedrich Otto. On confluence versus strong confluence for one-rule tracerewriting systems. Mathematical Systems Theory, 28:363{384, 1995. [Pra86] Vaughan R. Pratt. Modelling concurrency with partial orders. International Journal of Parallel Programming, 15(1):33{71, 1986. [Rei85] Wolfgang Reisig. Petri Nets (an Introduction). Number 4 in EATCS Monographs on Theoretical Computer Science. Springer, Berlin-Heidelberg-New York, 1985. [WD95] Celia Wrathall and Volker Diekert. On confluence of one-rule trace-rewriting systems. Mathematical Systems Theory, 28:341{361, 1995. [WDO92] Celia Wrathall, Volker Diekert, and Friedrich Otto. One-rule trace-rewriting systems and confluence. In I. M. Havel and V. Koubek, editors, Proceedings of the 17th Symposium on Mathematical Foundations of Computer Science (MFCS'92), Prague, (Czechoslovakia), 1992, number 629 in Lecture Notes in Computer Science, pages 511{521, Berlin-Heidelberg-New York, 1992. Springer. [Wei94] Mark Allan Weiss. Data Structures and Algorithm Analysis. Benjamin/Cummings Publishing Company, 1994. 111 Index Symbole (I1; : : : ; In)(i) : : : : : : : : : : : : : : : : : : : : : : 102 (?1; D1) _ (?2; D2) : : : : : : : : : : : : : : : : : 54 (?1; D1) ^ (?2; D2) : : : : : : : : : : : : : : : : : 54 (?; D) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 (?; D)(t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 (?; D?) ? (?; D?) : : : : : : : : : : : : : : : 19, 53 (?; D?) ? (?; D?) : : : : : : : : : : : : : : : 19, 53 (a) B i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 98 CT (l1; l2; R) : : : : : : : : : : : : : : : : : : : : : : : : 17 C ? ? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 CritPair(R) : : : : : : : : : : : : : : : : : : : : : : : : : 17 D ? ? ? ? : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 FN (t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 FN (t) u FN 0 (t) : : : : : : : : : : : : : : : : : : : : : : 93 FN (t) t FN 0 (t) : : : : : : : : : : : : : : : : : : : : : : 93 I 0 k(i) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102 I = (? ? ?) n D : : : : : : : : : : : : : : : : : : : : : : 7 IN(t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 IN(t) u IN 0 (t) : : : : : : : : : : : : : : : : : : : : : : : 92 IN(t) t IN 0 (t) : : : : : : : : : : : : : : : : : : : : : : : 92 Ik(i) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102 L(h(t)) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 61 Ld(t) ? [n] : : : : : : : : : : : : : : : : : : : : : : : : : : 61 M = (Q; ?; ?; ffi; q0; F; b) : : : : : : : : : : : : : 13 P (h(t)) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 61 S(h(t)) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 61 [n] : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 G (?; D) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 M (?; D) = ??=?I : : : : : : : : : : : : : : : : : : : : 7 M =R : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 O(?; D) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 T(?; D) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56 Con(t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 101 Dec(l) = Dec(h(l)) : : : : : : : : : : : : : : : : : : 60 Dec(R) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 Dec?(?; D) : : : : : : : : : : : : : : : : : : : : : : : : : : 54 N?-Bäume : : : : : : : : : : : : : : : : : : : : : : : : : : 79 Postt(l) = ta2MlFa(t) : : : : : : : : : : : : : : : 93 Pret(l) = ta2MlIa(t) : : : : : : : : : : : : : : : : : 93 Pref(t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 Pref(R) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 ? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 ?(t) ? ? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 ?? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 Suff(t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 Suff(R) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 ffi : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56 hM; <=i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 n =)R : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 `R(t) = maxfn 2 N j t n =)R t0g : : : : : : 11 dR(n) = maxf`R(t) 2 N j jtj = n; t 2 M g: : : : : : : : : : : : : : : : : : : : : : : : : : 12 ?I? ?? ? ?? : : : : : : : : : : : : : : : : : : : : : : : : : 7 ? 7??M : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13 indt(l) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 93 >=1 : V ?! P(C) : : : : : : : : : : : : : : : : : : : : : 21 >=2 : V ?! P(LR) : : : : : : : : : : : : : : : : : : : 21 ?: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52, 95 n : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 96 max : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 min : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 ? =)R : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 r : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 101 r(I; lk) : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102 ß? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 ßa : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 ßfag : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 postt(l) = ta2MlFa(t) n l : : : : : : : : : : : : : 93 pret(l) = ta2MlIa(t) n l : : : : : : : : : : : : : : 93 min(t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 a B i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 97 a B (l; t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : 98 h(?;D) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 55 i : l ?! t : : : : : : : : : : : : : : : : : : : : : : : : : : : 94 iOj : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 101 tC = ßC(t) : : : : : : : : : : : : : : : : : : : : : : : : : : 94 x ? y , y ? =)R uxv : : : : : : : : : : : : : : : 16 LR : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 F : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 R ? M (?; D) : : : : : : : : : : : : : : : : : : : : : : : 11 Dec(?; D) : : : : : : : : : : : : : : : : : : : : : : : : : : 53 Dec(R) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 59 Irr(R) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 112 Red(R) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 I(l; t) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 103 A Abhängigkeitsalphabet : : : : : : : : : : : : : : 7 dekompositionierbares : : : : : : : : : : : 71 zerlegbares : : : : : : : : : : : : : : : : : : : : : : 71 Ableitungsrelation : : : : : : : : : : : : : : : : : : 11 Alphabet : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 atomares : : : : : : : : : : : : : : : : : : : : : : : : 56 B Beschriftungen : : : : : : : : : : : : : : : : : : 21, 61 Buchstaben : : : : : : : : : : : : : : : : : : : : : : : : : : 7 beeinträchtigende : : : : : : : : : : : : : : : 97 sichtbare : : : : : : : : : : : : : : : : : : : : : : : : 45 C C?-Baum : : : : : : : : : : : : : : : : : : : : : : : : : : : 21 Beschriftung : : : : : : : : : : : : : : : : : : : : 21 Höhe : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 Repräsentation : : : : : : : : : : : : : : : : : : 21 Charakterisierung von Faktoren : : : : : 92 Church-Rosser-Eigenschaft : : : : : : : : : : 12 Clique : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 Cographen-Monoid : : : : : : : : : : : : : : 19, 53 COMPOSE : : : : : : : : : : : : : : : : : : : : : : : : : 62 CONCAT : : : : : : : : : : : : : : : : : : : 33, 34, 62 CONCATandREDUCE : : : : : : : : : : 73, 74 CONCATENATE : : : : : : : : : : : : : : : : : : : 29 CONCATTRACE : : : : : : : : : : : : : : : : : : : 36 D dekomponierbar : : : : : : : : : : : : : : : : : : : : : 72 Dekomposition : : : : : : : : : : : : : : : : : : 53, 60 von Alphabeten 53, 60 von Ersetzungssystemen : : : : : : : : : 60 von linken Seiten : : : : : : : : : : : : : : : : 60 DELETE : : : : : : : : : : : : : : : : : : : : 29, 32, 83 Derivationsrelation : : : : : : : : : : : : : : : : : : 11 Deskription : : : : : : : : : : : : : : : : : : : : : : : : : 53 direkte Summe : : : : : : : : : : : : : : : : : : 19, 53 DIVIDE : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 E Einschritttransitionsrelation : : : : : : : : : 13 elementaren Schritte : : : : : : : : : : : : : : : : : 7 Ersetzungssystem gewichtsreduzierendes : : : : : : : : : : : 11 konfluentes : : : : : : : : : : : : : : : : : : : : : : 11 langenreduzierendes : : : : : : : : : : : : : 11 noethersches : : : : : : : : : : : : : : : : : : : : 11 normalisiertes : : : : : : : : : : : : : : : : : : : 12 vollständiges : : : : : : : : : : : : : : : : : : : : 12 F FACTORIZE : : : : : : : : : : : : : : : : : : : : : : : 73 Faktor : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 Faktoren kombinierbare : : : : : : : : : : : : : : : : : : 101 zerfaserte : : : : : : : : : : : : : : : : : : : : : : : 53 zusammenhängende : : : : : : : : : : : : : 96 Faktorisierung : : : : : : : : : : : : : : : : : : : 73, 92 Faktorordnung : : : : : : : : : : : : : : : : : : : : : : 95 Faktorvorkommen : : : : : : : : : : : : : : : 16, 95 Filter : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 frei partiell kommutatives Monoid : : : : 7 H Homomorphismus : : : : : : : : : : : : : : : : : : : : 8 I Ideal : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 INCORPORATE : : : : : : : : : : : : : : : : : : : 30 induziertes Alphabet : : : : : : : : : : : : : : : : : 7 INSERT : : : : : : : : : : : : : : : : : : : : : : : : 29, 83 Intervall : : : : : : : : : : : : : : : : : : : : : : : : : : : : 98 Intervallrelation : : : : : : : : : : : : : : : : : : : : 103 K kombinierbar : : : : : : : : : : : : : : : : : : : : : : 101 Komplexprodukt : : : : : : : : : : : : : : : : 19, 53 Konfiguration : : : : : : : : : : : : : : : : : : : : : : : 13 akzeptierende : : : : : : : : : : : : : : : : : : : 13 Konfluenzproblem : : : : : : : : : : : : : : : : : : : 12 korrekt beschriftet : : : : : : : : : : : : : : : : : : 62 L leftQUOTIENT : : : : : : : : : : : : : : : : : : : : : 70 Lemma von Levi : : : : : : : : : : : : : : : : : : : : 58 Links-Derivation : : : : : : : : : : : : : : : : : 12, 74 Linksquotient : : : : : : : : : : : : : : : : : : : : : : : 62 M Multimenge : : : : : : : : : : : : : : : : : : : : : : : : : : 8 113 N Normalformen : : : : : : : : : : : : : : : : : : : : : : : 7 Foata : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 Normalformproblem : : : : : : : : : : : : : : : : : 12 nuklear : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56 P Parikh-Bilder : : : : : : : : : : : : : : : : : : : : : : : 47 partiell geordnete Multimengen : : : : : : : 8 Position : : : : : : : : : : : : : : : : : : : : : : : : : : : : 82 PRED : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 pred : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 24 PREPROCESSING : : : : : : : : : : : : : : : : : 48 Produkt direktes : : : : : : : : : : : : : : : : : : : : : 54, 94 freies : : : : : : : : : : : : : : : : : : : : : : : : : : : : 54 PROJECT : : : : : : : : : : : : : : : : : : : : : : : : : : 63 Projektionen : : : : : : : : : : : : : : : : : : : : : : : : : 9 PROPAGATE1 : : : : : : : : : : : : : : : : : : : : : 31 PROPAGATE2 : : : : : : : : : : : : : : : : : : : : : 37 R Rechtsquotient : : : : : : : : : : : : : : : : : : : : : : 70 REDUCE : : : : : : : : : : : : : : : : : : : : : : : : : : : 41 REDUCEnSTEPS : : : : : : : : : : : : : : : : : : 50 Reduktionsordnung : : : : : : : : : : : : : : : : : 16 REMOVE : : : : : : : : : : : : : : : : : : : : : : : : : : 32 rightQUOTIENT : : : : : : : : : : : : : : : : : : : 70 S Schnitt : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36 Schnittlemma : : : : : : : : : : : : : : : : : : : : : : 100 schwache Beschriftung : : : : : : : : : : : : : : : 79 separiert : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 Sichtbarkeit : : : : : : : : : : : : : : : : : : : : : : : : : 45 SPLIT : : : : : : : : : : : : : : : : : : : : : : : 29, 35, 62 SPLITTRACE : : : : : : : : : : : : : : : : : : 36, 40 Sprungwort : : : : : : : : : : : : : : : : : : : : : : : : 104 Spur : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 irreduzible : : : : : : : : : : : : : : : : : : : : : : 12 reduzible : : : : : : : : : : : : : : : : : : : : : : : : 12 Spurersetzungssystem : : : : : : : : : : : : : : : 11 Spurmonoid : : : : : : : : : : : : : : : : : : : : : : : : : : 7 Spurterm : : : : : : : : : : : : : : : : : : : : : : : : : : 56 korrekt beschrifteter : : : : : : : : : : : : 62 schwach beschrifteter : : : : : : : : : : : : 79 Subspur : : : : : : : : : : : : : : : : : : : : : : : : : : : : 93 Suffix : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 T temporalen Struktur : : : : : : : : : : : : : : : : : 1 Term : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 62 korrekt beschrifteter : : : : : : : : : : : : 62 linearer : : : : : : : : : : : : : : : : : : : : : : : : : 53 schwach beschrifteter : : : : : : : : : : : : 79 topologische Permutation : : : : : : : : : : : : : 9 Turingmaschine : : : : : : : : : : : : : : : : : : : : : 13 U Unentscheidbarkeit : : : : : : : : : : : : : : : : : : 13 V Vorkommen : : : : : : : : : : : : : : : : : : 80, 93, 94 induziertes : : : : : : : : : : : : : : : : : : : : : : 93 Vorkommen-Morphismus : : : : : : : : : : : : 94 Vorkommenbaum : : : : : : : : : : : : : : : : : : : 80 Vorkommenordnung : : : : : : : : : : : : : 52, 96 W wohlgeformte Terme : : : : : : : : : : : : : : : : : 55 Wort-Morphismus : : : : : : : : : : : : : : : : : : : 95 Z Zerfaserung : : : : : : : : : : : : : : : : : : : : : : : : : 53 zerlegbar : : : : : : : : : : : : : : : : : : : : : : : : : : : : 72 zusammenhängend : : : : : : : : : : : : : : : : : : 96 Zusammenhangskomponente : : : : : : : 101 114