Prioritätszählerautomaten und die Synchronisation von Halbspursprachen

Von der Fakultät Informatik der Universität Stuttgart zur Erlangung der Würde eines Doktors der Naturwissenschaften

genehmigte Abhandlung

von Klaus Reinhardt aus Stuttgart

Hauptberichter: Prof. Dr. V. Diekert Mitberichter: Prof. Dr. K.-J. Lange

Tag der mündlichen Prüfung: 7. Juli 1994

Stuttgart, 1994

Vorwort

Mein besonderer Dank gilt Prof. Dr. Volker Diekert, der mein Interesse für Halbspuren geweckt hat, für die intensive Unterstützung und Betreuung meiner Arbeit und Prof. Dr. Klaus-Jörn Lange für die Übernahme des Mitberichtes. Ebenso danke ich Michael Bertol, Werner Ebinger, Anca Muscholl, Wolfgang Reissenberger und Pierre-Andre Wacrenier für viele interessante Diskussionen und Prof. Dr. Michel Latteux, der mich auf das Problem der Maximalität aufmerksam gemacht hat.

Zusammenfassung

In dieser Arbeit wird gezeigt daß das Leerheitsproblem für die von einem Prioritätsmulticounterautomaten erkannte Sprache und damit auch das Halteproblem für Prioritätsmulticounterautomaten entscheidbar ist. Hierbei wird vorausgesetzt, daß das Erreichbarkeitsproblem für Petrinetze, bei denen die inhibitorischen Kanten auf eine bestimmte Art und Weise angeordnet sind (siehe [Rei94]), entscheidbar ist. Die Beziehungen der von diesen Automaten erkannten Prioritätsmulticountersprachen zu anderen Sprachklassen wird beschrieben und es wird gezeigt, daß die Sprache {(a^{n}b)^{m} | n, m ∈ ℕ} keine Prioritätsmulticountersprache ist.

Damit werden notwendige und hinreichende Kriterien für solche Semikommutationssysteme entwickelt, bei denen eine Halbspursprache, d.h. die die Hülle einer regulären Sprache unter diesem Semikommutationssystem, von einem Prioritätsmulticounterautomaten erkannt und damit die Maximalität und die Synchronisierbarkeit mit einer regulären Sprache entschieden werden kann. Ferner werden Kriterien für Semikommutationssysteme entwickelt, bei denen die Maximalität und die Synchronisierbarkeit von Halbspursprachen unentscheidbar ist.

Für Halbspuren werden Kriterien für die Inklusion, die Synchronisierbarkeit, für die Frage, ob die Synchronisation von Halbspuren wieder eine Halbspur ist und für die Existenz einer nicht konfluenten Situation gezeigt und deren Komplexität ermittelt. Gleiches erfolgt für diese Eigenschaften der Halbspuren eines Semikommutationssystems im allgemeinen.

Inhaltsverzeichnis

1 Einleitung 5

2 Begriffe 7 2.1 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Spuren und Kommutationen . . . . . . . . . . . . . . . . . . . . . 9 2.3 Halbspuren und Semikommutationen . . . . . . . . . . . . . . . . 9 2.4 Komplexitätsklassen . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.1 Reduktion und Orakel . . . . . . . . . . . . . . . . . . . . 11 2.4.2 Schaltkreiskomplexitätsklassen . . . . . . . . . . . . . . . . 13

2.5 Petrinetze mit inhibitorischen Kanten . . . . . . . . . . . . . . . . 15 2.6 Multimengen und Vektoren . . . . . . . . . . . . . . . . . . . . . 16 2.7 Geschachtelte Petrinetze . . . . . . . . . . . . . . . . . . . . . . . 17

3 Prioritätsmulticounterautomaten 24 3.1 Multicounter- und Prioritätsmulticountersprachen . . . . . . . . . 26 3.2 Die Inklusionsstruktur der Sprachklassen . . . . . . . . . . . . . . 28

4 Die Synchronisation von Halbspuren 32 4.1 Die Inklusion von Halbspuren . . . . . . . . . . . . . . . . . . . . 32 4.2 Die Synchronisierbarkeit von Halbspuren . . . . . . . . . . . . . . 34 4.3 Die Synchronisierbarkeit in Semikommutationssystemen . . . . . . 37 4.4 Das lokale Überprüfen der Synchronisierbarkeit von Halbspuren . 49

5 Die Synchronisation und die Maximalität von Halbspursprachen 50 5.1 Zählerhalbabhängigkeiten . . . . . . . . . . . . . . . . . . . . . . 51 5.2 Prioritätszählerhalbabhängigkeiten . . . . . . . . . . . . . . . . . 51

5.2.1 Hinreichendes Kriterium . . . . . . . . . . . . . . . . . . . 59 5.2.2 Notwendiges Kriterium . . . . . . . . . . . . . . . . . . . . 65

5.3 Unentscheidbare Fälle . . . . . . . . . . . . . . . . . . . . . . . . 68

6 Die Konfluenz von Semikommutationssystemen 77

1 Einleitung

Bei der formalen Beschreibung von Prozessen spielt die Reihenfolge der einzelnen Aktionen bereits bei sequentiellen Systemen eine große Rolle; z.B. bei der Optimierung von Programmcodes ist es wichtig zu betrachten, welche der einzelnen Anweisungen mit welchen anderen vertauscht werden können und welche abhängig sind. Beispielsweise sind die Zuweisungen m := n + o und o := n ∗ p abhängig, wohingegen die Zuweisungen m := n + o und p := n ∗ o unabhängig sind. Um dies mit mathematischen Instrumenten beschreiben zu können, werden Monoide von Spuren betrachtet. Die Spur, welche die möglichen Ablauffolgen eines Prozesses beschreibt, ist eine Äquivalenzklasse von durch Vertauschen unabhängiger Aktionen auseinander ableitbaren Ablauffolgen. Durch Spuren und Spursprachen kann man somit gültige Evaluierungen eines Prozesses beschreiben. Da die Computertechnik mit der Schaltgeschwindigkeit von Halbleiterelementen auf Grenzen stößt, kommt die Forschung in der letzten Zeit von nur sequentiell arbeitenden Computern immer mehr zu parallelen Systemen. Durch die nun auftretende Nebenläufigkeit von Aktionen in einem parallelen Prozess erhält die richtige Behandlung der Reihenfolge eine ganz entscheidende Bedeutung. Beim modularen Aufbau von Prozessen ist es unumgänglich, daß die Unterprozesse Daten miteinander austauschen. Zu diesem Zweck muß eine Synchronisation der Unterprozesse stattfinden. Produziert z.B. ein Unterprozess in Aktionen mit der Bezeichnung p Daten einer bestimmten Art und ein anderer Unterprozess konsumiert in Aktionen mit der Bezeichnung c Daten dieser Art, so ist c abhängig von p, d.h. findet eine Aktion p vor c statt, so kann deren Reihenfolge nicht vertauscht werden. Umgekehrt aber kann, falls eine Aktion c vor p stattfinden kann, deren Reihenfolge vertauscht werden. Da dies mit den symmetrischen Kommutationen nicht beschrieben werden kann, werden in dieser Arbeit Semikommutationssysteme betrachtet. Mögliche Ablauffolgen werden nun durch Halbspuren beschrieben. Interessante Fragestellungen sind dabei, ob eine gegebene Ablauffolge in einer gegebenen Halbspur liegt, ob gegebene Halbspuren synchronisierbar sind, ob deren Synchronisation wieder eine Halbspur ist (siehe Kapitel 4) und ob zwei Halbspuren, die Teilmenge einer gegebenen Halbspur sind, immer synchronisierbar sind (Konfluenz siehe Kapitel 6). Auch möchte man bei gegebenen Semikommutationssystemen bereits im Vorfeld erkennen können, welche Fälle darin auftreten können, z.B. ob es darin Halbspuren gibt, deren Synchronisation selbst keine Halbspur mehr ist. Für (endliche) Halbspuren sind alle diese Fragen entscheidbar und die Erkennung der gültigen Ablauffolgen kann durch einen endlichen Automaten erfolgen. Für Halbspursprachen werden die Fragen jedoch i.a. unentscheidbar. In einigen Fällen können verschiedene Arten von Zählerautomaten verwendet werden (siehe Kapitel 5).

Eine andere mächtige Beschreibungsmethode für nebenläufige Systeme, welche viel weiter verbreitet ist, sind die von C. A. Petri Anfang der 60’er Jahre vorgestellten Petrinetze. Eine wichtige Fragestellung bei Petrinetzen ist, ob eine bestimmte Konfiguration von einer Startkonfiguration aus erreichbar ist. Bei Petrinetzen ohne inhibitorische Kanten ist die Bedingung dafür, daß eine Aktion stattfinden kann, immer nur das Vorhandensein von Marken auf Stellen, die z.B. irgendwelche Resourcen repräsentieren. Für solche Petrinetze ist bereits bekannt, daß die Frage der Erreichbarkeit entscheidbar ist. In vielen Fällen will man jedoch eine Bedingung formulieren können, welche besagt, daß das Vorhandensein einer Marke eine Aktion verhindert. Dies kann nur durch eine inhibitorische Kante ausgedrückt werden. In [Rei94] wird gezeigt, daß das Erreichbarkeitsproblem bei denjenigen Petrinetzen entscheidbar ist, bei denen die Lage der inhibitorischen Kanten eine Anordnung (Indizierung) der Stellen mit folgender Eigenschaft ermöglicht: Hat eine Transition t eine inhibitorische Kante von einer Stelle s_{j}, so hat sie auch inhibitorische Kanten von allen kleineren Stellen s_{i} mit i ≤ j. Ein Spezialfall davon ist, daß nur eine Stelle auf Null getestet werden kann, d.h. daß nur von einer Stelle inhibitorische Kanten ausgehen. In Kapitel 3 wird der dazu korrespondierende Prioritätsmulticounterautomat beschrieben, bei dem die Anordnung der Zähler der Anordnung der Stellen im Petrinetz entspricht und dessen Leerheits- bzw. Halteproblem dem Erreichbarkeits problem im Petrinetz entspricht. Dieser Prioritätsmulticounterautomat wird später in Kapitel 5 verwendet um bestimmte Halbspursprachen zu erkennen.

2 Begriffe

2.1 Grundbegriffe

Wichtige Bezeichnungen aus [HU79] werden im folgenden zusammengefaßt beschrieben: Für ein Alphabet, d.h. eine Menge von Zeichen Σ ist

Σ^{n} := {x_{1}x_{2}...x_{n} | x_{i} ∈ Σ für 1 ≤ i ≤ n}

die Menge der Wörter der Länge |x_{1}x_{2}...x_{n}| := n. Die Menge aller Wörter über Σ ist Σ^{∗} := ⋃_{n∈ℕ}Σ^{n} und Σ^{+} := ⋃_{n∈ℕ^{+}} Σ^{n}, wobei ℕ = {0, 1, ...} die Menge der

natürlichen Zahlen, ℕ_{+} = {1, 2, ...} die Menge der positiven natürlichen Zahlen und ℤ = {..., −1, 0, 1, ...} die Menge der ganzen Zahlen ist. Das Leerwort ist λ mit |λ| = 0. Eine Menge von Wörtern L ⊆ Σ^{∗} nennt man Sprache. Für Wörter x = x_{1}...x_{n} und y = y_{1}...y_{m} ist die Konkatenation xy := x_{1}...x_{n}y_{1}...y_{m} und die Spiegelung x^{R} := x_{n}...x_{2}x_{1}. Σ bildet also mit der Konkatenation und dem neutralen Element λ ein Monoid. Die Konkatenation für Sprachen L_{1} und L_{2} ist L_{1}L_{2} := {w_{1}w_{2} | w_{1} ∈ L_{1} und w_{2} ∈ L_{2}}; der Sternoperator ^{∗} ist für Sprachen definiert durch L^{∗} := ⋃_{n∈ℕ}L^{n}

und analog dazu L^{+} := ⋃_{n∈ℕ^{+}} L^{n}. Die Anzahl der Vorkommen eines Zeichens x in

einem Wort w ist |w|_{x}. Ein Wort αβγ kann mittels einer Produktionsregel β → δ in einer Menge P von Produktionsregeln abgeleitet werden zu einem Wort αδγ. Wir schreiben dafür

αβγ ⟹_{P} αδγ. Es gilt w_{0} ⟹_{P}^{∗} w_{n}, falls w_{1}, ...w_{n−1} existieren mit w_{0} ⟹_{P} w_{1} ⟹_{P}

...w_{n} und falls auch noch n > 0, so gilt w_{0} ⟹_{P}^{+} w_{n}. Durch eine Grammatik G = (V, Σ, P, S) mit der Variablenmenge V = {S, ...} und den Produktionsregeln

P ⊆ (V ∪ Σ)^{+} × (V ∪ Σ \ {S})^{∗}

wird die Sprache L(G) := {x ∈ Σ^{∗} | S ⟹_{P}^{∗} x} erzeugt. Gilt P ⊆ V × (Σ^{+}V ∪ Σ) ∪ {S → λ}, so nennt man G und damit auch L(G) regulär, im Fall

P ⊆ V × (V ∪ Σ)^{+} ∪ {S → λ}

kontextfrei und im Fall P ⊆ V × (Σ^{∗}V Σ^{∗} ∪ Σ) ∪ {S → λ} linear.

Die Projektion eines Wortes oder einer Sprache auf ein Alphabet A ist der Homomorphismus Π_{A} mit Π_{A}(a) = a, falls a ∈ A und Π_{A}(a) = λ, falls a ∉ A. Die Zahl ggT (n, m) ∈ ℕ ist der größte gemeinsame Teiler zweier natürlicher Zahlen n und m. Für Mengen ist |M| die Anzahl der Elemente in M.

2.2 Spuren und Kommutationen

Ein Abhängigkeitsaphabet über einem Alphabet A ist ein Paar (A, D) mit einer reflexiven und symmetrischen Abhängigkeitsrelation D ⊆ A^{2}. Durch dieses ist ein Kommutationssystem C := {ab → ba | (a, b) ∈ A^{2} \ D} definiert. Spuren sind Äquivalenzklassen der Form [w] := {v | w ⟹_{C}^{∗} v}; über diesen entsteht ein Monoid M(A, D) mit der Multiplikation [w] · [u] = [wu] und dem neutralen Element [λ]. Eine Spur [a_{1}...a_{n}] wird repräsentiert als ein Graph mit Knoten, welche mit a_{1}, ...a_{n} markiert sind, und gerichteten Kanten von einem mit a_{i} markierten Knoten zu einem mit a_{j} markierten Knoten, für (a_{i}, a_{j}) ∈ D und i < j. Diese freien, partiell kommutativen Monoide wurden zuerst in der Mathematik von P. Cartier und D. Foata [CF69] betrachtet. In der Informatik wurden sie erstmals von A. Mazurkiewicz [Maz77] zu Beschreibung von Schaltfolgen in 1sicheren Petrinetzen verwendet.

2.3 Halbspuren und Semikommutationen

Die Semikommutationen wurden erstmals von M.Clerbout in ihrer Dissertation [Cle84] als Verallgemeinerung der partiellen Kommutation definiert (siehe auch M. Clerbout und M. Latteux [CL87]) und eine Menge von Resultaten entstanden in letzter Zeit auf diesem Gebiet, z.B. [CG94], [CGL^{+}92], [Gon93], [Lat92], [RW91]. Mit Semikommutationen ist es nun z.B. auch möglich Systeme mit Produzenten und Konsumenten zu beschreiben und in verschiedenen Arbeiten wie [HK89], [Och90] und [Och92] stellen sich Semikommutationen bei Beschreibung von Petrinetzen als nützlich heraus. Zu jedem Halbabhängigkeitsalphabet (A, SD) mit einer reflexiven, aber möglicherweise asymmetrischen Halbabhängigkeitsrelation SD ⊆ A × A ist das dazugehörige Semikommutationssystem definiert durch SC = {ab → ba | (a, b) ∉ SD}. Eine Halbspur über (A, SD) ist definiert als die Menge der Wörter [u⟩ = {w ∈ A^{∗} | u ⟹_{SC}^{∗} w}, welche von einem Wort u ∈ A^{∗} durch Anwendung von Ableitungsregeln in SC abgeleitet werden können. Gibt es mehrere Halbabhängigkeitsalphabete (A_{i}, SD_{i}), so werden die zugehörigen Halbspuren [u⟩_{i} ebenfalls indiziert. Es ist leicht zu sehen, daß zwei Halbspuren genau dann gleich sind, wenn sie die gleiche Spur im Monoid M(A, D) mit D = SD ∪ SD^{−1} repräsentieren. Dies legt nahe eine Halbspur [u⟩ über (A, SD) durch den Abhängigkeitsgraphen der Spur [u] in M(A, SD∪SD^{−1}) darzustellen. Zur Darstellung der Halbabhängigkeitsstruktur ersetzen wir jede Kante a → b durch eine gepunktete Kante a [figure] b, wenn (a, b) ∉ SD. Die gepunkteten Kanten nennen wir weiche Kanten. Die anderen Kanten a → b mit (a, b) ∈ SD nennen wir harte Kanten, da sie eine nicht abänderbare Reihenfolge ausdrücken. Ein Semikommutationssystem kann als Graphersetzungssystem betrachtet werden, bei dem eine weiche Kante a [figure] b abgeleitet werden kann zu einer harten Kante a ← b, wobei die Bedingung, daß keine Kreise entstehen, eingehalten werden muß.

Die Hülle einer Sprache L unter einem Semikommutationssystem SC ist die Menge f_{SC}(L) = {w ∈ A^{∗} | ∃u ∈ L, u ⟹_{SC}^{∗} w} der Wörter, welche von einem Wort der Sprache abgeleitet werden können (f_{SC}(w) = f_{SC}({w})). Unter einer Halbspursprache verstehen wir die Hülle f_{SC}(R) einer regulären Sprache R. Ein Semikommutationssystem SC ist die Komposition zweier Semikommutationssysteme SC_{1} und SC_{2}, wenn ∀w f_{SC}(w) = f_{SC_{1}}(f_{SC_{2}}(w)) gilt. Um komplexe Systeme in modularer Weise aufbauen zu können, benötigen wir die Synchronisation von Halbspuren in der gleichen Weise, wie sie von Mazurkiewicz in [Maz87] für die symmetrischen partiellen Kommutationen verwendet werden. Im folgenden werden wir (A, SD) = (⋃_{i} A_{i}, ⋃_{i} SD_{i}) als Synchronisationshalbabhängigkeitsalphabet verwenden. Die Synchronisation von Halbspuren ist

[u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … ∥ [u_{m}⟩_{m} = {w ∈ A^{∗} | ∀0 < i ≤ m Π_{A_{i}}^{A}(w) ∈ [u_{i}⟩_{i}},

wobei Π_{A_{i}}^{A}(w) die Projektion der Wörter w über A_{i} mittels des Homomorphismus Π_{A_{i}}^{A} mit für alle a ∈ A wenn a ∈ A_{i} dann Π_{A_{i}}^{A}(a) = a sonst Π_{A_{i}}^{A}(a) = λ ist. Wir nennen Halbspuren synchronisierbar, wenn ihre Synchronisation nicht die leere Menge ist. Allgemein ist die Synchronisation von Sprachen über dem Alphabet A definiert durch L_{1} ∥ L_{2} ∥ … ∥ L_{m} = {w ∈ A^{∗} | ∀0 < i ≤ m Π_{A_{i}}^{A}(w) ∈ L_{i}}.

Bemerkung: Es ist leicht zu sehen, daß die Synchronisation über einem einzelnen Alphabet gerade der Schnitt ist: Für (A_{1}, SD_{1}) = (A_{2}, SD_{2}) gilt [u⟩_{1} ∥ [v⟩_{2} = [u⟩_{1} ∩ [v⟩_{2}

2.4 Komplexitätsklassen

Bei der Analyse eines Problems genügt es nicht nur festzustellen, ob ein Problem von einem Computer bzw. einer Turingmaschine (siehe [HU79]) entschieden werden kann. In der Komplexitätstheorie untersucht man daher den Platz- und den Zeitbedarf in Abhängigkeit von der Eingabelänge, welche benötigt wird, ein Problem (z.B. die Zugehörigkeit eines Wortes zu einer Sprache) zu lösen und teilt die Probleme (Sprachen) in Komplexitätsklassen ein: DSPACE(S(n)) (bzw. NSPACE(S(n))) ist die Klasse der Sprachen, die von einer deterministischen (bzw. nichtdeterministischen) Turingmaschine erkannt werden, die bei einer Eingabe der Länge n auf jeder Berechnung nur S(n) Platz benötigt. DTIME(T(n)) (bzw. NTIME(T(n))) ist die Klasse der Sprachen, die von einer deterministischen (bzw. nichtdeterministischen Turingmaschine erkannt werden, die bei einer Eingabe der Länge n auf jeder Berechnung nur T(n) Schritte benötigt.

Besondere Komplexitätsklassen sind

\begin{aligned}NLOGSP ACE & := & NSP ACE(log n) \\ P & := & ⋃_{c>1} DT IME(n^{c}) \\ NP & := & ⋃_{c>1} NT IME(n^{c}) \\ P SP ACE & := & ⋃_{c>1} DSP ACE(n^{c}) \\ EXP T IME & := & ⋃_{c>1} DT IME(2^{n^{c}}) \end{aligned}

2.4.1 Reduktion und Orakel

Orakel machen es möglich bei der Lösung eines Problems A ein anderes Problem B als bereits kostenlos gelöst zu betrachten. Eine Möglichkeit, A auf B zu reduzieren, ist die Turingreduktion (A ≤_{T} B), welche von einer Orakelturingmaschine ausgeführt wird, die ein Ausgabeband und einen Fragezustand mit zwei Antwortzuständen besitzt. In welchem der Antwortzustände die Rechnung fortgesetzt wird, wenn die Orakelturingmaschine in den Fragezustand geht, hängt davon ab, ob der Inhalt des Ausgabebandes in der Orakelsprache liegt. Eine Rechnung, die von der Eingabe überprüfen soll, ob sie in A liegt, kann das Orakel B mehrfach benutzen und ist nicht an die Antwort des Orakels gebunden, d.h. sie muß nicht akzeptieren, wenn das gefragte Wort im Orakel liegt. Ist C eine Sprachklasse, so ist C^{A} die Klasse der Sprachen, die mit entsprechenden Orakelmaschinen mit Orakel A berechnet werden können; so ist beispielsweise NP^{A} = {L | L ≤_{T}^{np} A}. Die polynomielle Hierarchie ist als Orakelhierarchie definiert durch Σ_{0}^{P} := P und Σ_{k+1}^{P} := NP^{Σ_{k}^{P}} für k > 0. In dieser Arbeit verwenden wir jedoch nur die many-one-Reduktion, die von einem Transducer durchgeführt wird, der das Orakel nur einmal benutzt; das Ergebnis ist die Antwort des Orakels, d.h. der Inhalt des Ausgabebandes muß genau dann in B sein, wenn die Eingabe in A liegt. Ein logarithmischer Transducer T = (Z, Σ, Γ, Δ, δ, z_{0}, E) ist eine deterministische Turingmaschine mit einem (Zweiweg)Eingabeband mit Eingabealphabet Σ, einem Einwegausgabeband mit Ausgabealphabet Γ, auf das nur geschrieben aber nicht gelesen werden darf, einem logarithmisch platzbeschränkten Arbeitsband mit Bandalphabet Δ, einer Übergangsfunktion δ : (Z × Σ × Δ) ↦ (Z × Δ × Γ^{∗}), einem Anfangszustand z_{0} ∈ Z und den Endzuständen E ⊆ Z. Mit f_{T} (x) bezeichnen wir das Wort, das nach Erreichen eines Endzustandes auf dem Ausgabeband steht. Es gilt L ≤^{log} L′, wenn es einen logarithmischen Transducer T mit x ∈ L gdw. f_{T} (x) ∈ L′ gibt. Ein endlicher Transducer T = (Z, Σ, Γ, δ, z_{0}, E) (gemäß [Ber79] auch rationaler Transducer) ist ein Automat mit einem Einwegeingabeband mit Eingabealphabet Σ, einem Einwegausgabeband mit Ausgabealphabet Γ, einer Übergangsfunktion δ : (Z ×Σ) ↦ (Z ×Γ^{∗}) (bzw. einer Übergangsrelation δ ⊂ (Z ×Σ)×(Z ×Γ^{∗}), falls T nichtdeterministisch ist), einem Anfangszustand z_{0} ∈ Z und den Endzuständen E ⊆ Z. Für einen deterministischen Transducer T ist f_{T} (x) ∈ Γ^{∗} das Wort, das nach Durchlaufen der Eingabe x ∈ Σ^{∗} auf dem Eingabeband auf dem Ausgabeband steht, wenn ein Endzustand erreicht wurde. Bei einem nichtdeterministischen Transducer ist f_{T} eine reguläre Relation (auch rationale Relation), d.h. sie kann von einem nichtdeterministischen endlichen Automaten mit zwei Eingabebändern erkannt werden. Es gilt L ≤^{f} L′ (L ≤^{nf} L′), wenn es einen deterministischen (nichtdeterministischen) endlichen Transducer T mit Einwegeingabeband und Einwegausgabeband gibt mit x ∈ L gdw. es einen Ausgabewert f_{T} (x) ∈ L′ gibt (∃y ∈ L′ und (x, y) ∈ f_{T}). Für eine Sprachklasse S ist

\begin{aligned}LOG(S) & := & \{Y | ∃X ∈ S mit Y ≤^{log} X\}, \\ co−S & := & \{Y | \overline{Y} ∈ S\}, \end{aligned}

eine Sprache V heißt vollständig für S bezüglich einer Reduktion ’≤’, wenn V ∈ S und ∀X ∈ S X ≤ V gilt. Eine Sprachklasse S ist abgeschlossen bezüglich einer Reduktion ’≤’, wenn für alle L ≤ L′ ∈ S auch L ∈ S liegt. Eine Sprachklasse S ist eine abstrakte Familie von Sprachen^{1} (AFL), wenn S unter Vereinigung, Konkatenation, dem Sternoperator und rationaler Transduktion (≤^{nf}) abgeschlossen ist. Beispielsweise ist die Klasse CFL der kontextfreien Sprachen eine AFL. Eine Äquivalenzrelation δ über Σ^{∗} ist eine Kongruenz, wenn für alle w, x, y, z ∈ Σ^{∗} mit [w]_{δ} = [x]_{δ} und [y]_{δ} = [z]_{δ} auch [wy]_{δ} = [xz]_{δ} gilt. Die Semi-Dyck-Sprache D′_{n}^{∗} über dem Alphabet {a_{1}, ...a_{n}, b_{1}, ..., b_{n}} ist die Sprache der Wörter, die kongruent mit dem leeren Wort λ sind bezüglich der Kongruenz δ′ mit [a_{i}b_{i}]_{δ′} = [λ]_{δ′} für alle i ≤ n. Die Semi-Dyck-Sprache

D′_{n}^{∗} := {w ∈ {a_{1}, ...a_{n}, b_{1}, ..., b_{n}} | [w]_{δ′} = [λ]_{δ′}}

kann auch als Klammersprache bezeichnet werden, wobei a_{i} eine öffnende Klammer und b_{i} die dazugehörige schließende Klammer ist. Für n > 1 ist D′_{n}^{∗} vollständig für die Klasse CFL bezüglich rationaler Transduktion. Die Sprache D′_{1}^{∗} ist hingegen nur vollständig bezüglich rationaler Transduktion für die Klasse ROCL (siehe [Ber79]) der Sprachen, die von einem Automaten mit einem schwachen Zähler erkannt werden können. Die Sprache (D′_{1}^{∗}c)^{∗} ist vollständig bezüglich rationaler Transduktion für die Klasse OCL (siehe [Ber79]) der Sprachen, die von einem Automaten mit einem starken Zähler erkannt werden können und die Sprache {w$w^{R} | w ∈ {a, b}^{∗}}^{∗} ist vollständig bezüglich rationaler Transduktion für die Klasse LIN der linearen Sprachen.

1Eine genauere Bezeichnung ist ’volle abstrakte Familie von Sprachen’. Nicht volle AFL’s, bei denen die rationalen Transduktionen nicht löschend sein dürfen, kommen in dieser Arbeit nicht vor.

2.4.2 Schaltkreiskomplexitätsklassen

Unterhalb von P wurden viele Komplexitätsklassen mit verschiedenen Arten von parallelen Random Access Maschinen, verschiedenen Arten von Schaltkreisen, verschiedenen sequenziellen Modellen mit unterschiedlichen Akzeptanzbedingungen z.B. Alternierung oder Zählkomplexitätsklassen und die logarithmische Hülle über formalen Sprachklassen z.B. LOG(CF L) betrachtet und viele Beziehungen zwischen diesen Modellen gefunden (siehe z.B. [LR94], [LR90], [Par90], [Rei92a], [Rei90], [SV84], usw.). Von Interesse ist in dieser Arbeit die Klasse T C^{0}, in der diejenigen Sprachen liegen, welche von einer uniformen Familie von Schaltkreisen aus Threshold-Gattern mit konstanter Tiefe und polynomieller Größe erkannt werden können, d.h. für jede Eingabelänge existiert ein Schaltkreis in dieser Familie mit der Eigenschaft, daß für alle Eingaben dieser Länge der Ausgang des Schaltkreises genau dann 1 ist, wenn die Eingabe in der Sprache liegt. Als Uniformitätsbedingung verwenden wir die DLOGTIME-Uniformität [BIS90]; dies bedeutet, daß die Schaltkreise einer solchen Familie durch Ausdrücke beschrieben werden und die Sprache dieser Ausdrücke

{⟨c, i, y⟩ | |y| = n und das i-te Zeichen des n-ten Ausdrucks ist c}

von einer deterministischen logarithmisch zeitbeschränkten Turingmaschine erkannt werden kann. Threshold-Schaltkreise sind auch ein Modell für neuronale Netze. In T C^{0} liegen genau diejenigen Sprachen, welche von einer parallelen Random Access Maschine, welche zusätzlich über die Majoritätsfunktion verfügt, in konstanter Zeit berechnet werden kann [Par90]. Nach [BIS90] ist T C^{0} die Klasse der Sprachen, die durch Logik erster Stufe mit zusätzlichem Mayoritätsquantor (FO+MAJ) beschrieben werden können. NC^{k} (AC^{k}) ist die Klasse der Sprachen, die von einer uniformen Familie von Schaltkreisen aus ∧, ∨ und ¬ -Gattern mit der Tiefe O(log^{k}n) und polynomieller Größe mit beschränktem (bzw. unberschränktem) Fan-In erkannt werden können [Ruz81]. Die Probleme in NC = ⋃_{k} NC^{k} betrachtet man häufig als die effizient parallelisierbaren Probleme. Zwar ist nicht bekannt, ob die Klassen sich trennen lassen (z.B. ist nicht bekannt ob T C^{0} ≠ NP), es wird jedoch angenommen, daß viele dieser Klassen verschieden sind, was eine genaue Einteilung von Problemen in diese Klassen interessant macht.

2.5 Petrinetze mit inhibitorischen Kanten

Üblicherweise bedeutet eine positiv gewichtete Kante von einer Stelle zu einer Transition in einem Petrinetz, daß die Transition nur dann schalten darf, wenn genügend Marken auf der Stelle liegen. Im Gegensatz dazu bedeutet eine inhibitorische Kante, daß die Transition nur dann schalten darf, wenn keine Marke auf der Stelle liegt. Ein solches Petrinetz beschreiben wir durch ein 6-Tupel (S, T, W, I, m_{0}, m_{e}) mit der Gewichtsfunktion W ∈ ℕ^{S×T ∪T ×S}, den inhibitorischen Kanten I ⊆ S ×T und den Anfangs- und Endmarkierungen m_{0}, m_{e} ∈ ℕ^{S}. Die inhibitorischen Kanten werden wir in den Bildern durch ————• darstellen. Eine Transition t ∈ T kann eine Markierung m zu der Markierung m′ schalten, d.h. m[t⟩m′, wenn m − W (., t) = m′ − W (t, .) ∈ ℕ^{S} und ∀s ∈ S (s, t) ∈ I → m(s) = 0. Eine Transitionsfolge w = t_{1}...t_{n} ∈ T^{∗} kann m_{0} nach m_{n} schalten, d.h. m_{0}[w⟩m_{n}, wenn m_{1}, ...m_{n−1} existieren mit m_{0}[t_{1}⟩m_{1}[t_{2}⟩...[t_{n}⟩m_{n}. Das Erreichbarkeitsproblem für ein Petrinetz (S, T, W, I, m_{0}, m_{e}) ist es, zu entscheiden, ob ein w ∈ T^{∗} existiert mit m_{0}[w⟩m_{e}. Existieren s, s′ ∈ S und t, t′ ∈ T mit den inhibitorischen Kanten (s, t), (s′, t′) ∈ I, welche unabhängig liegen, d.h. es gilt (s, t′), (s′, t) ∉ I, so wird das Erreichbarkeitsproblem i.a. unentscheidbar. Ist dies jedoch nicht der Fall, so gilt für alle s, s′ ∈ S und t, t′ ∈ T mit (s, t), (s′, t′) ∈ I die Bedingung (s, t′) ∈ I oder (s′, t) ∈ I. D.h. für alle s, s′ ∈ S gilt

T (s) := {t | (s, t) ∉ I} ⊆ T (s′) := {t | (s′, t) ∉ I} oder T (s) ⊇ T (s′).

Also lassen sich die Stellen mit dieser Teilmengenbeziehung linear anordnen und zwar so, daß jede Stelle zu all denjenigen Transitionen eine inhibitorische Kante hat, zu denen eine bezüglich der Anordnung größere Stelle eine inhibitorische Kante hat. Diese Ordnung wird in [Rei94] beim Übergang von Petrinetzen mit inhibitorischen Kanten zu geschachtelten Petrinetzen ausgenutzt um die Entscheidbarkeit in diesem Fall zu zeigen.

2.6 Multimengen und Vektoren

Für zwei Mengen A, B ist A^{B} die Menge der Funktionen f : B ↦ A von B nach A. Eine solche Funktion mit f(b_{1}) = a_{1}, f(b_{2}) = a_{2}, ... läßt sich darstellen als

Menge {b_{1} ↦ a_{1}, b_{2} ↦ a_{2}, ...} oder als B-Vektor ( a_{1} ; a_{2} ; ⋮ ). Eine Multimenge über

B ist eine Funktion in ℕ^{B}. Eine Funktion, die auf Multimengen abbildet f : A ↦ ℕ^{B} betrachten wir als Multimenge in ℕ^{B×A} mit f(b, a) = f(a)(b), f(., a) = f(a) und f(b, .) = {a ↦ f(b, a) | a ∈ A} oder als B × A-Matrix. Ist A ⊆ B so gilt ℕ^{A} ⊆ ℕ^{B}, wobei wir eine Funktion an nicht definierten Stellen als um 0 erweitert denken. Es gilt ℕ^{A} ∩ ℕ^{B} = ℕ^{A∩B}. Die Einschränkung einer Multimenge f ∈ ℕ^{B} auf A ist f |_{A}:= {b ↦ n | b ∈ A ∧ f(b) = n}. Dies bedeutet, daß für alle f und A die 3 Aussagen f ∈ ℕ^{A}, f |_{A}= f und ∀x ∉ A f(x) = 0 äquivalent sind. Die Addition zweier Multimengen f, g ∈ ℕ^{A} erklärt sich durch (f +g)(a) = f(a)+ g(a) und die Skalarmultiplikation mit n ∈ ℕ durch (fn)(a) = (nf)(a) = nf(a).

Sei M ⊆ ℕ^{A} eine endliche Menge von Multimengen, so ist die Identitätsfunktion id_{M} ∈ M^{M} ⊆ ℕ^{A×M} mit ∀m ∈ M id_{M}(., m) = id_{M}(m) := m eine A × M-Matrix, bei der ein Spaltenvektor bei einer Position für ein m ∈ M der A-Vektor m selbst ist. Sei f ∈ ℕ^{M} eine Multimenge von Multimengen. Entsprechend der Multiplikation der Matrix id_{M} mit einem M-Vektor f ∈ ℕ^{M} definieren wir

M · f := id_{M} · f = Σ_{m∈M} mf(m) ∈ ℕ^{A}.

Diese Multiplikation M · f := Σ_{m∈M} mf(m) wird später bei der geschachtelten

Beschreibung von Schaltfolgen wichtig. Ist f ∈ ℕ^{M′} mit M ⊆ M′, so ist M · f := M · (f |_{M}).

Sei z.B. M := \{\{a_{1} ↦ 3, a_{2} ↦ 2\}, \{a_{1} ↦ 1, a_{2} ↦ 5\}\} = \{( \begin{matrix}3 \\ 2 \end{matrix} ), ( \begin{matrix}1 \\ 5 \end{matrix} )\} und f := \{( \begin{matrix}3 \\ 2 \end{matrix} ) ↦

4, ( \begin{matrix}1 \\ 5 \end{matrix} ) ↦ 7\}, so ist M · f = ( \begin{matrix}3 1 \\ 2 5 \end{matrix} ) · ( \begin{matrix}4 \\ 7 \end{matrix} ) = ( \begin{matrix}19 \\ 43 \end{matrix} ) =

{a_{1} ↦ 19, a_{2} ↦ 43}. Für eine endliche Menge M von Multimengen ist M^{∗} := {M · f | f ∈ ℕ^{M}} die Menge aller Linearkombinationen.

2.7 Geschachtelte Petrinetze

Die Idee eines geschachtelten Petrinetzes ist, daß eine Transition selbst eine Kette (als Liste zwischen [ und ] dargestellt) hintereinandergeschalteter Unternetze mit inneren Stellen ist, welche vor und nach dem Schalten dieser Transition frei von Marken sein müssen. Wesentlicher Unterschied zu den Netzsystemen in [Kie89] ist dabei, daß Marken auf äußeren Stellen mit in die Unternetze genommen und und übrige Marken auf diesen Stellen wieder nach außen genommen werden können. (Dies läßt sich mit der Verwendung globaler Variablen in Unterprogrammen vergleichen.) Die Kantengewichte (welche zuvor mit W bezeichnet wurden) sind nun keine festgelegten Größen außerhalb der Transitionen, sondern sie werden im Innern einer Transition bestimmt. Zu diesem Zweck enthält jede Transition eine semilineare Menge von Multimengen, durch welche der benötigte Zusammenhang von äußerem Schaltverhalten und der inneren Schaltbedingung hergestellt wird. Zusätzlich übernimmt diese semilineare Menge die Aufgabe die Schaltfolgen zu restringieren. Eine Darstellung als Vektoren (wie sie bei einer hypothetischen Implementation gebraucht würde) brächte einen erheblichen formalen Aufwand zur Berechnung der jeweils benötigten Koordinaten mit sich. Aus diesem Grund wurde die Schreibweise als Multimenge gegenüber der Darstellung als Vektor bevorzugt.

Definition Ein geschachteltes Petrinetz (S_{T} , T) besteht aus einer Menge T von Transitionen, welche im eigentlichen Sinne Transitionsketten sind, und den Stellen S_{T}. Dabei gilt:

(1) Eine Elementartransition hat die Form t = ([ ], c, P) mit der leeren Liste [ ] von Unternetzen, der Konstantenmultimenge c ∈ ℕ^{S_{T} ×{0,1}}, welche festlegt, wieviele Marken mindestens von den Stellen abgezogen werden und auf die Stellen gelegt werden müssen, und den linear unabhängigen (und endlich vielen) Periodenmultimengen

P ⊆ {p ∈ ℕ^{S_{T} ×{0,1}} | p(0) = p(1)},

welche beschreiben, wieviele Marken zusätzlich abgezogen und wieder aufgelegt werden können. (Bei einer Elementartransition muß dieser Zusatz jeweils gleich sein, damit das Schaltverhalten nur durch c bestimmt ist. Prinzipiell genügt für eine Elementartransition auch P = ∅.)

(2) Das Schaltverhalten einer Elementartransition: Die Multimengen m_{0}, m_{1} ∈ ℕ^{S_{T}} seien Markierungen; es sei c ∉ P (man denke sich c als markiert). Die Elementartransition t kann mittels eines Pfades f ∈ ℕ^{{c}∪P} mit f(c) = 1 von der Markierung m_{0} zu der Markierung m_{1} schalten, d.h. m_{0}[t⟩m_{1} mittels f, wenn p := ({c}∪P)·f = c+P ·f und m_{0}−p(0) = m_{1}−p(1) ∈ ℕ^{S_{T}}. (Es scheint hier überflüssig zu sein, daß die Markierungen vor und nach dem Schalten sowohl durch einen größeren Pfad f als auch durch eine größere Differenz m_{0}−p(0) erhöht werden können, doch wir werden im Beispiel 3 Seiten weiter sehen, daß im allgemeinen Fall beides separat möglich sein muß.) Der Pfad f bescheibt also mit Hilfe der in Unterkapitel 2.6 beschriebenen Multiplikation, wie oft die Transition schaltet (in diesem Fall gerade f(c) = 1 mal) und von jeder Periode, wie oft sie hinzukommt.

(3) Schaltfolgen: Für ein Netz (S, T) mit S = S_{T} ist Q := ⋃_{(K,c,P)∈T}{c}∪P die disjunkte Vereinigung

aller Mengen von Konstanten- und Periodenmultimengen, die die Transitionen in T beschreiben (man denke sich die Multimengen in {c} ∪ P mit t = (K, c, P) ∈ T mit t markiert). Eine Transitionsfolge w = t_{1}...t_{n} ∈ T^{∗} kann nun mittels eines Pfades f ∈ ℕ^{Q} von der Markierung m_{0} ∈ ℕ^{S} zu der Markierung m_{n} ∈ ℕ^{S} schalten, d.h. m_{0}[w⟩m_{n} mittels f, wenn der Pfad in einzelne Schaltvorgänge zerlegt werden kann, d.h. wenn

∃m_{1}, ...m_{n−1} ∈ ℕ^{S}, f_{1}, ...f_{n} ∈ ℕ^{Q} f = Σ_{i=1}^{n} f_{i} ∧ ∀1 ≤ i ≤ n m_{i−1}[t_{i}⟩m_{i} mittels f_{i}.

(Dies gilt ungeachtet dessen, ob die t_{i} Elementartransitionen oder ’komplexe’ Transitionen sind.)

(4) Im allgemeinen Fall hat eine ’komplexe’ Transition n Netze (S_{i}, T_{i}) mit mindestens so vielen Stellen wie außen, d.h.

∀1 ≤ i ≤ n S_{T_{i}} = S_{i} ⊇ S_{T} ,

als Unternetze. Diese Transition hat die Form t = ([(S_{1}, T_{1})...(S_{n}, T_{n})], c, P) mit

{c} ∪ P ⊆ ℕ^{S_{T} ×{0,1}∪ ⋃_{i=1}^{n}(S_{i}×{2i,2i+1}∪Q_{i}×{−i})}

mit Q_{i} := ⋃_{(K′,c′,P′)∈T_{i}}{c′} ∪ P′ und

∀p ∈ P p(0) = p(2) ∧ p(2n + 1) = p(1) ∧ ∀2 ≤ i ≤ n p(2i − 1) = p(2i).

(Wegen p(2i) ∈ ℕ^{S_{i}} und p(2i−1) ∈ ℕ^{S_{i−1}} für 2 ≤ i ≤ n bedeutet p(2i−1) = p(2i), daß der Wert p(s, 2i−1) = p(s, 2i) ∈ ℕ^{S_{i−1}∩S_{i}} liegt, also für s ∈ S_{i−1}\S_{i}∪S_{i}\S_{i−1} gleich 0 ist.) Eine Multimenge in c + P^{∗} beschreibt somit, wieviele Marken die Transition insgesamt zu Beginn ihres Schaltens abzieht (markiert mit 0), wieviele sie zu Beendigung ihres Schaltens auflegt (markiert mit 1) und für jedes Unternetz (S_{i}, T_{i}), wieviele Marken zu Beginn einer Schaltfolge des Unternetzes zur Verfügung gestellt werden (markiert mit 2i), wieviele Marken genau beim Ende einer Schaltfolge des Unternetzes wieder vorhanden sein müssen (markiert mit 2i + 1) und den Pfad, der die Schaltfolge des Unternetzes quantitativ beschreibt (markiert mit −i). Dabei darf wiederum die Differenz der Marken am Ende eines Unternetzes zu den Marken am Anfang des folgenden Unternetzes nicht durch Erhöhen einer Periode verändert werden; dies wird durch p(2i − 1) = p(2i) ausgedrückt. Gleiches gilt für die Differenz der Marken, welche die Transition insgesamt zu Beginn ihres Schaltens abzieht, zu den Marken am Anfang des ersten Unternetzes (p(0) = p(2)) und die Differenz der Marken, welche die Transition insgesamt zu Beendigung ihres Schaltens auflegt, zu den Marken am Ende des letzten Unternetzes (p(2n + 1) = p(1)). Die Periodenmultimengen in P sind linear unabhängig, somit ist die Darstellung eines p ∈ c + P^{∗} eindeutig und f mit p = ({c} ∪ P) · f = c + P · f ist eindeutig festgelegt.

(5) Die Transition t kann mittels eines Pfades f ∈ ℕ^{{c}∪P} mit f(c) = 1 von der Markierung m_{0} zu der Markierung m_{1} schalten, d.h. m_{0}[t⟩m_{1} mittels f, wenn p := ({c} ∪ P) · f = c + P · f, m_{0} − p(0) = m_{1} − p(1) ∈ ℕ^{S_{T}} und

∀1 ≤ i ≤ n ∃w_{i} ∈ T_{i}^{∗} p(2i)[w_{i}⟩p(2i + 1) mittels p(−i).

Die Menge c+P^{∗} dient sowohl der Restriktion von möglichen Schaltfolgen in Unternetzen, als auch der Spezifikation der (nicht explizit genannten) Zwischenübergänge von ℕ^{S_{T}} nach ℕ^{S_{1}}, von ℕ^{S_{i}} nach ℕ^{S_{i+1}} und von ℕ^{S_{n}} nach ℕ^{S_{T}}. p(−i) ist die Summe der Pfade im i-ten Unternetz; f beschreibt also durch rekursive Anwendung der in Unterkapitel 2.6 beschriebenen Multiplikation die Summe der Pfade in jeder Unternetzebene. Da gleichzeitiges Vergrößern von m_{0} und m_{1} die Differenz m_{0} − p(0) = m_{1} − p(1) positiv läßt und die innere Schaltbedingung nicht verändert, gilt die Monotonie.

(6) Kommt eine Stelle vor und nach einem solchen Zwischenübergang in t vor, so ist sie dort als frei zu bezeichnen: ∀0 < i < n F_{2i+1} := F_{2i+2} := S_{i} ∩ S_{i+1}. Die Menge der freien Stellen F_{2} am Anfang des ersten Unternetzes und und F_{2n+1} am Ende des letzten Unternetzes sind, falls sie nicht anders festgelegt werden, definiert durch F_{2} := S_{T} ∩ S_{1} und F_{2n+1} := S_{n} ∩ S_{T}. Stellen in \overline{F_{2i}} := S_{i} \ F_{2i} bzw. \overline{F_{2i+1}} := S_{i} \ F_{2i+1} sind dagegen fest spezifiziert.

(7) Die erweiterte Erreichbarkeitsmenge für eine Transition t ist

ER_{t} := {(m_{0}, m_{1}, f) | m_{0}[t⟩m_{1} mittels f}.

Die Erreichbarkeitsmenge R_{t} := {(m_{0}, m_{1}) | ∃f m_{0}[t⟩m_{1} mittels f} und die Pfadmenge

E_{t} := {f | ∃m_{0}, m_{1} m_{0}[t⟩m_{1} mittels f}

sind Projektionen von ER_{t}. Für eine Menge T gilt entsprechend ER_{T} := ⋃_{t∈T} ER_{t}

analog dazu E_{T}, R_{T} und für ein Netz (S, T) ist entsprechend [Hau90]

ER_{(S,T)} := {(m_{0}, m_{1}, f) | ∃w ∈ T^{∗} m_{0}[w⟩m_{1} mittels f}

und E_{(S,T)} := {f | ∃w ∈ T^{∗} ∃m_{0}, m_{1} m_{0}[w⟩m_{1} mittels f} ⊇ E_{T}. Es gilt also ER_{(K,c,P)} =

{(m_{0}, m_{1}, f) | f(c) = 1 und für p mit p = ({c} ∪ P) · f = c + P · f gilt
m_{0} − p(0) = m_{1} − p(1) ≥ ∅ ∧
∀(S_{i}, T_{i}) ∈ K (p(2i), p(2i + 1), p(−i)) ∈ ER_{(S_{i},T_{i})} }

und E_{(K,c,P)} =

{f | f(c) = 1 und für p mit p = ({c} ∪ P) · f = c + P · f gilt
∀(S_{i}, T_{i}) ∈ K (p(2i), p(2i + 1), p(−i)) ∈ ER_{(S_{i},T_{i})} }.

(8) Zwei Transitionsmengen T, T′ heißen erreichbarkeitsäquivalent, wenn R_{T} = R_{T′}.

(9) Das Schaltbarkeitsproblem für eine Transitionenmenge T ist zu entscheiden, ob R_{T} nicht leer ist.

Beispiel: Sei S_{T} = {s_{1}} und T = {t} bestehend aus der in folgendem Bild mit s_{1} dargestellten Transition t = ([({s_{1}, s_{2}, s_{3}}, {t_{1}, t_{2}})({s_{1}, s_{3}}, {t_{3}})], c, P) spezifiziet

durch c(0) = (1), c(1) = (2), c(2) = ( \begin{matrix}2 \\ 0 \\ 0 \end{matrix} ), c(3) = ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ), c(4) = ( \begin{matrix}0 \\ 3 \end{matrix} ), c(5) = ( \begin{matrix}1 \\ 1 \end{matrix} ) und

c(c_{1}, −1) = c(c_{2}, −1) = c(c_{3}, −2) = c(p_{10}, −2) = c(p_{11}, −2) = 0. Die Transitionen in den Unternetzen t_{1} = ([ ], c_{1}, {}), t_{2} = ([ ], c_{2}, {}), t_{3} = ([ ], c_{3}, {p_{10}, p_{11}}) sind

spezifiziert durch c_{1} = ( \begin{matrix}1 0 \\ 0 2 \\ 0 0 \end{matrix} ), c_{2} = ( \begin{matrix}0 0 \\ 1 0 \\ 0 1 \end{matrix} ) und c_{3} = ( \begin{matrix}0 2 \\ 1 0 \end{matrix} ).

[figure: s_{1}; s_{1}; s_{2}; t_{1}; s_{3}; t_{2}; s_{3}; s_{1}; t_{3}; 2; 2; 3; 2; 2; =; =]

Deren Periodenvektoren p_{10} = ( \begin{matrix}1 1 \\ 0 0 \end{matrix} ), p_{11} = ( \begin{matrix}0 0 \\ 1 1 \end{matrix} ) von t_{3} und die Periodenvekto-

ren P = {p_{1}...p_{9}} von t mit p_{1} = {(s_{1}, 0) ↦ 1, (s_{1}, 2) ↦ 1}, p_{2} = {(s_{1}, 5) ↦ 1, (s_{1}, 1) ↦ 1}, p_{3} = {(s_{1}, 3) ↦ 1, (s_{1}, 4) ↦ 1}, p_{4} = {(s_{3}, 3) ↦ 1, (s_{3}, 4) ↦ 1}, p_{5} = {(c_{1}, −1) ↦ 1}, p_{6} = {(c_{2}, −1) ↦ 1}, p_{7} = {(c_{3}, −2) ↦ 1}, p_{8} = {(p_{10}, −2) ↦ 1}, p_{9} = {(p_{11}, −2) ↦ 1} gehen nicht in die bildliche Darstellung ein und sind bei diesem Beispiel so gewählt, daß die Schaltfolgen nicht durch sie restringiert werden. Ein Schaltvorgang wird in der Reihenfolge von links nach rechts interpretiert. Es gilt z.B. (1)[t⟩(8) mittels {c ↦ 1, p_{1} ↦ 0, p_{2} ↦ 6, p_{3} ↦ 1, p_{4} ↦ 1, p_{5} ↦ 1, p_{6} ↦ 2, p_{7} ↦ 3, p_{8} ↦ 0, p_{9} ↦ 0} = (1, 0, 6, 1, 1, 1, 2, 3, 0, 0) mit der folgenden Interpretation:

Zu Beginn zieht t eine Marke von s_{1} ab und stellt 2 Marken auf s_{1} im ersten Unternetz zur Verfügung. Einmaliges Schalten (p_{5} ↦ 1) von t_{1} zieht eine dieser Marken ab und legt 2 Marken auf s_{2}. Zweimaliges Schalten von t_{2} (p_{6} ↦ 1) bewegt diese beiden Marken nach s_{3}, wovon eine gefordert wird und die andere zusätzlich ist (p_{4} ↦ 1). Die übrige Marke auf s_{1} ist ebenfalls zusätzlich (p_{3} ↦ 1). (Auf s_{2} darf ohnehin keine zusätliche Marke bleiben.) Im zweiten Unternetz stehen nun 4 Marken auf s_{3} zu Verfügung (eine davon ist zusätzlich). Da genau eine dieser Marken übrig bleiben muß, schaltet t_{3} drei mal (p_{7} ↦ 3) und legt dabei 6 Marken zu der einen hinzu. Zuletzt legt t 8 Marken (2 obligatorische und 6 zusätzliche wegen p_{2} ↦ 6) auf s_{1} ab.

Der Schaltvorgang (1)[t⟩(8) kann aber auch mittels (1, 0, 6, 1, 1, 1, 2, 3, 9, 5) stattfinden, wobei lediglich zwischendurch mehr abgezogen und wieder aufgelegt wird, was sich wieder ausgleicht. Auch kann (2)[t⟩(9) mittels (1, 0, 6, 1, 1, 1, 2, 3, 0, 0) oder auch mittels (1, 1, 7, 2, 1, 1, 2, 3, 12, 5), hierbei ist die Erhöhung der Perioden p_{1}, p_{2}, p_{3}, p_{8} und p_{9} freiwillig. (2)[t⟩(15) kann mittels (1, 1, 13, 0, 5, 3, 6, 7, 0, 0) schalten, hierbei ist die Erhöhung der Perioden p_{1} und p_{2} erzwungen. Durch zweimaliges Schalten könnte z.B. auch (1)[tt⟩(15) mittels (2, 0, 12, 2, 2, 2, 4, 6, 25, 10) gelten. Wir verwenden die folgenden Ergebnisse aus [Rei94]:

Theorem 2.1 Zu jeder Transitionenmenge T kann effektiv ein erreichbarkeitsäquivalentes T′ konstruiert werden mit der Eigenschaft, daß für alle Transitionen t = (K, c, P) ∈ T′ die folgenden 6 Bedingungen gelten:

1. Für alle (S_{i}, T_{i}) ∈ K hat T_{i} selbige Eigenschaft, d.h. die Eigenschaft ist rekursiv über der Schachtelungsstruktur.

2. ∀(S_{i}, T_{i}) ∈ K ∀p ∈ {c} ∪ P p(2i) − (Q_{i} · (p(−i)))(0) = p(2i + 1) − (Q_{i} · (p(−i)))(1), d.h. für jeden Periodenvektor stimmt in jedem Unternetz die Differenz der Markierungen an Anfang und Ende mit der Differenz der Markierungen, die durch den Pfad im Unternetz entstehen, überein.

3. ∀(S_{i}, T_{i}) ∈ K ∀s ∈ F_{2i} Σ_{p∈P} p(s, 2i) ≥ 1 ∧ ∀s ∈ F_{2i+1} Σ_{p∈P} p(s, 2i + 1) ≥ 1,

d.h. freie Stellen können beliebig erhöht werden.

4. ∀(S_{i}, T_{i}) ∈ K ∀q ∈ Q_{i} Σ_{p∈P} p(q, −i) ≥ 1, d.h. alle Durchläufe durch Tran-

sitionen und alle Perioden in Unternetzen können beliebig oft verwendet werden.

5. ∀(S_{i}, T_{i}) ∈ K ∃(x_{i}, x_{i} + Δ_{i}, α_{i}), (x′_{i} + Δ′_{i}, x′_{i}, α′_{i}) ∈ ER_{(S_{i},T_{i})} mit ∀s ∈ \overline{F_{2i}} Δ_{i}(s) ≥ 1 ∧ x_{i}(s) ≤ c(s, 2i)∧

∀s ∈ \overline{F_{2i+1}} Δ′_{i}(s) ≥ 1 ∧ x′_{i}(s) ≤ c(s, 2i + 1),

d.h. falls die freien Stellen genügend hoch sind, so gibt es eine Schaltfolge, bei der die nicht freien Stellen erhöht, bzw. verkleinert werden.

6. {c ↦ 1} ∈ E_{t}, d.h. c selbst beschreibt schon eine erlaubte Schaltfolge. (Darüber hinaus gibt es gemäß Lemma 2.1 beliebig hohe Pfade in t, d.h. es gilt ∀g ∈ ℕ^{P} ∃f′ ∈ ℕ^{P} f′ ≥ g ∧ {c ↦ 1} + f′ ∈ E_{t}.)

Korollar 2.1 [Rei94] Das Schaltbarkeitsproblem für geschachtelte Petrinetze ist entscheidbar.

Lemma 2.1 [Rei94] Unter der Voraussetzung, daß die Bedingungen 1 bis 5 für t = (K, c, P) gelten, gilt:

∀f ∈ ℕ_{+}^{P}, g ∈ ℤ^{P} ∃k ≥ 2 {c ↦ 1} + kf, {c ↦ 1} + kf + g ∈ E_{t}

Die Bedingung sagt, daß jede Pfaddifferenz g durch eine andere Pfaddifferenz f ausgeglichen werden kann, wenn man diese nur oft genug anwendet und dabei alle Perioden beliebig erhöhen kann.

Wenn die inhibitorischen Kanten so liegen, daß sich die Stellen so anordnen lassen, daß jede Stelle zu all denjenigen Transitionen eine inhibitorische Kante hat, zu denen eine bezüglich der Anordnung größere Stelle eine inhibitorische Kante hat, dann kann dazu ein Menge von geschachtelten Transitionen T′ konstruiert werden für die R_{T′} genau dann nicht leer ist, wenn ein w ∈ T^{∗} existiert mit m_{0}[w⟩m_{e}. Damit kann das Erreichbarkeitsproblem für (S, T, W, I, m_{0}, m_{e}) mit Hilfe von Korollar 2.1 entscheiden werden.

Theorem 2.2 [Rei94] Gilt für ein Petrinetz (S, T, W, I, m_{0}, m_{e}) die Bedingung

∃g ∈ ℕ_{+}^{S} ∀s, s′ ∈ S g(s) ≤ g(s′) → (∀t ∈ T (s′, t) ∈ I → (s, t) ∈ I),

so ist das Erreichbarkeitsproblem für (S, T, W, I, m_{0}, m_{e}) entscheidbar.

3 Prioritätsmulticounterautomaten

In diesem Kapitel wird beschrieben, für welche Art von Counterautomaten entscheidbar ist, ob die von einem gegeben Counterautomaten akzeptierte Sprache leer ist. Bekannt ist die Entscheidbarkeit der Erreichbarkeit einer akzeptierenden Konfiguration, falls die Leerheit bei keinem Zähler unterschieden werden kann (man bezeichnet diese als schwache Zähler). In diesem Fall ist sie äquivalent zum Erreichbarkeitsproblem in Petrinetzen bzw. in Vektoradditionssystemen ([May84], [Kos84]). Man kann leicht sehen, daß das Ereichbarkeitsproblem unentscheidbar wird, wenn man die Leerheit für zwei Zähler testen kann, da nun ein wiederholtes, kontrolliertes ’Umschaufeln’ zwischen diesen beiden Zählern möglich wird. Mit dieser Methode kann eine Turingmaschine simuliert und damit das Halteproblem auf das Erreichbarkeitsproblem reduziert werden (siehe [Min71]). Multicountersprachen (Sprachen die von Multicounterautomaten erkannt werden) mit keinem oder nur einem Nulltest bilden keine AFL (abstrakte Familie von Sprachen), da sie nicht unter Sternbildung abgeschlossen sind. Mit der folgenden Verallgemeinerung wird jedoch eine AFL gebildet: Außer dem Nulltest von Zähler 1 kann auch, falls Zähler 1 Null ist, Zähler 2 auf Leerheit getestet werden oder allgemein, falls die Zähler 1 bis k −1 den Wert Null haben, kann Zähler k auf Leerheit getestet werden. Kontrolliertes ’Umschaufeln’ wird dabei nur in einer Richtung möglich. Formal läßt sich dies wie folgt fassen:

Definition Ein Prioritätsmulticounterautomat ist ein Einwegautomat beschrieben durch ein 6-Tupel

A = (k, Z, Σ, δ, z_{0}, E)

mit Zustandsmenge Z, Eingabealphabet Σ, Übergangsrelation

δ ⊆ (Z × (Σ ∪ {λ}) × {0 … k}) × (Z × {−1, 0, 1}^{k}),

Anfangszustand z_{0}, akzeptierende Zustände E ⊆ Z, Konfigurationenmenge C_{A} = Z × Σ^{∗} × ℕ^{k}, Anfangskonfiguration σ_{A}(x) = ⟨z_{0}, x, 0^{k}⟩ und Konfigurationsübergangsrelation

⟨z, ax, n_{1}, ..., n_{k}⟩ |_{\overline{A}} ⟨z′, x, n_{1} + i_{1}, ..., n_{k} + i_{k}⟩

gdw. z, z′ ∈ Z, a ∈ Σ ∪ {λ}, ⟨(z, a, j), (z′, i_{1}, ...i_{k})⟩ ∈ δ, ∀i ≤ j n_{i} = 0 (und n_{j+1} > 0 oder j = k)^{2}.

2Automaten gemäß der Definition mit bzw. ohne diesen Zusatz lassen sich leicht ineinander überführen

Bemerkung: Die von dem Prioritätsmulticounterautomaten A erkannte Sprache ist L(A) = \{w | ∃z_{e} ∈ Z ∃n_{1}, ..., n_{k} ∈ ℕ ⟨z_{0}, w, 0, ..., 0⟩ |\frac{∗}{A} ⟨z_{e}, λ, n_{1}, ..., n_{k}⟩. Ein Prioritätsmulticounterautomat kann so umgewandelt werden, daß er nur einen akzeptierenden Zustand z_{e} besitzt und vor dem Akzeptieren alle Zähler löscht. Dies geschieht dadurch, indem man man von jedem der bisherigen Endzustände einen λ-Übergang in einen neuen Zwischenzustand macht, in welchem die Zähler in einer λ-Schleife dekrementiert werden und mit einem weiteren Nulltest (mit j = k) bei einem weiteren λ-Übergang in den neuen Endzustand z_{e} geht. Wir können dann die von dem Prioritätsmulticounterautomaten A erkannte Sprache als L(A) = \{w | ⟨z_{0}, w, 0, ..., 0⟩ |\frac{∗}{A} ⟨z_{e}, λ, 0, ..., 0⟩\} betrachten.

Theorem 3.1 Für einen Prioritätsmulticounterautomaten ist entscheidbar, ob die erkannte Sprache leer ist.

Beweis: Zu einem Prioritätsmulticounterautomat mit einem Zustand kann ein Petrinetz (S, T, W, I, m_{0}, m_{1}) konstruiert werden mit den Stellen S := {1...k} ∪ Z, den Transitionen T = δ, den Gewichten W mit W (z, ((z′, a, j), (z′′, V))) := 1 falls z = z′ und := 0 sonst, W (((z′, a, j), (z′′, V)), z) := 1 falls z = z′′ und := 0 sonst, W (i, ((z′, a, j), (z′′, V))) := 1 falls V (i) = −1 und := 0 sonst und W (((z′, a, j), (z′′, V)), i) := 1 falls V (i) = 1 und := 0 sonst, den inhibitorischen Kanten I := {(i, ((z′, a, j), (z′′, V))) | i ≤ j}, der Anfangsmarkierung m_{0} := {z_{0} ↦ 1} und der Endmarkierung m_{1} := {z_{e} ↦ 1}, in welchem genau dann m_{1} von m_{0} erreichbar ist, wenn die von dem Prioritätsmulticounterautomaten akzeptierte Sprache nicht leer ist. Aufgrund von Theorem 2.2 mit g(i) = i für i ≤ k und g(z) = k + 1 für z ∈ Z ist dies entscheidbar. Beispiel: Sei k = 5 und die Transition t = ((z, a, 2), (z′, ⟨0, 1, −1, 0, 1⟩)) ∈ δ, so sieht das betreffende Teilnetz wie folgt aus:

[figure: z′; z; s_{1}; s_{2}; s_{3}; s_{4}; s_{5}; t; •; •]

Eine bestimmte Eingabe w kann in die Zustände eines Prioritätsmulticounterautomat kodiert werden, welcher die |w|-fache Anzahl von Zuständen besitzt und mit λ-Übergängen den ursprünglichen Prioritätsmulticounterautomat auf w simuliert. Die akzeptierte Sprache ist {λ} (und nicht {}) gdw. der ursprünglichen Prioritätsmulticounterautomat w akzeptiert; somit folgt:

Korollar 3.1 Für einen Prioritätsmulticounterautomaten A ist das Halteproblem (d.h. die Frage ⟨z_{0}, λ, 0, ..., 0⟩ |\frac{∗}{A} ⟨z_{e}, λ, 0, ..., 0⟩) entscheidbar.

3.1 Multicounter- und Prioritätsmulticountersprachen

In [Gon93] definiert D. Gonzalez die Klasse MC der Multicountersprachen als kleinste Familie, welche unter Schnitt und rationaler Transduktion abgeschlossen ist und die Semi-Dyck-Sprache D′_{1}^{∗} enthält. Die Sprachen in MC können gerade von einem Multicounterautomaten, der keinen Zähler auf Leerheit testen kann, erkannt werden (siehe [Gre78] Seite 316). Wegen z.B. {a^{n}b^{n} | n ≥ 0}^{∗} ∉ MC laut [Gre78] ist MC nicht unter Sternbildung abgeschlossen.

Definition Die Klasse P MC der Prioritätsmulticountersprachen ist der Abschluß (von {Σ^{∗}}) unter rationaler Transduktion, Sternbildung und Schnitt mit der Semi-Dyck-Sprache D′_{1}^{∗}.

P MC ist eine AFL. Die Sprachen in P MC können gerade von einem Prioritätsmulticounterautomaten erkannt werden. Es ist leicht zu sehen, daß ein Counterautomat, der bei 2 Zählern 0 testen kann, die Sprache {(a^{n}b)^{m} | n, m ∈ ℕ} erkennen kann, ein Prioritätsmulticounterautomat ist aber schwächer:

Theorem 3.2 Die Sprache {(a^{n}b)^{m} | n, m ∈ ℕ} kann nicht von einem Prioritätsmulticounterautomaten erkannt werden.

Beweis: Angenommen ein Prioritätsmulticounterautomat A mit k Zählern könnte die Sprache {(a^{n}b)^{m} | n, m ∈ ℕ} erkennen, so könnte ein Multicounterautomat M mit m Zählern und beliebigem Nulltest von einem Prioritätsmulticounterautomaten P, der k +2m Zähler besitzt, mit der folgenden Methode simuliert werden, wobei die ersten k Zähler den Zählern von A entsprechen und zwei der weiteren Zähler jeweils einem Zähler von M entsprechen: P rät zuerst in einer λ-Schleife den maximalen Zählerinhalt n, den ein Zähler von M während der simulierten Rechnung haben wird. Dabei beginnt P den Automaten A auf a^{n}b zu simulieren und gleichzeitig wird für jeden Zähler von M der ’Gegenzähler’ (d.h. einer der beiden entsprechenden Zähler) mit n gefüllt. Nun simuliert P den Automaten M, wobei jeder Gegenzähler immer in entgegengesetzter Richtung verändert wird, d.h. wird z.B. der z-te Zähler mit z ≤ m inkrementiert, so wird der entsprechende k+z-te Zähler ebenfalls inkrementiert und der entsprechende ’Gegenzähler’ (mit der Nummer k+m+z) dekrementiert. Wenn M einen Nulltest ausführt, so prüft P, ob der entsprechende Gegenzähler n hat, indem er, während er diesen n-fach dekrementiert, A auf a^{n}b weitersimuliert und anschließend, während er den Gegenzähler wieder n-fach inkrementiert, A nochmals auf a^{n}b weitersimuliert. Die Simulation von A kann nur akzeptieren, wenn n jedesmal richtig geraten wird. Somit ist sichergestellt daß vor und nach dem Nulltest der Inhalt des Gegenzählers n und der Zähler selbst daher 0 ist. P akzeptiert, wenn die Simulationen von M und A akzeptieren. Wegen Theorem 3.1 könnte somit die von M erkannte Sprache auf Leerheit überprüft werden, was ein Widerspruch ist. Zu einer Vielzahl von Klassen existiert gemäß [Ber79] und [Gre78] (siehe auch Diagramm auf der übernächsten Seite) eine Sprache, die vollständig bezüglich rationaler Transduktion in dieser Klasse ist. Dabei entspricht jedes Zeichen des Alphabetes einer Operation auf dem Speicher der Automaten, die die Sprachklasse erkennen können, so entsprechen z.B. die öffnenden- und schließenden Klammern der Dyck-Sprachen den zugehörigen push- und pop-Operationen der Kellerautomaten. Die Wörter der Sprache entsprechen den korrekten Protokollen des Speichers (siehe auch Kellerprotokolle in [Rei89]). Die Sprache kann von einem Automaten erkannt werden, der diese Operationen direkt ausführt. Umgekehrt kann jede andere Sprache der Klasse reduziert werden mittels eines Transducers, der den dazugehörigen Automaten simuliert und die ausgeführten Operationen auf das Ausgabeband schreibt. Die Simulation entspricht genau dann einer Rechnung des Automaten, wenn das ausgegebene Wort in der vollständigen Sprache liegt. Für k-P MC lautet die Sprache wie folgt: Sei P D_{0} := {λ}, Σ_{k} := {a_{1}, b_{1}, c_{1}, ..., a_{k}, b_{k}, c_{k}} und P D_{k} :=

\begin{matrix}(\{w ∈ (Σ_{k} \ \{c_{k}\})^{∗} | Π_{Σ_{k−1}}(w) ∈ P D_{k−1} ∧ \\ |w|_{a_{k}} = |w|_{b_{k}} ∧ ∀uv = w |u|_{a_{k}} ≥ |u|_{b_{k}}\}c_{k})^{∗}. \end{matrix}

Die Sprache P D_{k} ist vollständig bezüglich rationaler Transduktion in der Klasse k-P MC der von einem Prioritätsmulticounterautomaten mit k Zählern erkannten Sprachen. Hierbei entspricht a_{i} dem Inkrementieren des Zählers i, b_{i} dem Dekrementieren des Zählers i und c_{i} dem Nulltest des Zählers i und allen Zählern l ≤ i, da aus wc_{i}v ∈ P D_{k} folgt daß ∀l ≤ i |w|_{a_{l}} = |w|_{b_{l}} gilt.

3.2 Die Inklusionsstruktur der Sprachklassen

Theorem 3.3 Für k > 0 sind die Klassen k-P MC und LIN unvergleichbar und für k > 1 sind die Klassen k-P MC und CF L unvergleichbar

Beweis: ’⊈’: Die Sprachen {a^{n}b^{n} | n ∈ ℕ}^{∗} bzw. {a^{n}b^{n}c^{n} | n ∈ ℕ} sind in 1-P MC bzw. 2-P MC aber nicht linear bzw. kontextfrei. ’⊉’: Die Sprache {w$w^{R} | w ∈ {a, b}^{∗}} ist linear. Könnte ein Prioritätsmulticounterautomat mit k Zählern die Sprache erkennen, so könnte ein solcher auch die Sprache

\begin{matrix}\{a^{n_{1}}ba^{n_{2}}...ba^{n_{k+1}}$a^{n_{k+1}}b...a^{n_{2}}ba^{n_{1}} | ∀i ≤ k + 1 n_{i} ∈ ℕ\} = \\ \{w$w^{R} | w ∈ \{a, b\}^{∗}\} ∩ \{w ∈ \{a, b, $\}^{∗} | |w|_{b} = 2k\} \end{matrix}

erkennen, was nach folgendem Lemma 3.1 nicht möglich ist.

Lemma 3.1 {a^{n_{1}}ba^{n_{2}}...ba^{n_{k+1}}$a^{n_{k+1}}b...a^{n_{2}}ba^{n_{1}} | ∀i ≤ k + 1 n_{i} ∈ ℕ} ∉ k-P MC.

Beweis: Eine Prioritätsmulticounterautomat A mit k Zählern, der die Sprache {a^{n_{1}}ba^{n_{2}}...ba^{n_{k+1}}$a^{n_{k+1}}b...a^{n_{2}}ba^{n_{1}} | ∀i ≤ k + 1 n_{i} ∈ ℕ} erkennt, kann gemäß Theorem 3.1, Theorem 2.2 und Theorem 2.1 umgewandelt werden in ein geschachteltes Petrinetz (∅, T), das für alle t ∈ T die Bedingungen 1-6 erfüllt. Da die Anzahl 2k der Transitionen, die dem Lesen eines b’s entsprechen, beschränkt ist (gleiches gilt für $), müssen sich die Transitionen, die vor und nach einem solchen Schaltvorgang schalten, in verschiedenen Unternetzen schalten. Aus diesem Grund beschreibt jeder Schaltpfad f ∈ E_{T} u.a. eindeutig ein Wort der Sprache und die Konfiguration von A bei Lesen von $, d.h. es existieren Homomorhpismen

h_{a} : ℕ^{Q} ↦ ℕ^{k+1} und h_{k} : ℕ^{Q} ↦ ℕ^{k} mit Q := ⋃_{(K,c,P)∈T}{c} ∪ P, wobei für alle

f ∈ E_{T} in dem durch f beschriebenen Wort h_{a}(f)(i) = n_{i} für alle i ≤ k + 1 gilt und der j-te Zähler beim lesen von $ den Wert h_{k}(f)(j) hat. Um alle Wörter der Sprache zu erreichen, muß ein t = (K, c, P) ∈ T existieren, mit den Periodenmultimengen p_{1}...p_{k+1} ∈ P, wobei

f_{a}({p_{1} ↦ 1}), ..., f_{a}({p_{k+1} ↦ 1})

linear unabhängig sind. Andererseits müssen aber

f_{k}({p_{1} ↦ 1}), ..., f_{k}({p_{k+1} ↦ 1})

linear abhängig sein und somit existiert ein g ∈ ℤ^{\{p_{1},...p_{k+1}\}} mit f_{k}(g) = \overline{0} und f_{a}(g) ≠ \overline{0}. Nach Lemma 2.1 folgt nun für f = \{1\}^{P} die Existenz eines k mit

{c ↦ 1} + kf, {c ↦ 1} + kf + g ∈ E_{t}.

Diese Pfade beschreiben zwei verschiedene Wörter der Sprache, bei denen A beim Lesen von $ in der gleichen Konfiguration ist. Durch falsches Zusammensetzen der Worthälften erhält man damit ein Wort, das der Prioritätsmulticounterautomat A fälschlicherweise akzeptiert.

Da die Sprache {a^{n_{1}}ba^{n_{2}}...ba^{n_{k+1}}$a^{n_{k+1}}b...a^{n_{2}}ba^{n_{1}} | ∀i ≤ k + 1 n_{i} ∈ ℕ} leicht von einem Zählerautomaten mit k + 1 blinden Zählern erkannt werden kann, folgt:

Korollar 3.2 Die Hierarchien k-BLIND und k-P BLIND gemäß [Gre78] und die Hierarchie k-P MC sind echt.

Bemerkung: Sei Σ_{l} := {a_{0}, b_{0}, c_{0}, ..., a_{l}, b_{l}, c_{l}} und LD_{k,l} :=

{w ∈ Σ_{l}^{∗} | Π_{Σ_{k}}(w) ∈ P D_{k} ∧ ∀i ≤ l |w|_{a_{i}} = |w|_{b_{i}} ∧ ∀uv = w |u|_{a_{i}} ≥ |u|_{b_{i}}}.

Die Sprache LD_{k,l} kann von einem Prioritätsmulticounterautomaten, welcher überhaupt nur bei den ersten k Zählern einen Nulltest machen darf (aber weitere l − k Zähler haben kann), erkannt werden. Vermutlich ergibt sich dabei mit dieser Einschränkung eine echte Hierarchie. Es ist aber nicht einmal bekannt, ob ein Prioritätsmulticounterautomat Sprachen erkennen kann, die kein Multicounterautomat, der bei genau einem seiner Zähler Null testen kann, erkennen kann.

Ein Überblick über Sprachklassen, bei denen das Leerheitsproblem entscheidbar ist, deren Automaten und die dazugehörigen, unter rationaler Transduktion vollständigen Sprachen gibt folgendes Inklusionsdiagramm:

endlicher Automat 1-turn Zählerautomat {a^{n}b^{n} | n ∈ ℕ} [figure]  [figure] ss  [figure] blinder Zählerautomat {w | |w|_{a} = |w|_{b}} [figure] [figure] schwacher Zählerautomat ROCL D′_{1}^{∗} [figure] [figure]  1-turn Kellerautomat LIN {w$w^{R} | w ∈ {0, 1}^{∗}} starker Zählerautomat OCL (D′_{1}^{∗}c)^{∗} [figure]  [figure] BLIND Multicounterautomat PBLIND = MC [figure] Prioritätsschlangenautomat [figure]  Kellerautomat CFL D′_{2}^{∗} Multicounterautomat mit einem Nulltestzähler [figure] Prioritätsmulticounterautomat

Vermutung: Das Halteproblem für einen Prioritätsmulticounterautomaten mit einem zusätzlichem Keller, der bei einem Nulltest leer sein muß ist ebenfalls entscheidbar. Die Klasse der von solchen Automaten erkannten Sprachen enthält alle Sprachklassen des Diagramms.

Eine andere Möglichkeit zur Definition von Zählerautomaten besteht darin blinde Zähler (vergleiche BLIND in [Gre78]) zu verwenden, deren Inhalt auch negativ sein kann. Bei einem solchen Zähler kann man außer Inkrement und Dekrement anstelle eines Nulltest einen Natürlichkeitstest (d.h. Zahlerinhalt ≥ 0) als Instruktion erlauben. Einen Prioritätsnatürlichkeitstestautomaten kann man analog zum Prioritätsmulticounterautomaten definieren; die einzigen Unterschiede sind dabei die neue Konfigurationenmenge C_{A} = Z×Σ^{∗}×ℤ^{k} und die Konfigurationsübergangsrelation ⟨z, ax, n_{1}, ..., n_{k}⟩ |_{\overline{A}} ⟨z′, x, n_{1} + i_{1}, ..., n_{k} + i_{k}⟩, welche jetzt die Bedinung z, z′ ∈ Z, a ∈ Σ, ⟨(z, a, j), (z′, i_{1}, ...i_{k})⟩ ∈ δ, ∀i ≤ j n_{i} ≥ 0 hat. Ein solcher Automat kann einen Prioritätsmulticounterautomaten mit der doppelten Anzahl von Zählern simulieren. Dabei wird ein Zähler durch zwei Zähler mit umgekehrtem Vorzeichen (Inkrementieren und Dekrementieren vertauscht) simuliert. Einer der Zähler wird bei jedem Schritt auf ≥ 0 geprüft wird und der Nulltest wird durch einen Natürlichkeitstest des ’Gegenzählers’ simuliert. Umgekehrt kann ein solcher Automat auch von einem Prioritätsmulticounterautomaten mit der doppelten Anzahl von Zählern simuliert werden. Der Inhalt eines Zählers wird als Differenz zweier Zähler dargestellt und für jede Veränderung des simulierten Zählers wird nichtdeterministisch entweder der positive Teil oder der negative Teil in umgekehrter Weise verändert. Der Natürlichkeitstest wird durch einen Nulltest des negativen Teils simuliert. Im Gegensatz zu Prioritätsmulticounterautomaten läßt sich vermuten, daß zugelassen werden kann, daß die ersten zwei oder vielleicht auch drei (aber keinesfalls vier) Zähler unabhängig von ihrer Priorität auf Natürlichkeit getestet werden können, ohne daß das Leerheitsproblem dadurch unentscheidbar wird. Ein solcher Automat kann Sprachen erkennen (siehe später in Kapitel 5), die nicht in PMC liegen.

4 Die Synchronisation von Halbspuren

4.1 Die Inklusion von Halbspuren

Eine grundsätzliche Fragestellung für eine gültige Ablauffolge eines konkurrierenden Systems ist, ob eine andere Ablauffolge ebenfalls gültig ist. Ist das System durch partielle Kommutation beschrieben, so entspricht diese Fragestellung dem folgenden Spuräquivalenzproblem: Gegeben seien ein symmetrisches Semikommutationssystem C und zwei Wörter w, w′; gilt w ⟹_{C}^{∗} w′? Daß das Spuräquivalenzproblem in T C^{0} liegt, wurde in [AG91] gezeigt. Dort wird für jedes abhängige Paar (a, b) in Logik erster Stufe mit zusätzlichem Majoritätsquantor beschrieben, ob es für jede Postion in w eine entsprechende Position in w′ mit der gleichen Anzahl vorhergehender a’s und b’s gibt. Nach einem Resultat von [BIS90] liegt dies folglich in T C^{0}. Die Struktur S eines Wortpaares w, w′ für ein festes Halbabhängigkeitsalphabet ist

S = ⟨{1...k}, Ξ_{w,x_{1}}, ..., Ξ_{w,x_{n}}, Ξ_{w′,x_{1}}, ..., Ξ_{w′,x_{n}}⟩

mit dem Universum {1...k} und Prädikaten

Ξ_{w,x_{1}}(i) ≡ ’Das i-te Zeichen in w ist x_{1}’.

Die Struktur S eines Wortpaares w, w′ mit einem Halbabhängigkeitsalphabet (A, SD) mit A = {a_{1}, ..., a_{|A|}} ist

S = ⟨{1...k}, Ξ_{w}, Ξ_{w′}, Ξ_{SD}⟩

mit dem Universum {1...k} mit |w|, |w′|, |A| ≤ k und Prädikaten

Ξ_{w}(i, j) ≡ ’Das i-te Zeichen in w ist a_{j}’
und Ξ_{SD}(i, j) ≡ (a_{i}, a_{j}) ∈ SD.

In der Logik erster Stufe können zusätzlich die Prädikate =, ≤ und BIT mit

BIT (i, j) ≡ ’Das i-te Bit in der Binärdarstellung von j ist 1’,

die logisch Junktoren ∧, ∨¬ und die Quantoren ∀ und ∃ für Variablen über dem Universum verwendet werden. Steht auch der Majoritätsquantor

Mi : ϕ(i) ≡ ’Für mehr als die Hälfte aller möglichen i’s ist ϕ(i) wahr’

zur Verfügung, so kann damit auch das Prädikat

j = #i : ϕ(i) ≡ ’j ist die Zahl der Werte i für die ϕ(i) gilt’

ausgedrückt werden. Die gleiche Methode wie in [AG91] kann auch auf asymmetrische Semikommutationssysteme angewendet werden:

Theorem 4.1 Das folgende Halbspur-Inklusionsproblem ist in T C^{0}: Gegeben seien ein asymmetrisches Semikommutationssystem SC durch das Halbabhängigkeitsalphabet (A, SD) und zwei Wörter w, w′; gilt w ⟹_{SC}^{∗} w′ bzw. [w′⟩ ⊆ [w⟩?

Beweis: Nach folgende Projektionslemma (siehe [Cle84]) gilt: Für ein Semikommutationssystem SC gilt

w ⟹_{SC}^{∗} w′ ⇔ ∀(a, b) ∈ A^{2}, Π_{ab}(w) ⟹_{SC}^{∗} Π_{ab}(w′).

In analoger Weise wie im Spuräquivalenzfall können wir für jedes (asymmetrisch) abhängige Paar (a_{i}, a_{j}) ∈ SD beschreiben, ob es für jede Position l in w eine entsprechende Position m in w′ mit der gleichen Anzahl vorhergehender a_{i}’s und einer höchstens so großen Anzahl vorhergehender a_{j}’s gibt. Um sicherzustellen, daß w′ keine zusätzlichen Zeichen enthält, wird zusätzlich beschrieben, daß es für jede Position m in w′ eine entsprechende Position l in w mit der gleichen Anzahl vorhergehender a_{i}’s gibt. Das beschreibende Prädikat lautet

∀i ∀j (¬Ξ_{SD}(i, j) ∨ ∀l ∃m ∃k_{1} (k_{1} = #l′ : l′ ≤ l ∧ Ξ_{w}(l′, i)) ∧

(k_{1} = #m′ : m′ ≤ m ∧ Ξ_{w′}(m′, i)) ∧

∃k_{2} ∃k_{3} (k_{2} = #l′ : l′ ≤ l ∧ Ξ_{w}(l′, j)) ∧
(k_{3} = #m′ : m′ ≤ m ∧ Ξ_{w′}(m′, j)) ∧
(k_{3} ≤ k_{2}) ∧

∀i ∀m ∃l ∃k_{1} (k_{1} = #l′ : l′ ≤ l ∧ Ξ_{w}(l′, i)) ∧ (k_{1} = #m′ : m′ ≤ m ∧ Ξ_{w′}(m′, i))

und nach [BIS90] liegt die Inklusion von Halbspuren folglich in T C^{0}.

Es ist leicht zu sehen, daß die Inklusion von Halbspuren auch für ein festes SD in T C^{0} liegt. Bereits für SD = {(1, 0)} liegt die Inklusion von Halbspuren jedoch nicht in AC_{0}, da gemäß [AG91] der Majoritätsquantor in konstanter Tiefe durch

w ∈ MAJ ⇔ ⋁_{i< \frac{|w|}{2}}[1^{|w|−i}0^{i}⟩ ⊆ [w⟩

darauf reduziert werden kann.

4.2 Die Synchronisierbarkeit von Halbspuren

Gegeben seien m Halbabhängigkeitsalphabete (A_{i}, SD_{i}) mit 0 < i ≤ m und die Halbspuren [u_{1}⟩_{1}, [u_{2}⟩_{2}, … [u_{m}⟩_{m}. Die Bedingung

∀i, j ≤ m ∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a}

ist notwendig für Synchronisierbarkeit. Dies zu überprüfen liegt in T C^{0}. Doch dies ist nicht hinreichend.

Beispiel: Betrachte die folgenden Halbabhängigkeitsalphabete

[figure: (A_{1}, SD_{1}) =; a; b; c; und; (A_{2}, SD_{2}) =; a; b; d]

mit dem durch Vereinigung erhaltenen

Halbabhängigkeitsalphabet (A, SD) = [figure: a; b; c; d]

und die Halbspuren

[figure: [cacba⟩_{1} =; c; a; c; b; a; .; .; .; .; .; .; .; .; .; .; [dbada⟩_{2} =; d; b; a; d; a; .; .; .; .; .; .; .; .; .; .]

[figure: [bdada⟩_{2} =; d; b; a; d; a; .; .; .; .; .; [daadb⟩_{2} =; d; a; a; d; b; .; .; .; .; .; .; .; .; .; .]

Da in der Synchronisation die Ordnung jedes abhängigen Paares erhalten bleiben muß, kann man sie durch die Vereinigung beschreiben. Beispielsweise für [cacba⟩_{1} ∥ [dbada⟩_{2} erhalten wir

[figure: [cdacbda⟩ =; c; d; a; c; b; d; a; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

Andererseits erhalten wir für [cacba⟩_{1} ∥ [bdada⟩_{2} den Graphen

[figure: c; d; a; c; b; d; a; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

und daher ist [cacba⟩_{1} ∥ [bdada⟩_{2} = ∅. Daraus läßt sich ersehen, daß Halbspuren genau dann synchronisierbar sind, wenn die Vereinigung ihrer Graphen keinen Kreis aus harten Kanten enthällt. (Störende weiche Kanten können herumgedreht werden). Dies führt zu den folgenden zwei Theoremen.

Theorem 4.2 Das folgende Problem ist NLOGSPACE-vollständig: Gegeben seien m Halbabhängigkeitsalphabete (A_{i}, SD_{i}) mit 0 < i ≤ m und die Halbspuren [u_{1}⟩_{1}, [u_{2}⟩_{2}, … [u_{m}⟩_{m}. Gilt [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} ≠ ∅?

Beweis: Nach der deterministischen Überprüfung von ∀i, j ≤ m ∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a} rät eine nichtdeterministische logarithmisch platzbeschränkte Turingmaschine einen Kreis und überprüft jede Verbindung indem sie die Reihenfolge und die Abhängigkeit des jeweiligen Paares in jeder Halbspur überprüft.

Nach [Imm88] und [Sze88] liegt das Komplement, d.h. die Nichtexistenz eines solchen Kreises ebenfalls in NLOGSPACE. Die NLOGSPACE-Härte folgt aus Theorem 4.3.

Theorem 4.3 Das folgende Problem ist NLOGSPACE-vollständig: Gegeben seien ein Halbabhängigkeitsalphabet (A, SD) und die Halbspuren [u⟩, [v⟩ mit

∀a ∈ A |u_{i}|_{a} = |u_{j}|_{a}.

Gilt [u⟩ ∩ [v⟩ ≠ ∅?

Beweis: Das Problem ist in NLOGSPACE wegen Theorem 4.2. Das monotone Grapherreichbarkeitsproblem für gerichtete Graphen ist bekanntlicherweise NLOGSPACE-vollständig; für einen gegebenen Graphen

G = ({s = a_{1}, a_{2}, … a_{n} = e}, R)

mit der Eigenschaft (a_{i}, a_{j}) ∈ R ⇒ i < j soll ermittelt werden, ob ein gerichteter Pfad von s nach e existiert. Dies kann man auf das Synchronisierbarkeitsproblem reduzieren, indem man die Kante (e, s) zu dem Abhängigkeitsgraphen ({s, a_{2}, a_{3} … a_{n−1}, e}, R) hinzufügt (SD := R∪{(e, s)}) und nach der Synchronisierbarkeit von [esa_{2}a_{3} … a_{n−1}⟩ und [a_{2}a_{3} … a_{n−1}es⟩ fragt. Es existiert ein gerichteter Pfad von s nach e, gdw.die Halbspuren nicht synchronisierbar sind, weil ein Kreis aus harten Kanten vorhanden ist. Für die Beschreibung modularer Systeme ist es nützlich, wenn die Synchronisation von Halbspuren immer eine Halbspur ist, wenn die Halbspuren synchronisierbar sind. Doch dies ist nicht immer der Fall, wie man am Beispiel [cacba⟩_{1} ∥ [daadb⟩_{2} sehen kann. Wir erhalten hierbei

[figure: c; d; a; c; b; d; a; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

und daher gilt [cacba⟩_{1} ∥ [daadb⟩_{2} = [cdacbad⟩_{1} ∪ [cdacdba⟩_{2} da entweder die weiche Kante a [figure] d oder die weiche Kante d [figure] b umgedreht werden muß. Es ist leicht zu sehen, daß die Synchronisation von Halbspuren eine Halbspur ist, gdw.die Vereinigung ihrer Graphen keinen Kreis aus harten Kanten und keinen Kreis mit mindestens 2 weichen Kanten, welche unabhänging voneinander umgedreht werden können, besitzt. Damit kommt man zu den zwei folgenden Theoremen.

Theorem 4.4 Das folgende Problem ist NLOGSPACE-vollständig: Gegeben seien m Halbabhängigkeitsalphabete (A_{i}, SD_{i}) mit 0 < i ≤ m und die Halbspuren [u_{1}⟩_{1}, [u_{2}⟩_{2}, … [u_{m}⟩_{m}. Gilt ∃w ∈ A^{∗} mit [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} = [w⟩?

Beweis: Eine nichtdeterministische logarithmisch platzbeschränkte Turingmaschine kann zu einer weichen Kante einen Kreis aus harten Kanten finden, welcher es verbieten würde, daß diese Kante umgedreht wird. Mit Hilfe der Technik von [Imm88] und [Sze88] kann sie somit auch für eine weiche Kante überprüfen, ob sie umgedreht werden kann. Somit kann sie auch einen Kreis mit zwei weichen Kanten raten und überprüfen, ob beide umgedreht werden können. Unter abermaliger Anwendung von [Imm88] und [Sze88] kann sie, nachdem sie zuvor die Synchronsierbarkeit festgestellt hat, überprüfen, ob kein solcher Kreis existiert. Die NLOGSPACE-Härte folgt aus Theorem 4.5.

Theorem 4.5 Das folgende Problem ist NLOGSPACE-vollständig: Gegeben seien ein Halbabhängigkeitsalphabet (A, SD) und die Halbspuren [u⟩, [v⟩ mit [u⟩ ∩ [v⟩ ≠ ∅. Gilt ∃w ∈ A^{∗} mit [u⟩ ∩ [v⟩ = [w⟩?

Beweis: Das Problem ist in NLOGSPACE wegen Theorem 4.4. Das monotone Grapherreichbarkeitsproblem für gerichtete Graphen kann man auf das Problem reduzieren, indem man die zusätzlichen Knoten b und c und die Kanten (b, s), (b, c), (e, c) und (e, s) zu dem Graphen hinzufügt und bei dem so erzeugten Abhängigkeitsgraphen ({b, c, s, a_{2}, a_{3}, … a_{n−1}, e}, SD) überprüft, ob die Synchronisation der Halbspuren [cbs(a_{2}a_{3} … a_{n−1})^{n}e⟩ und [s(a_{2}a_{3} … a_{n−1})^{n}ecb⟩ eine Halbspur ist.

[figure: s; e; c; b; (a_{2}...a_{n−1})^{n}; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

Die Synchronisation ist genau dann die Halbspur [bs(a_{2}a_{3} … a_{n−1})^{n}ec⟩, wenn ein Pfad aus harten Kanten von s nach e existiert.

4.3 Die Synchronisierbarkeit in Semikommutationssystemen

Es ist leicht zu sehen, daß nur ein Kreis aus harten Kanten von mindestens zwei Halbspuren für die Nichtsynchronisierbarkeit von Halbspuren für die ∀i, j ≤ m ∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a} gilt, verantwortlich sein kann. (Ein solcher Kreis kann auch aus einer einzigen symmetrischen Kante bestehen.) Dieser Kreis muß sich natürlich im Abhängigkeitsgraphen widerspiegeln und sich aus Kanten aus mindestens zwei der Abhängigkeitsgraphen zusammensetzen.

Theorem 4.6 Gegeben seien m Halbabhängigkeitsalphabete (A_{i}, SD_{i}) mit 0 < i ≤ m. Die folgenden Aussagen sind äquivalent: i) ∀u_{1} ∈ A_{1}^{∗}, … u_{m} ∈ A_{m}^{∗}, (∀i, j ≤ m ∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a}) ⇒ [u_{1}⟩_{1} ∥

[u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} ≠ ∅

ii) ¬∃1 < k, i ≠ j, C = {(x_{1}, x_{2}), … (x_{k−1}, x_{k}), (x_{k}, x_{1})} mit C ⊆ SD ∧ C ∩ SD_{i} ≠ ∅ ∧ C ∩ SD_{j} ≠ ∅

Auch diese Eigenschaft ist NLOGSPACE-vollständig. Das nächste Theorem besagt, daß Halbabhängigkeitsalphabete genau dann die Eigenschaft haben, daß es vorkommen kann, daß die Synchronisation zweier Halbspuren nicht leer aber trotzdem keine Halbspur ist, wenn in der Vereinigung dieser Halbabhängigkeitsalphabete ein Kreis derart existiert, daß

• die Knoten verschieden sind,

• zwei gerichtete Kanten (x_{1}, x_{k}) und (x_{j+1}, x_{j}) in Gegenrichtung zeigen,

• diese beiden Kanten nicht durch eine Sehne getrennt sind,

• keine Sehne rückwärts verläuft und

• der Kreis in jedem der Halbabhängigkeitsalphabete an einer Stelle unterbrochen ist oder an einer Stelle eine gerichtete Kante in Gegenrichtung besitzt, doch im diesem Fall muß an dieser Stelle eine Kante in einem der anderen Halbabhängigkeitsalphabete existieren, in welchem der Kreis an einer anderen Stelle unterbrochen ist oder eine Kante in Gegenrichtung besitzt.

[figure: x_{k}; x_{j+1}; x_{1}; x_{j}; ⋯; ⋯]

Theorem 4.7 Gegeben m Halbabhängigkeitsalphabete (A_{i}, SD_{i}) mit 0 < i ≤ m. Die folgenden Aussagen sind äquivalent:

i) ∀u_{1} ∈ A_{1}^{∗}, … u_{m} ∈ A_{m}^{∗}∃w ∈ A^{∗} mit [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} = [w⟩ oder = ∅

ii) ¬∃0 < j < k, (x_{1}, x_{2}), …, (x_{k−1}, x_{k}) ∈ SD ∪ SD^{−1} mit

∀n ≠ p ⇒ x_{n} ≠ x_{p}∧

(x_{1}, x_{k}), (x_{j+1}, x_{j}) ∈ SD \ SD^{−1}∧

∀n, p mit 0 < n ≤ j < p ≤ k, n + 1 < p < n + k − 1 ⇒

(x_{n}, x_{p}) ∉ SD ∪ SD^{−1}∧

∀n, p mit 1 < n + 1 < p ≤ k ⇒ (x_{p}, x_{n}) ∉ SD∧

∀i ≤ m∃n ≤ k, ((x_{n+1}, x_{n}) ∉ SD_{i}∧
((x_{n}, x_{n+1}) ∉ SD_{i}∨
∃l ≤ m, ≠ i, p ≤ k, ≠ n,(x_{p+1}, x_{p}) ∉ SD_{l}∧
(x_{n}, x_{n+1}) ∈ SD_{l} ∪ SD_{l}^{−1}))

Das einfachste Beispiel hierfür ist (A_{1}, SD_{1}) = ({a, b}, {(a, b)}) und (A_{2}, SD_{2}) = ({a, b}, {(b, a)}) in diesem Fall gilt [ba⟩_{1} ∥ [ab⟩_{2} = {ab, ba} ≠ [u⟩ für jedes u. Betrachten wir nur Halbspuren über einem Halbabhängigkeitsalphabet, so erhalten wir, daß es vorkommen kann, daß die Synchronisation von Halbspuren keine Halbspur aber auch nicht leer ist, gdw.ein Kreis aus verschiedenen Knoten mit zwei gerichteten Kanten in jeder Richtung derart existiert, daß Sehnen nur in der Richtung von einem Teil, von dem aus zwei dieser Kanten wegzeigen zu einem Teil zu dem die beiden anderen hinzeigen (mit anderen Worten Sehnen, die diese Kanten ’abkürzen’) vorkommen .

Korollar 4.1 Gegeben ein Halbabhängigkeitsalphabet (A, SD). Die folgenden Aussagen sind äquivalent:

i) ∀u, v ∈ A^{∗}∃w ∈ A^{∗} mit [u⟩ ∥ [v⟩ = [w⟩ oder = ∅

ii) ¬∃0 < j < k, n ≠ p ≠ j, k, (x_{1}, x_{2}), … (x_{k−1}, x_{k}) ∈ SD ∪ SD^{−1} mit

∀n ≠ p ⇒ x_{n} ≠ x_{p}∧

(x_{1}, x_{k}), (x_{j+1}, x_{j}) ∈ SD \ SD^{−1}∧ (x_{n+1}, x_{n}), (x_{p+1}, x_{p}) ∈ SD^{−1} \ SD∧ ∀n, p mit 0 < n ≤ j < p ≤ k, n + 1 < p < n + k − 1 ⇒

(x_{n}, x_{p}) ∉ SD ∩ SD^{−1}∧

∀n, p mit 1 < n + 1 < p ≤ k ⇒ (x_{p}, x_{n}) ∉ SD

So gibt es gerade die beiden grundlegenden Beispiele für Halbabhängigkeitsalphabete (alle anderen lassen sich durch Zusammenfassen von Knoten darauf reduzieren):

[figure: a; b; c; d; und; a; b; c; d]

Im ersten Beispiel würde jede eventuelle Sehne die Situation [cabd⟩ ∥ [bdca⟩ = [abdc⟩ ∪ [dcab⟩ ≠ [u⟩ für jedes u verhindern. Im zweiten Beispiel ’funktioniert’ die Situation [dcab⟩ ∥ [bdca⟩ = [abdc⟩ ∪ [cdba⟩ ≠ [u⟩ für jedes u unabhängig von der Existenz der Kante von a nach d. Nun kommen wir zum Beweis von Theorem 4.7: Beweis: ¬ii ⇒ ¬i: Betrachte den kürzesten Kreis dieser Art und wähle u_{i} = x_{n+1} … x_{k}x_{1}x_{2} … x_{n} so, daß (x_{n+1}, x_{n}) ∉ SD_{i} und (x_{n}, x_{n+1}) ∉ SD_{i} ∨ ∃l ≤ m, ≠ i, (x_{n}, x_{n+1}) ∈ (SD_{l}∪SD_{l}^{−1})∩[u_{l}⟩_{l}. Somit hat die Synchronisation einen Kreis mit den weichen Kanten (x_{k}, x_{1}) und (x_{j}, x_{j+1}) und keinen Kreis aus harten Kanten. ¬i ⇒ ¬ii: Wähle v, v′, u_{i} (Längen-)minimal mit ∀iΠ_{A_{i}}^{A}(v) = u_{i}, ∀iΠ_{A_{i}}^{A}(v′) = u_{i} und ¬∃w mit ∀i Π_{A_{i}}^{A}(w) = u_{i}, v, v′ ∈ [w⟩. Konstruiere G als die Vereinigung aller Graphen von [u_{i}⟩_{i}. Konstruiere G′ aus G indem jedes b [figure]a durch a ⟶ b ersetzt wird, falls a = x_{1} ⟶ x_{2} ⟶ … x_{j} = b in G. Wegen v, v′ enthält der Graph G′ keinen Kreis aus harten Kanten. Somit muß G′ einen Kreis mit mindestens zwei weichen Kanten besitzen,

[figure: x_{k}; x_{1}; x_{j+1}; x_{j}; ...; ...; .; .; .; .; .; .; .; .; .; .]

da ansonsten G′ den Graphen für [w⟩ darstellen würde. G′ muß ohnehin die harten Kanten von G enthalten, denn es gilt ∀i Π_{A_{i}}^{A}(w) = u_{i} und Kreise mit einer weichen Kante verschwinden bei der Konstruktion von G′. Der kürzeste Kreis dieser Art hat kein Sehne. Mit der im folgenden beschriebenen iterativen Methode können wir einen Kreis mit mindestens zwei weichen Kanten finden, dessen harte Kanten nicht neu, d.h. aus G sind und der nur neue Sehnen (aus G′ \ G) besitzt, welche die beiden weichen Kanten nicht trennen und in Richtung des Kreises verlaufen: Wir ersetzen eine neue Kante im Kreis durch den Pfad originaler Kanten, durch den diese Kante erzeugt wurde. Führt dies zu einer unerlaubten Sehne, so können wir immer einen kürzeren Kreis finden, der mindestens zwei weiche Kanten und keine unerlaubte Sehne besitzt. Da sich in einem solchen Schritt die Anzahl der weichen Kanten oder die Anzahl der neuen harten Kanten im Kreis vermindert, muß diese Methode terminieren. Aufgrund der Minimalität der u_{i} gibt es keine anderen Knoten in G′ außer denen im Kreis und kein Element von A kommt mehrfach vor. Ferner kann der Kreis aufgrund der Minimalität keine weiche Sehne besitzen und daher kann es in SD keine Sehne in Gegenrichtung geben. Jede Kante im Kreis muß von einem der [u_{i}⟩_{i}’s stammen. Doch der Kreis muß für jedes [u_{i}⟩_{i} an irgendeiner Stelle offen sein und dies könnte eine Stelle sein, an der [u_{i}⟩_{i} eine harte Kante hätte beitragen können. In diesem Fall muß die Kante von einem anderen [u_{l}⟩_{l} geliefert werden. Dieses [u_{l}⟩_{l} muß jedoch an einer anderen Selle offen sein. Genau dies drückt die Formel in ¬ii aus.

Theorem 4.8 Es ist co-NP-vollständig zu entscheiden, ob für Semikommutationssysteme bzw. für ein Semikommutationssystem die Aussagen von Theorem 4.7 bzw. Korollar 4.1 erfüllt sind.

Beweis: Es ist leicht zu sehen, daß das Problem in co-NP liegt. Zum Beweis der Härte kann fast die gleiche Graphkonstruktion wie in [DOR94] für ein Halbabhängigkeitsalphabet (A, SD) verwendet werden. Der einzige Unterschied ist, daß anstelle der zwei dort verwendeten gerichteten Kanten jeweils ein zusätzlicher Knoten und zwei zu diesem gerichtete Kanten einzusetzten sind. Gegeben sei ein Ausdruck e = c_{1} ∧ … ∧ c_{n} in konjunktiver 3-Normalform über den Variablen x_{1}, ..., x_{m}. Wir konstruieren nun daraus einen Graphen für (A, SD), der genau 4 gerichtete Kanten besitzt. Das Halbabhängigkeitsalphabet (A, SD) besitzt in diesem Fall die Eigenschaft (ii) in Korollar 4.1 genau dann nicht, wenn ein Kreis ohne Sehnen aus verschiedenen Knoten mit zwei gerichteten Kanten in jeder Richtung im Graphen existiert. Durch die Konstruktion wird dies genau dann der Fall sein, wenn der Ausdruch e erfüllbar ist. Zunächst konstruieren wir einen Graphen G(x) mit x = (x_{1}, ..., x_{m}) wie im folgendem Bild:

[figure: .; .; .; .; .; .; .; .; .; .; .; .; \overline{x_{m}}; \overline{x_{2}}; \overline{x_{1}}; x_{1}; x_{2}; x_{m}; x_{m}; x_{2}; x_{1}; \overline{x_{1}}; \overline{x_{2}}; \overline{x_{m}}; l_{1}; r_{1}]

Jede Belegung der Variablen x_{1}, ..., x_{m} entspricht eindeutig einem Pfad ohne Sehnen von l_{1} nach r_{1}, der durch die Knoten verläuft, welche mit einer Variablen benannt sind, die mit ’wahr’ belegt ist. Zu jeder Klausel c = (x ∨ y ∨ z) konstruieren wir den Graphen

[figure: z; y; x; G(c) =]

und zu dem Ausdruck e = c_{1} ∧ ⋯ ∧ c_{n} den Graphen

[figure: G(c_{n}); G(c_{2}); G(c_{1}); r; l; G(e) =]

als disjunkte Vereinigung G(c_{1}) ˙∪ ⋯ ˙∪ G(c_{n}), wobei zusätzlich für alle 1 ≤ i < n das rechte Ende von G(c_{i}) mit dem linken Ende von G(c_{i+1}) verbunden wird. Das linke Ende von G(e) nennen wir l und das rechte r. Existiert eine erfüllende Belegung der Variablen x_{1}, ..., x_{m}, so ist in jeder Klausel eine Variable ’wahr’ und somit existiert auch ein Pfad ohne Sehnen von l_{1} nach r_{1}, der nur durch Knoten verläuft, welche mit keiner Variablen benannt sind, die nicht mit ’wahr’ belegt ist. Den gesamten Graphen für e, welcher die Form

[figure: r; l; l_{1}; r_{1}; G(x); G(e)]

hat, erhalten wir durch die disjunkte Vereinigung G(x) ˙∪ G(e) und durch Hinzufügen einer symmetrischen Kante zwischen r_{1} und r und gerichteten Kanten von l und l_{1} zu einem zusätzlichen Punkt. Weiterhin werden für alle 1 ≤ i ≤ m alle mit x_{i} benannten Knoten mit allen mit \overline{x_{i}} benannten Knoten verbunden. Existiert eine erfüllende Belegung der Variablen x_{1}, ..., x_{m}, so setzen sich die beiden entsprechenden Pfade in G(x) und G(e) mit den drei hinzugefügten Kanten zu einem Kreis ohne Sehnen mit zwei gerichteten Kanten in jeder Richtung zusammen. Umgekehrt ergibt sich aus der Existenz eines solchen Kreises eine erfüllende Belegung von e wie folgt: Ein solcher Kreis muß durch die beiden gerichteten Kanten in G(x) verlaufen. Setzt sich der Kreis auf einer Seite o.B.d.A über den mit x_{1} benannten Knoten fort, so muß er dies auch auf der anderen Seite tun, da er sonst eine Sehne von x_{1} nach \overline{x_{1}} hätte. Damit ist ausgeschlossen, daß der Kreis durch einen mit \overline{x_{1}} benannten Knoten verlaufen kann und das bisher beschriebene Kreisstück muß auf beiden Seiten entweder durch x_{2} nach \overline{x_{2}} fortgestzt werden. Hier wiederholt sich die Argumentation und allgemein gilt für alle 1 ≤ i ≤ m, daß der Kreis entweder nicht durch mit x_{i} oder nicht durch mit \overline{x_{i}} benannte Knoten verlaufen kann. Da das Kreisstück durch G(e) für alle Klauseln durch einen mit einer darin vorkommenden Variablen benannten Knoten gehen muß, erfüllt die entsprechende Belegung alle Klauseln von e. Beispiel: Sei e = ((z ∨ y) ∧ (\overline{z} ∨ \overline{y}), so ergibt sich der folgende Graph:

[figure: \overline{y}; \overline{z}; y; z; z; \overline{z}; y; \overline{y}; \overline{y}; \overline{z}; y; z]

Analog zu einem anderen Resultat in [DOR94] ist es Σ_{2}^{P} -vollständigzu entscheiden, ob die Richtung von asymmetrischen Kanten so verändert werden kann, daß die Synchronisation zweier Halbspuren immer eine Halbspur ist, wenn sie nicht leer ist:

Theorem 4.9 Das folgende Problem ist Σ_{2}^{P} -vollständig: Gegeben zwei Abhängigkeitsalphabete (A, D) und (A, D′) mit D′ ⊆ D. Gibt es ein SC mit D = {(a, b) ∈ A × A | ab ⟹ ba ∉ SC ∩ SC^{−1}} und D′ = {(a, b) ∈ A × A | ab ⟹ ba ∉ SC ∪ SC^{−1}} und ∀u, v ∈ A^{∗}∃w ∈ A^{∗} mit [u⟩ ∥ [v⟩ = [w⟩ oder = ∅?

Beweis: Durch Raten von SC und eine Frage an ein co-NP-Orakel entsprechend dem letzten Theorem kann das Problem in Σ_{2}^{P} entschieden werden. Da, wie aus dem Beweis von Theorem 4.7 zu sehen ist, die Richtung der meisten Kanten in einem sehr großen Kreis die Bedingung nicht beeinflusst, kann in diesem Fall nicht die gleiche Graphkonstruktion wie in [DOR94] zum Beweis der Härte verwendet werden. Daher verwenden wir nun eine andere Konstruktion, welche Gebrauch von der Richtung erlaubter Sehnen im Kreis macht. Nach [Sto77], [Wra77]) ist die Allgemeingültigkeit beschränkt quantifizierter Boolescher Formeln in konjunktiver 3-Normalform vollständig für die Klasse Π_{2}^{P} = Co − Σ_{2}^{P}. Wir werden nun diese auf das Problem reduzieren.

Gegeben sei die Formel f = ∀x_{1}, …, x_{k}∃x_{k+1}, …, x_{m} e =

∀x_{1}, …, x_{k}∃x_{k+1}, …, x_{m}(c_{1} ∧ … ∧ c_{n}).

Zunächst konstruieren wir einen Graphen G(x) mit x = (x_{1}, ..., x_{m}) wie im folgendem Bild:

[figure: .; .; .; .; .; .; .; .; .; .; .; .; \overline{x_{m}}; \overline{x_{2}}; \overline{x_{1}}; x_{1}; x_{2}; x_{m}; x_{m}; x_{2}; x_{1}; \overline{x_{1}}; \overline{x_{2}}; \overline{x_{m}}; l_{m}; r_{m}]

Die mit Pfeilen dargestellten Kanten sind die zu richtenden Kanten in D \ D′. Das ’Herzstück’ von G(x) besteht aus zwei Knoten, welche auf 3 Wegen mit Zwischenknoten über jeweils zwei zu richtende Kanten verbunden sind. Sind in zwei der Verbindungen alle Kanten gleichgerichtet oder sind in zwei der Verbindungen je zwei verschieden gerichtete Kanten, so wird durch diese bereits ein Kreis ohne Sehnen mit zwei gerichteten Kanten in jeder Richtung gebildet. Interessant ist daher nur der Fall, daß wie im obigem Bild eine der Verbindungen Kanten in verschiedener Richtung besitzt, eine der Verbindungen Kanten in der einen Richtung besitzt und eine der Verbindungen Kanten in der anderen Richtung besitzt. Die Aufgabe des Restes von G(x) ist es wie im vorangehenden Beweis unbeabsichtigte Kreise zu verhindern und damit eine eindeutige Entsprechung von Kreisen und Belegungen herzustellen. Ein Graph mit G(x) und einer dazu identischen Kopie G(x)′ läßt genau dann die Konstruktion des Semikommutationssystems SC mit der gewünschten Eigenschaft nicht zu, wenn zu jeder Ausrichtung der Kanten in D \ D′ ein Kreis wie im folgendem Bild existiert, bei dem alle Sehnen in gleicher Weise gerichtet sind.

[figure: G(x); G(x)′]

Für die andere Richtung einer Kante muß der Kreis einen anderen Weg nehmen, wie z.B. folgendes Bild zeigt:

[figure: G(x); G(x)′]

Um die Richtung der Kante mit der Variablenbelegung zu koppeln konstruieren wir für alle 1 ≤ i ≤ k folgenden Graphen G(x_{i}) durch welchen 2 Kreisstücke verlaufen:

[figure: .; .; .; .; .; .; .; .; .; .; .; .; \overline{x_{i−1}}; \overline{x_{i+1}}; \overline{x_{i}}; \overline{x_{i}}; \overline{x_{i+1}}; \overline{x_{i−1}}; x_{i−1}; x_{i+1}; x_{i}; x_{i}; x_{i+1}; x_{i−1}; l′_{i}; r′_{i}; δ_{i}; .; .; .; .; .; .; .; .; .; .; .; .; \overline{x_{i−1}}; \overline{x_{i+1}}; \overline{x_{i}}; \overline{x_{i}}; \overline{x_{i+1}}; \overline{x_{i−1}}; x_{i−1}; x_{i+1}; x_{i}; x_{i}; x_{i+1}; x_{i−1}; l_{i}; r_{i}]

Die Indizes werden dabei molulo m betrachtet. Wie zuvor gilt für alle 1 ≤ j ≤ m, daß der Kreis entweder nicht durch mit x_{j} oder nicht durch mit \overline{x_{j}} benannte Knoten verlaufen kann. Die Richtung der Sehne δ_{i} hängt davon ab, ob der Kreis durch x_{i} oder durch \overline{x_{i}} verläuft. Den gesamten Graphen für f, welcher die Form

[figure: G(x); G(x)′; G(e); δ_{k+1}; G(x_{1}); G(x_{2}); G(x_{k}); …; …]

mit G(e) wie im vorherigen Beweis hat, erhalten wir durch disjunkte Vereinigung

G(x) ˙∪ G(x)′ ˙∪ G(e) ˙∪ G(x_{1}) ˙∪ … ˙∪ G(x_{k})

der Graphen, durch Hinzufügen einer weiteren zu richtenden Kante δ_{k+1} mit zwei zusätzlchen Knoten und von symmetrischen Verbindungskanten vom Endpunkt von δ_{k+1} nach r_{k} und nach l′_{m}, vom Anfangspunkt von δ_{k+1} nach r′_{k} und nach r′_{m}, für alle 1 ≤ i < k von r_{i} nach l_{i+1} und von r′_{i} nach l′_{i+1}, von r_{m} nach l_{1}, von r′ nach l′_{1} und von l_{m} nach l′. Weiterhin werden wie im vorherigen Beweis für alle 1 ≤ i ≤ m alle mit x_{i} benannten Knoten mit allen mit \overline{x_{i}} benannten Knoten verbunden und dadurch unbeabsichtigte Kreise verhindert.

Für jede Orientierung der gerichteten Kanten wird für alle 1 ≤ i ≤ k die Variable x_{i} als ’wahr’, wenn δ_{i} und δ_{k+1} die gleiche Richtung haben und ansonsten als ’falsch’ belegt. Ist die Formel f wahr, so kann für jede Orientierung der gerichteten Kanten die dadurch bestimmte Belegung der Varaiablen x_{1}, ..., x_{k} zu einer erfüllenden Belegung von e erweitert werden und somit existiert der Kreis, bei dem alle Sehnen in gleicher Weise gerichtet sind. Umgekehrt folgt daraus, daß bei allen Orientierungen der zu richtenden Kanten ein Kreis existiert, bei dem alle Sehnen in gleicher Weise gerichtet sind, daß jede Belegung der Varaiablen x_{1}, ..., x_{k} zu einer dem Kreis entsprechenden erfüllenden Belegung von e erweitert werden kann und damit f wahr ist.

Bemerkung: Gegeben 2m Abhängigkeitsalphabete (A_{i}, D_{i}) und (A_{i}, D′_{i}) mit D′_{i} ⊆ D_{i} für alle 0 < i ≤ m. Es ist leicht zu sehen, daß genau dann Semikommutationssysteme SC_{i} mit

\begin{matrix}D_{i} = \{(a, b) ∈ A_{i} × A_{i} | ab ⟹ ba ∉ SC_{i} ∩ SC_{i}^{−1}\} und \\ D′_{i} = \{(a, b) ∈ A_{i} × A_{i} | ab ⟹ ba ∉ SC_{i} ∪ SC_{i}^{−1}\} \end{matrix}

für 0 < i ≤ m und ∀u_{1} ∈ A_{1}^{∗}, … u_{m} ∈ A_{m}^{∗}

(∀i, j ≤ m∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a}) ⇒ [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} ≠ ∅

existieren, wenn gilt:

\begin{matrix}¬∃1 < k, i ≠ j, C = \{(x_{1}, x_{2}), … (x_{k−1}, x_{k}), (x_{k}, x_{1})\} mit \\ C ⊆ ⋃_{l} D′_{l} ∪ \{(x_{k}, x_{1})\} ∧ (x_{k}, x_{1}) ∈ ⋃_{l} D_{l} ∧ C ∩ D_{i} ≠ ∅ ∧ C ∩ D_{j} ≠ ∅. \end{matrix}

Dies bedeutet, daß die Richtung von asymmetrischen Kanten so verändert werden kann, daß Halbspuren, deren Buchstabenzahlen auf der Schnittmenge übereinstimmen, immer synchronisierbar sind, d.h. die Richtung von asymmetrischen Kanten so verändert werden kann, daß kein gerichteter Kreis, der sich aus Kanten aus mindestens zwei der Abhängigkeitsgraphen zusammensetzt, existiert, gdw. kein solcher Kreis existiert, in dem höchstens eine der Kanten asymmetrisch ist. Die Eigenschaft liegt somit in NLOGSPACE.

4.4 Das lokale Überprüfen der Synchronisierbarkeit von Halbspuren

In [DV89] wird eine leicht zu überprüfende (T C^{0}), notwendige Bedingung für die Synchronisierbarkeit von Spuren beschrieben und es wird ein Kriterium angegeben, mit dessen Hilfe für Abhängigkeitsalphabete entschieden werden kann, ob diese Bedingung auch hinreichend ist. Dieses Kriterium nennt man die local checking property. Sie ist co-NP-vollständig[DOR94]. Das gleiche machen wir nun für Halbspuren. Falls die zwei Halbspuren [u_{1}⟩_{1}, [u_{2}⟩_{2} synchronisierbar sind, so gilt Π_{A_{1}∩A_{2}}^{A_{1}}(u_{1}) ⟹_{SC′}^{∗} Π_{A_{1}∩A_{2}}^{A_{2}}(u_{2}) für das Semikommutationssystem SC′ mit

SD′ = SD_{1} ∩ SD_{2}^{−1}. Gemäß Theorem 4.1 liegt das Überprüfen dieser Bedingung in T C^{0}.

Lemma 4.1 Die Bedingung ist hinreichend, falls die Komposition der Semikommutationssysteme SC_{1} und SC_{2}^{−1} ein Semikommutationssystem ist, dies bedeutet f_{SC_{1}} ∘ f_{SC_{2}^{−1}} = f_{SC′} für ein Semikommutationssystem SC′.

Beweis: Wenn die Komposition der Semikommutationssysteme SC_{1} und SC_{2}^{−1} ein Semikommutationssystem ist, so ist deren Komposition SC bestimmt durch

SD′ = SD_{1} ∩ SD_{2}^{−1}. Sei A_{1} ˙∪{a_{1}, … a_{n}} = A_{2} ˙∪{b_{1}, … b_{m}}. Falls Π_{A_{1}∩A_{2}}^{A_{1}}(u_{1}) ⟹_{SC′}^{∗}

Π_{A_{1}∩A_{2}}^{A_{2}}(u_{2}) so gilt auch u_{1}a_{1}^{|u_{2}|_{a_{1}}} … a_{n}^{|u_{2}|_{an}} ⟹_{SC′}^{∗} u_{2}b_{1}^{|u_{1}|_{b_{1}}} … b_{m}^{|u_{1}|_{bm}}, da

(A_{1} × {a_{1}, … a_{n}}) ∩ SD_{1} = ∅ und (A_{2} × {b_{1}, … b_{m}}) ∩ SD_{2} = ∅, und damit die jeweils nicht vorkommenden Buchstaben unabhängig sind, also gilt auch

u_{1}a_{1}^{|u_{2}|_{a_{1}}}, … a_{n}^{|u_{2}|_{an}} ⟹_{SC_{1}}^{∗} s ⟹_{SC_{2}^{−1}}^{∗} u_{2}b_{1}^{|u_{1}|_{b_{1}}}, … b_{m}^{|u_{1}|_{bm}}

und folglich ist s eine Synchronisation von [u_{1}⟩_{1} und [u_{2}⟩_{2}.

Theorem 4.10 Die local checking property für Synchronisierbarkeit von zwei Halbspuren ist co-NP-vollständig.

Beweis: Ein Kriterium dafür, ob die Komposition zweier Semikommutationssysteme ein Semikommutationssystem ist, findet sich in [RW91]. Es ist leicht zu sehen, daß dieses Kriterium in co-NP ist und da das Kriterim für Konfluenz, von welchem in [DOR94] gezeigt wurde, daß es ebenfalls co-NP-vollständig ist, ein Spezialfall davon ist, ist dieses ebenfalls co-NP-vollständig.

5 Die Synchronisation und die Maximalität von Halbspursprachen

Es ist leicht zu sehen, daß für reguläre Stringsprachen R_{1}, R_{2} die Synchronisation ebenfalls eine reguläre Sprache (mittels eines Produktautomaten) ist und die Synchronisierbarkeit daher leicht (NLOGSPACE) zu entscheiden ist. Andererseits ist bei regulären Halbspursprachen die Synchronisierbarkeitfrage d.h. f_{SC}(R_{1}) ∥ f_{SC}(R_{2}) ≠ ∅ oder die Frage f_{SC}(R_{1}) ∥ R_{2} ≠ ∅ im allgemeinen unentscheidbar. In diesem Kapitel soll nun untersucht werden, welche Eigenschaft SD (bzw. SC) haben muß, damit diese Frage entscheidbar wird. Desweiteren ist die Frage nach der Maximalität einer regulären Sprache bezüglich eines Semikommutationssystems von Interesse. Die Menge der maximalen Wörter einer Sprache L ist

max_{SC}(L) := {u ∈ L | ∀v ∈ L v ⟹_{SC}^{∗} u ⟶ u ⟹_{SC}^{∗} v}.

Es ist leicht zu sehen, daß die Frage, ob L maximal ist, d.h. ob max_{SC}(L) = L äquivalent ist zur Frage f_{SC}(L′) ∩ L = ∅ mit

L′ := {w | ∃u ∈ L u ⟹_{SC∩SC^{−1}}^{∗} v ⟹_{SC\SC^{−1}} w}.

Die Leerheit und die Unendlichkeit von Halbspursprachen sind bereits an der zugrundeliegenden regulären Sprache mit geringer Komplexität (NLOGSPACE) zu entscheiden. Auch das Wortproblem ist sowohl für ein festes Semikommutationssystem (NLOGSPACE) als auch uniform (laut [BMS82] NP-vollständig) entscheidbar. Universalität, Äquivalenz, Inklusion, Erkennbarkeit und Disjunktheit sind jedoch wie in [Iba78] und [AH89] gezeigt bereits für symmetrische Kommutationssysteme im allgemeinen unentscheidbar. Die Maximalität hingegen ist eine triviale Eigenschaft für symmetrische Kommutationssysteme. Ist SC konfluent (siehe nächstes Kapitel), so ist gemäß [RW91] die Komposition von SC und SC^{−1} ein Semikommutationssystem und damit die Frage f_{SC}(R_{1}) ∥ f_{SC}(R_{2}) ≠ ∅ äquivalent zu der Frage f_{SC∪SC^{−1}}(R_{1}) ∥ R_{2} ≠ ∅. Somit genügt es in diesem Fall die Synchronisierbarkeit einer Halbspursprache mit einer regulären Sprache zu betrachen.

5.1 Zählerhalbabhängigkeiten

In [CG90] wird gezeigt, daß sich Semikommutationssysteme mit Hilfe der Dekomposition in atomare Semikommutationssysteme zerlegen lassen. Atomare Semikommutationssysteme haben die Form \overline{SD} = A_{1} ×A_{2}. Ist |A_{1}| = 1 oder |A_{2}| = 1, so ist \overline{SD} eine atomare Zählersemikommutation, d.h. das Element in A_{1} bzw. A_{2} kann mit Hilfe eines Zählers an eine andere Stelle bewegt werden.

Definition Entsprechend der Definition von Zählersemikommutationen, welche in [Gon93] definiert wurden, ist SD eine Zählerhalbabhängigkeit (CSD), falls wenn (a, b) ∈ SD und (c, d) ∈ SD, so auch (a, d) ∈ SD und (c, b) ∈ SD.

Theorem 5.1 [Gon93] f_{SC}(MC) ⊆ MC ⇔ SD ist eine CSD.

D.h. die Multicountersprachen sind abgeschlossen unter der Hüllenbildung mit einer Zählersemikommutation. Wegen der Entscheidbarkeit des Leerheitsproblems für Multicountersprachen folgt:

Korollar 5.1 [Gon93] Ist SD ist eine CSD, so sind für reguläre Stringsprachen R_{1}, R_{2} die Fragen f_{SC}(R_{1}) ∩ R_{2} = ∅? und max_{SC}(R_{1}) = R_{1} entscheidbar.

Da die Komposition zweier CSD SD_{1} und SD_{2}^{−1} ebenfalls eine CSD ist, gilt:

Korollar 5.2 [Gon93] Sind SD_{1} und SD_{2} CSD’s, so ist für reguläre Stringsprachen R_{1}, R_{2} die Frage f_{SC_{1}}(R_{1}) ∩ f_{SD_{2}}(R_{2}) = ∅? entscheidbar.

5.2 Prioritätszählerhalbabhängigkeiten

Da wir nun mit dem Prioritätsmulticounterautomaten ein stärkeres Instrument zur Verfügung haben, definieren wir im folgenden die Prioritätszählerhalbabhängigkeiten (PCSD):

Definition Ein Relation SD ist eine PCSD, wenn sie die Eigenschaft hat, daß

die Relationen {(w, w′) | w ⟹_{SC}^{∗} w′} und {(w, w′) | w ⟹_{SC}^{∗} w′′ ⟹_{SC\SC^{−1}} w′′′ ⟹_{SC}^{∗} w′}

in P MC liegen, d.h. die Relationen können von einem Prioritätsmulticounterautomaten mit 2 Eingabebändern erkannt werden.

Durch Raten eines Wortes w in der regulären Sprache R, gleichzeitige Simulation des endlichen Automaten für R auf w und gleichzeitige Simulation des Prioritätsmulticounterautomaten für {(w, w′) | w ⟹_{SC}^{∗} w′} folgt:

Theorem 5.2 Jede PCSD SD hat die Eigenschaft, daß f_{SC}(R) und {w | ∃u ∈ R u ⟹_{SC}^{∗} w′′ ⟹_{SC\SC^{−1}} w′ ⟹_{SC}^{∗} w} für jede reguläre Stringsprache R in P MC liegen.

Korollar 5.3 Für jede PCSD SD ist für reguläre Stringsprachen R_{1}, R_{2} die Frage f_{SC}(R_{1}) ∩ R_{2} = ∅? entscheidbar.

Beweis: Wegen f_{SC}(R_{1}) ∈ P MC und der Abgeschlossenheit unter Schnitt mit regulären Sprachen existiert ein Prioritätsmulticounterautomat, der f_{SC}(R_{1})∩R_{2} erkennt und dessen Leerheitsproblem wegen Theorem 3.1 entscheidbar ist.

Korollar 5.4 Für jede PCSD SD ist für eine reguläre Stringsprache L die Frage max_{SC}(L) = L entscheidbar.

Beweis: Durch Raten eines Wortes w in der regulären Sprache L, gleichzeitige Simulation des endlichen Automaten für L auf w und gleichzeitige Simulation des Prioritätsmulticounterautomaten für {(w, w′) | w ⟹_{SC}^{∗} w′′ ⟹_{SC\SC^{−1}} w′′′ ⟹_{SC}^{∗} w′}

aus Theorem 5.2 folgt f_{SC}(L′) ∈ P MC für L′ := {w | ∃u ∈ L u ⟹_{SC∩SC^{−1}}^{∗} v ⟹_{SC\SC^{−1}}

w}. Wegen der Abgeschlossenheit unter Schnitt mit regulären Sprachen existiert ein Prioritätsmulticounterautomat, der f_{SC}(L′) ∩ L erkennt. Dessen Leerheitsproblem ist äquivalent zu der Frage max_{SC}(L) = L und ist wegen Theorem 3.1 entscheidbar.

Bemerkung: Beim Beweis jeder der folgenden hinreichenden Bedingungen für PCSD’s können wir uns o.B.d.A auf das Erkennen der Relation {(w, w′) | w ⟹_{SC}^{∗} w′} beschränken. Beweis: Es existiert, wie für jede der folgenden hinreichenden Bedingungen für PCSD’s gezeigt wird, ein Prioritätsmulticounterautomat für die Sprache {(w, w′) | w ⟹_{SC}^{∗} w′}, der für jedes Zeichen a zu jeder Zeit die Differenz der bisher gelesenen Vorkommen von a in w und w′ durch Zählerinhalte repräsentiert.

Um {(w, w′) | w ⟹_{SC}^{∗} w′′ ⟹_{SC\SC^{−1}} w′′′ ⟹_{SC}^{∗} w′} zu erkennen, wird die Anzahl der

Zustände dieses Prioritätsmulticounterautomat verdoppelt. Nur wenn eine asymmetrische Vertauschung stattfindet, kann von der ersten Hälfte der Zustände in die zweite Hälfte übergegangen und nur dort später akzeptiert werden. Das Auftreten einer asymmetrischen Vertauschung kann, wie bei der weiteren Konstruktion ersichtlich, durch das Überprüfen eines Zählers auf ≠ 0 festgestellt werden.

Korollar 5.5 Jede CSD ist eine PCSD.

Beispiel: Betrachten wir das folgende Halbabhängigkeitsalphabet SD:

[figure: a; b; c; d]

Es ist die Komposition der beiden atomaren Zählerhalbabhängigkeiten

[figure: a; b; c; d; und; a; b; c; d]

und die Relation {(w, w′) | w ⟹_{SC}^{∗} w′} kann von folgendem Prioritätsmulticounterautomaten erkannt werden:

[figure: (a, a, 0, 0, 0); (b, b, 0, 0, 0); (c, λ, 0, 1, 0); (λ, c, 0, −1, 0); (d, λ, 0, 0, 1); (λ, d, 0, 0, −1); z_{0}; (λ, λ, 2, 0, 0); z_{e}]

Die erste Stelle der die Übergänge beschreibenden Tupel bezeichnet das gelesene Zeichen des ersten Eingabebandes, die zweite Stelle der Tupel bezeichnet das gelesene Zeichen des zweiten Eingabebandes, die dritte Stelle gibt die Zahl der auf Null getesteten Zähler an und alle weiteren Stellen bezeichnen die Veränderung der Zählerinhalte. Der angegebene Automat zählt die nach vorne bewegten c’s bzw. d’s in Zähler 1 bzw. 2; a’s und b’s können nur simultan auf beiden Bändern gelesen werden. Der Automat kann nur akzeptieren, wenn beide Zähler durch den Nulltest kommen (2 in dritter Stelle). Der Automat akzeptiert z.B. (cdabdc, abdccd), nicht aber (ac, ca).

Um {(w, w′) | w ⟹_{SC}^{∗} w′′ ⟹_{SC\SC^{−1}} w′′′ ⟹_{SC}^{∗} w′} zu erkennen muß während einem

simultanen Lesen von a oder b auf beiden Eingabebändern sichergestellt sein, daß einer der beiden Zähler nicht Null enthält, dies geschieht durch dekrementieren und anschließendes Inkrementieren in folgendem Automaten:

[figure: (a, a, 0, 0, 0); (b, b, 0, 0, 0); (c, λ, 0, 1, 0); (λ, c, 0, −1, 0); (d, λ, 0, 0, 1); (λ, d, 0, 0, −1); z_{0}; (a, a, 0, 0, −1); (b, b, 0, 0, −1); (λ, λ, 0, 0, 1); (a, a, 0, −1, 0); (b, b, 0, −1, 0); (λ, λ, 0, 1, 0); z_{1}; z_{2}; (a, a, 0, 0, 0); (b, b, 0, 0, 0); (c, λ, 0, 1, 0); (λ, c, 0, −1, 0); (d, λ, 0, 0, 1); (λ, d, 0, 0, −1); z_{3}; (λ, λ, 2, 0, 0); z_{e}]

Der Automat akzeptiert z.B. (acdcb, adcbc), nicht aber (acdcb, adccb).

Theorem 5.3 Ist SD eine PCSD über dem Alphabet A, so auch über A′ ⊇ A.

Beweis: Jeder zusätzliche Buchstabe in A′ \A kann mit allen anderen Buchstaben kommutieren. Zu diesem Zweck werden jeweils 2 zusätzliche Zähler verwendet, mit deren Hilfe die Differenz der Anzahl der Vorkommen dieser Buchstaben in den bisher gelesenen Präfixen von w und w′ gemerkt wird. Diese Zähler müssen nie zwischendurch auf 0 getestet werden. Beispiel: Betrachten wir das folgende Halbabhängigkeitsalphabet SD:

[figure: a; b; c; d; e; f]

Die Relation {(w, w′) | w ⟹_{SC}^{∗} w′} kann nun von folgendem Prioritätsmulticounterautomaten erkannt werden:

[figure: (a, a, 0, 0, 0, 0, 0, 0, 0); (b, b, 0, 0, 0, 0, 0, 0, 0); (c, λ, 0, 1, 0, 0, 0, 0, 0); (λ, c, 0, −1, 0, 0, 0, 0, 0); (d, λ, 0, 0, 1, 0, 0, 0, 0); (λ, d, 0, 0, −1, 0, 0, 0, 0); (λ, e, 0, 0, 0, 1, 0, 0, 0); (e, λ, 0, 0, 0, 0, 1, 0, 0); (λ, λ, 0, 0, 0, −1, −1, 0, 0); (λ, f, 0, 0, 0, 0, 0, 1, 0); (f, λ, 0, 0, 0, 0, 0, 0, 1); (λ, λ, 0, 0, 0, 0, 0, −1, −1); z_{0}; (λ, λ, 6, 0, 0, 0, 0, 0, 0); z_{e}]

Theorem 5.4 Seien SD_{1} und SD_{2} PCSD’s über den disjunkten Alphabeten A_{1} und A_{2}, so ist auch SD = SD_{1} ∪ SD_{2} ∪ A_{1} × A_{2} ∪ A_{2} × A_{1} über A = A_{1} ∪ A_{2} eine PCSD.

Beweis: Ein Prioritätsmulticounterautomat simuliert auf A_{1} den Prioritätsmulticounterautomaten für SD_{1} und auf A_{2} den Prioritätsmulticounterautomaten für SD_{2}. Beim Übergang zwischen diesen Simulationen werden alle Zähler auf 0 getestet. Beispiel: Betrachten wir das folgende Halbabhängigkeitsalphabet SD:

[figure: a; b; c; d]

Der Prioritätsmulticounterautomat, der die Relation {(w, w′) | w ⟹_{SC}^{∗} w′} erkennt, setzt sich aus dem Automaten für SD_{0} = {(a, c)}, der die Zustände z_{0} und z_{e} besitzt, und dem Automaten für SD_{1} = {(b, d)}, der die Zustände z_{1} und z_{e} besitzt, zusammen:

[figure: (a, a, 0, 0); (c, λ, 0, 1); (λ, c, 0, −1); z_{0}; (λ, λ, 1, 0); (λ, λ, 1, 0); z_{e}; (λ, λ, 1, 0); (λ, λ, 1, 0); z_{1}; (b, b, 0, 0); (d, λ, 0, 1); (λ, d, 0, −1)]

Die Sprache L = c^{∗}a(d^{∗}bc^{∗}a)^{∗} wird vom endlichen Automaten

[figure: c; z_{0}; a; b; z_{e}; d]

erkannt. Die Sprache f_{SC}(L) = c^{∗}ac^{∗}(d^{∗}bd^{∗}c^{∗}ac^{∗})^{∗} wird von folgendem Prioritätsmulticounterautomaten gemäß Theorem 5.2 erkannt, welcher beide Automaten auf dem gleichen geratenen Eingabewort w simuliert, wodurch das zweite Eingabeband des simulierten Prioritätsmulticounterautomaten zum einzigen Eingabeband wird und die erste Komponente der Übergangstripel wegfällt.

[figure: (a, 0, 0); (c, 0, −1); z_{0}; (λ, 1, 0); (λ, 1, 0); z_{e}; (λ, 1, 0); (λ, 1, 0); z_{1}; (b, 0, 0); (λ, 0, 1); (d, 0, −1); (λ, 0, 1); (c, 0, −1); z_{0}; (λ, 1, 0); (λ, 1, 0); z_{e}; (λ, 1, 0); (λ, 1, 0); z_{1}; (d, 0, −1)]

Mit den soweit charakerisierten PCSD und Theorem 5.14 erhalten wir bereits einen alternativen Beweis für folgendes Resultat in [AH89]:

Theorem 5.5 [AH89] Für ein symmetrisches Kommutationssystem C ist die Frage f_{C}(R_{1}) ∩ f_{C}(R_{2}) = ∅? für reguläre Sprachen R_{i} genau dann entscheidbar, wenn \overline{D} diagonal ist, d.h. sind (a, b), (b, c) und (c, d) in \overline{D}, so sind auch (a, c) oder (b, d) in \overline{D}.

Beweis: Nach [Wol65] ist ein Graph genau dann diagonal, wenn er ein transitiver Wald ist, d.h. er entsteht aus einem Wald durch (transitives) Hinzufügen von Kanten von allen Knoten zu allen ihren Vorgängerknoten. Ein solcher transitiver Wald ist entweder nicht zusammenhängend (d.h. er enthält mehrere transitive Bäume) oder er besteht nur aus einem einzigen transitiven Baum, dessen Wurzelknoten mit allen anderen Knoten (welche ebenfalls einen transitiven Wald bilden) verbunden ist. Ist also \overline{D} diagonal und somit ein transitiver Wald, so ist entweder \overline{D} nicht zusammenhängend oder D enthält einen isolierten Knoten. Daraus läßt sich erkennen, daß D entweder wegen Theorem 5.4 (falls \overline{D} nicht zusammenhängend ist) oder wegen Theorem 5.3 (falls D einen isolierten Knoten enthält) eine PCSD ist. Ist \overline{D} nicht diagonal, so besitzt D einen induzierten Teilgraphen der Form • — • — • — • oder der Form • — • • — •. Aufgrund der Unentscheidbarkeitsbedingung 1 in Theorem 5.14 ist die Frage f_{C}(R_{1}) ∩ R_{2} = ∅? und somit die Frage f_{C}(R_{1}) ∩ f_{C}(R_{2}) = ∅? für reguläre Sprachen R_{i} in diesem Fall unentscheidbar.

Bemerkung: Nach [Wol65] gilt also für jeden nichtleeren, symmetrischen Graphen D:

1. \overline{D} ist nicht zusammenhängend oder

2. D enthält einen induzierten Teilgraphen der Form • — • — • — • oder

3. D enthält einen induzierten Teilgraphen der Form • — • • — • oder

4. D enthält einen isolierten Knoten.

In [Sei74] und unabhängig davon in [Teo93] wird gezeigt, daß die Graphen, die keinen induzierten Teilgraphen der Form • — • • — • besitzen, gerade die Cographen sind, d.h. die Graphen, die nur aus einem Einzelknotnen bestehen oder durch Komplementbildung und disjunkte Vereinigung anderer Cographen gebildet werden können. Somit gilt für jeden nichtleeren, symmetrischen Graphen D:

1. \overline{D} ist nicht zusammenhängend oder

2. D enthält einen induzierten Teilgraphen der Form • — • — • — • oder

3. D ist nicht zusammenhängend oder

4. D besteht aus einem einzigen Knoten.

Es ist leicht zu sehen, daß die beiden Resultate direkt auseinander folgen: Enthält D einen induzierten Teilgraphen der Form • — • • — •, so ist D entweder nicht zusammenhängend oder mit der kürzesten Verbindung wird ein induzierter Teilgraph der Form • — • — • — • gebildet. Enthält D einen isolierten Knoten, so ist D nicht zusammenhängend oder besteht aus einem einzigen Knoten. Ist \overline{D} nicht zusammenhängend, so enthält D einen isolierten Knoten oder die Zusammenhangskomponenten (mindestes zwei) sind größer und somit enthält D einen induzierten Teilgraphen der Form • — • • — •.

Wir wollen nun noch weitere PCSD’s finden. Leider sind die PCSD’s nicht unter der gleichen Komposition wie allgemeine Semikommutationssysteme abgeschlossen, wie folgendes Beispiel zeigt: Die Komposition der beiden PCSD’s

[figure: a; b; c; d; und; a; b; c; d; ist; a; b; c; d]

und nach Theorem 5.9 keine PCSD. Aus diesem Grund definieren wir nun eine Verschärfung der Kompositionsbedingung in [RW91]:

Definition SD = SD_{1} ∩ SD_{2} ist die starke Komposition von SD_{1} und SD_{2} über dem Alphabet A, wenn ∀w, w′ mit w′ ∈ f_{SC}(w) ∃w_{1}...w_{n} = w, w′_{1}...w′_{n} = w′ ∀i ≤ n w′_{i} ∈ f_{SC_{1}}(w_{i}) ∨ w′_{i} ∈ f_{SC_{2}}(w_{i}).

w = w′ =  w_{1} w′1  w_{2} w′2  w_{3} w′3  ... ...  w_{n} w′n

Theorem 5.6 SD = SD_{1} ∩ SD_{2} ist die starke Komposition von SD_{1} und SD_{2} über dem Alphabet A, gdw ¬∃x_{1}, x′_{1}, ...x_{n}, x′_{n} ∈ A ((x_{1}, x′_{1}) ∈ SD_{1}\SD_{2}∨(x_{2}, x′_{1}) ∈ SD_{1} \SD_{2})∧((x_{n}, x′_{n}) ∈ SD_{2} \SD_{1} ∨(x_{n}, x′_{n−1}) ∉ SD_{2} \SD_{1})∧∀i < n ((x_{i}, x′_{i}) ∉ SD ∧ (x_{i+1}, x′_{i}) ∉ SD).

Beweis: Müssen zwei Paare (x_{1}, x′_{1}) bzw.(x_{2}, x′_{1}) und (x_{n}, x′_{n}) bzw.(x_{n}, x′_{n−1}) in verschieden Semikommutationssysteme abgeleitet werden, so ist das dann und nur dann möglich, wenn keine Verschränkung der folgenden Art vorliegt:

[figure: w =; w′ =; x_{1}; x_{1}; x′_{1}; x′_{1}; x_{2}; x_{2}; x′_{2}; x′_{2}; x_{3}; x_{3}; ...; ...; x′_{n−1}; x′_{n−1}; x_{n}; x_{n}; x′_{n}; x′_{n}]

Korollar 5.6 SD = SD_{1} ∩ SD_{2} ist die starke Komposition von SD_{1} und SD_{2} über dem Alphabet A, wenn ∀a, b, c ∈ A (a, b) ∈ SD_{1} ∨ ((a, c) ∈ SD_{2} ∧ (c, b) ∈ SD_{2}).

Theorem 5.7 Seien SD_{1} und SD_{2} PCSD’s über dem Alphabet A, so ist auch die starke Komposition von SD_{1} und SD_{2} über dem Alphabet A (falls diese existiert) eine PCSD.

Beweis: Ein Prioritätsmulticounterautomat simuliert nichtdeterministisch entweder den Prioritätsmulticounterautomaten für SD_{1} oder den Prioritätsmulticounterautomaten für SD_{2}. Beim Übergang zwischen den Simulationen werden alle Zähler auf 0 getestet. Beispiel: Betrachten wir das folgende Halbabhängigkeitsalphabet SD:

[figure: a; b; c; d]

Es ist die starke Komposition der beiden PCSD’s

[figure: SD_{1} :=; a; b; c; d; und; a; b; c; d; =: SD_{0}]

Der Prioritätsmulticounterautomat, der die Relation {(w, w′) | w ⟹_{SC}^{∗} w′} erkennt, setzt sich wieder aus den Automaten für SD_{1} und SD_{2} zusammen:

[figure: (b, b, 1, 0); (d, d, 0, 0); (a, a, 0, 0); (c, λ, 0, 1); (λ, c, 0, −1); z_{0}; (λ, λ, 1, 0); (λ, λ, 1, 0); z_{e}; (λ, λ, 1, 0); (λ, λ, 1, 0); z_{1}; (a, a, 1, 0); (c, c, 0, 0); (b, b, 0, 0); (d, λ, 0, 1); (λ, d, 0, −1)]

5.2.1 Hinreichendes Kriterium

Auch mit der starken Komposition werden noch nicht alle PCSD’s erfasst, da dabei nicht die Möglichkeit besteht den Inhalt eines Zählers, der in beiden Simulationen die gleiche Aufgabe erfüllt, beizubehalten. Eine allgemeinere Definition, welche dies ermöglicht, ist folgende:

Theorem 5.8 Eine Relation SD über dem Alphabet A ist eine PCSD, wenn

∃ s ∈ ℕ, C_{1}, B_{1}, D_{1}, ..., C_{s}, B_{s}, D_{s} ⊆ A und g ∈ ℕ^{{l,r}×A} injektiv

mit \overline{SD} = ⋃_{i≤s} \overline{SD_{i}} mit

∀i ≤ s \overline{SD_{i}} = (C_{i} × B_{i} ∪ D_{i} × C_{i}) \ id_{A} und B_{i} ∪ D_{i} ⊆ C_{i} und ∀i, j ≤ s ∀b ∈ B_{i} \ B_{j}, d ∈ D_{i} \ D_{j}, a ∈ B_{i} ∩ B_{j}, e ∈ D_{i} ∩ D_{j}

⟶ max(g(l, b), g(r, d)) < min(g(l, a), g(r, e)) und

∀b, d, e ∈ A (d, b) ∈ \overline{SD_{i}} ∧ (d, e) ∈ \overline{SD_{j}}
⟶ d ∈ D_{i} ∩ D_{j} ∨ b, e ∈ B_{i} ∩ B_{j} und
∀d, b, e ∈ A (d, b) ∈ \overline{SD_{i}} ∧ (e, b) ∈ \overline{SD_{j}}
⟶ d, e ∈ D_{i} ∩ D_{j} ∨ b ∈ B_{i} ∩ B_{j}.

Beweis: Anschaulich gesehen ist klar: Wenn ein w ∈ A^{∗} abgeleitet werden kann zu w^{R}, so müssen alle dabei beteiligten Kommutationen in einem \overline{SD_{i}} liegen. Dies sagt folgender Hilfssatz: Hilfssatz: Für jede geordnete Menge {a_{1}, ..., a_{n}} mit

S(a_{1}, ..., a_{n}) := \{(a_{i}, a_{j}) | i < j ≤ n\} ⊆ \overline{SD}

existiert ein Index i ≤ s mit S(a_{1}, ..., a_{n}) ⊆ \overline{SD_{i}}. Der Beweis durch Induktion: Die Behauptung ist klar für ∅, {a_{1}}, {a_{1}, a_{2}}. Sei

I := \{i ≤ s | ∃j < n (a_{j}, a_{n}) ∈ \overline{SD_{i}}\},

so folgt aus

\{a_{1}...a_{n−1}\} × \{a_{n}\} ⊆ ⋃_{i∈I} \overline{SD_{i}}

entweder ∀i ∈ I a_{n} ∈ B_{i} oder ∃i ∈ I a_{n} ∉ B_{i}, woraus wegen

∀a_{j}, a_{n} mit j, k < n ∀l ∈ I (a_{j}, a_{n}) ∈ \overline{SD_{l}} ∧ (a_{k}, a_{n}) ∈ \overline{SD_{i}}
⟶ a_{j}, a_{k} ∈ D_{l} ∩ D_{i} ∨ a_{n} ∈ B_{l} ∩ B_{i}

∃i ∈ I {a_{1}...a_{n−1}} ⊆ D_{i} ∧ a_{n} ∈ C_{i} folgt. Im zweiten Fall ist die Behauptung bereits erfüllt. Im ersten Fall gilt mit analoger Argumentation ∀i ∈ I′ a_{1} ∈ D_{i} mit I′ := \{i ≤ s | ∃1 < j ≤ n (a_{1}, a_{j}) ∈ \overline{SD_{i}}\}. Daher existiert ein i_{0} ∈ I ∩ I′ mit a_{1} ∈ D_{i_{0}} und a_{n} ∈ B_{i_{0}}. Nach Induktion existiert ein j (∈ I) mit S(a_{2}, ..., a_{n}) ⊆ \overline{SD_{j}} und ein k (∈ I′) mit S(a_{1}, ..., a_{n−1}) ⊆ \overline{SD_{k}}. Sei

m := min{l | 2 ≤ l ≤ n − 1, a_{l} ∉ D_{j} ∩ D_{k}},

so folgt daraus für alle m′ mit m < m′ < n wegen (a_{m}, a_{m′}) ∈ \overline{SD_{j}} ∩ \overline{SD_{k}}, daß m′ ∈ B_{j} ∩ B_{k}. Es gilt also

a_{2}, ..., a_{m−1} ∈ D_{j} ∩ D_{k} und a_{m+1}, ..., a_{n−1} ∈ B_{j} ∩ B_{k}

und außerdem gilt a_{1} ∈ D_{k} und a_{n} ∈ B_{j}. Sei o.B.d.A. g(r, a_{1}) > g(l, a_{n}). Es muß ein h ∈ I existieren mit a_{n} ∈ B_{h} und a_{m} ∈ C_{h}. Wäre a_{1} ∈ D_{i_{0}} \ D_{h}, so würde nach Definition aus a_{n} ∈ B_{i_{0}} ∩ B_{h} die falsche Ungleichung g(r, a_{1}) < g(l, a_{n}) folgen. Folglich muß auch a_{1} ∈ D_{h} gelten. Existiert ein a_{p} ∈ D_{k} \ D_{h} mit 2 ≤ p ≤ m − 1, so gilt wegen a_{1} ∈ D_{k} ∩ D_{h} die Ungleichung g(r, a_{1}) > g(r, a_{p}) und somit ist a_{1} ∈ D_{j} (sonst würde aus a_{1} ∈ D_{k} \ D_{j} und a_{p} ∈ D_{k} ∩ D_{j} wieder die gegenteilige Ungleichung gelten) und j ist der gesuchte Index i des Hilfssatzes. Existiert ein a_{p} ∉ B_{h} mit m + 1 ≤ p ≤ n − 1, so gilt analog dazu g(l, a_{n}) < g(l, a_{p}) und somit ist a_{n} ∈ B_{k} und k ist der gesuchte Index i des Hilfssatzes. Ansonsten ist h der gesuchte Index i des Hilfssatzes. □

Ein Prioritätsmulticounterautomat M mit s Zuständen und max{g(x, a) | x ∈ {l, r}, a ∈ A} Zählern erkennt {(w, w′) | w ⟹_{SC}^{∗} w′} wie folgt: Befindet sich M im Zustand q_{i} und hat M den Präfix v von w und den Präfix v′ von w′ gelesen, so dürfen nur die Zähler mit den Nummern g(l, b) und g(r, d) für alle b ∈ B_{i} und d ∈ D_{i} einen Wert c(g(l, b)) bzw. c(g(r, d)) größer als 0 haben (alle anderen müssen den Wert 0 haben) und es gilt

∀a ∈ A |v|_{a} + c(g(l, a)) = |v′|_{a} + c(g(r, a))

. Im Zähler g(l, a) wird also die Anzahl der sich nach links bewegenden a’s gezählt. Die Zählerinhalte c(g(l, a)) und c(g(r, a)) können jederzeit simultan dekrementiert werden.

Geht M in den Zustand q_{j} über, so müssen dabei alle Zähler mit Nummern aus

{g(l, b) | b ∈ B_{i} \ B_{j}} ∪ {g(r, d) | d ∈ D_{i} \ D_{j}}

auf 0 getestet werden, was möglich ist, weil diese Zählernummern gemäß Definition kleiner als die in

{g(l, b) | b ∈ B_{i} ∩ B_{j}} ∪ {g(r, d) | d ∈ D_{i} ∩ D_{j})

sind. Sind alle Zähler 0, so kann der Automat die gelesene Eingabe akzeptieren. A kann im Zustand q_{i} ein Zeichen d ∈ D_{i} auf dem ersten Eingabeband überlesen und dabei c(g(r, d)) inkrementieren oder ein Zeichen b ∈ B_{i} auf dem zweiten Eingabeband überlesen und dabei c(g(l, b)) inkrementieren oder ein Zeichen b ∈ B_{i} auf dem ersten Eingabeband überlesen und dabei c(g(l, b)) dekrementieren oder ein Zeichen d ∈ D_{i} auf dem zweiten Eingabeband überlesen und dabei c(g(r, d)) dekrementieren oder ein Zeichen c ∈ C_{i} simultan auf beiden Eingabebändern überlesen. Damit wird garantiert, daß A nur solche Paare w, w′ akzeptiert, bei denen bei der Ableitung von w nach w′ Zeichen in einem D_{i} bzw. B_{i} nur über solche Zeichen nach vorne bzw. nach hinten vertauscht wurden, mit denen sie nicht abhängig sind. Es ist nun noch zu zeigen, daß w′ nicht von w abgeleitet werden kann, wenn M zwischendurch nicht weiterlesen kann. Sei B := {b ∈ A | |v|_{b} < |v′|_{b}} die Menge der Zeichen, welche im bisher gelesenen Teil von w seltener vorkommen als im bisher gelesenen Teil von w′ und D := {d ∈ A | |v|_{d} > |v′|_{d}} entsprechend umgekehrt. Für den Fall, daß w (bzw. w′) bereits zu Ende gelesen wurde und M nicht weiterlesen kann, muß noch ein Zeichen, welches nicht in D (bzw. B) ist, im Rest des jeweils anderen Wortes stehen, dann kann w′ aber nicht von w ableitbar sein, da die Anzahl dieses Zeichens nicht in w und w′ übereinstimmt. Seien also x, x′ ∈ A mit w = vxu und w′ = v′x′u′ die jeweils nächsten Zeichen. Mittels λ-Übergängen sind alle Zustände q_{i} mit D ⊆ D_{i} und B ⊆ B_{i} erreichbar, da die Zähler in {g(r, d), g(l, b) | d ∈ D, b ∈ B} bei einem solchen Übergang nicht auf 0 zu testen sind. Ferner existiert mindestens ein solches q_{m}. Da Zeichen aus D von v nach u′ und Zeichen aus B von u nach v′ gelangen müssen, gilt

D × \{x′\} ∪ \{x\} × B ⊆ \overline{SD}.

Wäre x = x′, so existiert gemäß obenstehendem Hilfssatz (für eine geordnete Menge {a_{1}, ..., a_{n}} = D ∪ {x} ∪ B mit x = a_{m} und a_{i} ∈ D für i < m und a_{i} ∈ B für i > m) ein i mit

S(D, x, B) ⊆ \overline{SD_{i}}

und so könnte M das Zeichen x simultan auf beiden Bändern lesen.

Sonst gilt x, x′ ∉ D∪B, da M sonst x oder x′ lesen könnte, daher gilt (x, x′) ∈ \overline{SD}. Insgesamt gilt also

D^{2}, B^{2}, (D ∪ \{x\}) × (B ∪ \{x′\}) ⊆ \overline{SD} ∪ id.

[figure: w =; w′ =; = vxu; = v′x′u′; d; b; d; b; x; x′]

(1.) Der Fall ∃d_{1} ≠ d_{2}, b_{1} ≠ b_{2}

(d_{1}, d_{2}) ∈ (D ∪ {x})^{2} ∩ SD ∧ (b_{1}, b_{2}) ∈ (B ∪ {x′})^{2} ∩ SD

kann aus folgenden Grund nicht auftreten: Aus (d_{1}, b_{1}) ∈ \overline{SD_{i}} ∧ (d_{1}, b_{2}) ∈ \overline{SD_{j}} ∧ (d_{2}, b_{2}) ∈ \overline{SD_{k}} für gewisse i, j, k folgt, daß d_{1} ∈ D_{i} ∩ D_{j} ∨ b_{1}, b_{2} ∈ B_{i} ∩ B_{j} und, wegen (b_{1}, b_{2}) ∈ (B ∪ {x′})^{2} ∩ SD muß d_{1} ∈ D_{i} ∩ D_{j} gelten. Analog dazu gilt auch b_{2} ∈ B_{j} ∩ B_{k}. Es gilt aber d_{1} ∉ D_{k} und b_{2} ∉ B_{i}, d.h. d_{1} ∈ D_{j} \ D_{k} und b_{2} ∈ B_{j} \ B_{i}. Also müsste g(r, d_{1}) < g(l, b_{2}) und g(l, b_{2}) < g(r, d_{1}) gelten, was ein Widerspruch ist. (2.) Für den Fall

(D ∪ {x})^{2} ∩ SD = (B ∪ {x′})^{2} ∩ SD = ∅

existiert gemäß dem Hilfssatz ein i mit

S(D, x, x′, B) ⊆ \overline{SD_{i}}

und falls D ∪ {x} ⊆ D_{i} oder B ∪ {x′} ⊂ B_{i}, so kann M entweder x oder x′ lesen. Existiert jedoch o.B.d.A ein d ∈ D ∪ \{x\} \ D_{i}, so gilt x′ ∈ B_{i} wegen (d, x′) ∈ \overline{SD_{i}} und somit kann M x′ lesen. (3.) Bleibt also o.B.d.A. der Fall

(D ∪ {x})^{2} ∩ SD = ∅ ∧ (b_{1}, b_{2}) ∈ (B ∪ {x′})^{2} ∩ SD.

Gemäß dem Hilfssatz existiert ein i ≤ s mit S(D, x, B) ⊆ \overline{SD_{i}} und ein j mit S(D, x, x′) ⊆ \overline{SD_{j}}. Aus (x, b_{1}) ∈ \overline{SD_{i}} ∧ (x, b_{2}) ∈ \overline{SD_{j}} oder (x, b_{2}) ∈ \overline{SD_{i}} ∧ (x, b_{1}) ∈ \overline{SD_{j}} folgt x ∈ D_{i} ∩ D_{j} ∨ b_{1}, b_{2} ∈ B_{i} ∩ B_{j}. Und da wegen (b_{1}, b_{2}) ∈ (B ∪ {x′})^{2} ∩ SD die zweite Möglichkeit wegfällt, kann M im Zustand q_{i} das Zeichen x lesen.

Beispiel: Betrachten wir das folgende Halbabhängigkeitsalphabet SD:

[figure: a; b; c; d]

Es ist der Schnitt der beiden PCSD’s

[figure: SD_{1} :=; a; b; c; d; und; a; b; c; d; =: SD_{2}]

mit C_{1} = {b, c, d}, B_{1} = {c}, D_{1} = D_{2} = {c, d}, B_{2} = {d}, C_{2} = {a, c, d} und g(l, c) = 1, g(l, d) = 2, g(r, c) = 3, g(r, d) = 4. Damit ergibt sich nach der Konstruktion in Theorem 5.8 der folgende Prioritätsmulticounterautomat, der die Relation {(w, w′) | w ⟹_{SC}^{∗} w′} erkennt:

[figure: (b, b, 0, 0, 0, 0, 0); (d, λ, 0, 0, 0, 0, 1); (λ, d, 0, 0, 0, 0, −1); (λ, λ, 0, −1, 0, −1, 0); (c, λ, 0, 0, 0, 1, 0); (λ, c, 0, 1, 0, 0, 0); z_{1}; (λ, λ, 1, 0, 0, 0, 0); (λ, λ, 2, 0, 0, 0, 0); z_{e}; (λ, λ, 4, 0, 0, 0, 0); (λ, λ, 4, 0, 0, 0, 0); z_{2}; (a, a, 0, 0, 0, 0, 0); (c, λ, 0, 0, 0, 1, 0); (λ, c, 0, 0, 0, −1, 0); (λ, λ, 0, 0, −1, 0, −1); (d, λ, 0, 0, 0, 0, 1); (λ, d, 0, 0, 0, 1, 0, 0)]

Bemerkung: Bei dem so konstruierten Prioritätsmulticounterautomat lassen sich auch leicht durch Hinzufügen weiterer Zustände die λ-Übergänge vermeiden. Der in Theorem 5.8 konstruierte Prioritätsmulticounterautomat hat die Eigenschaft, daß von jedem Zustand in jeden anderen Zustand übergegangen werden kann, wenn die entsprechende Nulltestbedingung erfüllt ist und daß der Verwendungszweck für jeden Zähler eineindeutig ist. Es ist nicht bekannt, ob mit dieser Eigenschaft eine Einschränkung der charakterisierten PCSD’s verbunden ist.

5.2.2 Notwendiges Kriterium

Eine notwendige Bedingung für eine PMCD gibt der folgende Satz:

Theorem 5.9 SD ist keine PCSD, wenn SD einen induzierten Teilgraphen der Form (\{a, b, c, d\}, E) mit \{(c, a), (b, d)\} ⊆ E ⊆ \overline{\{(a, d), (c, d), (c, b)\}} mit |E| = 4 oder einen induzierten Teilgraphen der Form ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E) oder ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E^{−1}) mit {(a_{i}, b_{i}), (b_{i}, c_{i+1}) | i < n\} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}} enthält.

Das negative Kriterium sind also die Teilgraphen

[figure: a; b; c; d; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; oder; a_{i}; b_{i}; a_{i+1}; c_{i}; c_{i+1}; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

wobei gepunktete Linien eventuelle (nicht störende) Abhängigkeiten beschreiben. Beweis: Angenommen SD ist eine PCSD und zu jeder regulären Sprache R gäbe es somit einen Prioritätsmulticounterautomaten, der f_{SC}(R) erkennt, so können folgende Fälle auftreten: (1.) Enthält SD einen induzierten Teilgraphen der Form ({a, b, c, d}, E) mit \{(c, a), (b, d)\} ⊆ E ⊆ \overline{\{(a, d), (c, d), (c, b)\}}, so könnte ein Prioritätsmulticounterautomat die Sprache

f_{SC}((a(dc)^{∗}b)^{+}) ∩ d^{∗}a(b(cd)^{∗}a)^{∗}bc^{∗} ∩

{d^{n_{1}}ab(cd)^{n_{2}}ab(cd)^{n_{3}}... | ∀j Σ_{i=1}^{j} n_{2i−1} − n_{2i} ≥ 0} ∩

{d^{n_{1}}ab(cd)^{n_{2}}ab(cd)^{n_{3}}... | ∀j Σ_{i=1}^{j} n_{2i} − n_{2i+1} ≥ 0}

= {d^{n}a(b(cd)^{n}a)^{m}bc^{n} | n, m ∈ ℕ}

erkennen, indem er zusätzlich einen endlichen Automaten und zwei Ein-Zählerautomaten (ohne Nulltest) simuliert. Dies ist aber ein Widerspruch, da diese rational äquivalent zu der Sprache {(a^{n}b)^{m} | n, m ∈ ℕ} ist, welche wegen Theorem 3.2 nicht von einem Prioritätsmulticounterautomat erkannt werden kann. Ein Teilstück mitten aus der Spur [w⟩ mit w ∈ (a(dc)^{∗}b)^{+} kann dabei z.B. die Form

[figure: ...; ...; c; b; a; d; c; d; c; d; c; b; a; d; ...; ...; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

haben, wobei die gestrichelten Pfeile mögliche weiche Kanten darstellen, welche bei der durch dargestellten Ableitung zu einem Wort in d^{∗}a(b(cd)^{∗}d)^{∗}c^{∗} umgedreht werden müssen. Durch den Schnitt mit den Sprachen

[figure: w =; w′ =; d; d; d; d; d; d; d; d; d; d; d; d; c; c; c; c; c; c; c; c; c; c; c; c; a; a; a; a; b; b; b; b]

\begin{matrix}\{d^{n_{1}}ab(cd)^{n_{2}}ab(cd)^{n_{3}}... | ∀j Σ_{i=1}^{j} n_{2i−1} − n_{2i} ≥ 0\} und \\ \{d^{n_{1}}ab(cd)^{n_{2}}ab(cd)^{n_{3}}... | ∀j Σ_{i=1}^{j} n_{2i} − n_{2i+1} ≥ 0\}, \end{matrix}

welche jeweils mit einem Zähler ohne Nulltest erkannt werden können, wird erreicht, daß sich ein d nicht vorwärts über ein b und ein c nicht rückwärts über ein a bewegt werden kann, obwohl das Semikommutationssystem dies zulassen würde. Auf diese Weise kann die gleiche Länge der Blöcke erzwungen werden. (2.) Enthält SD einen induzierten Teilgraphen der Form ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E) mit \{(a_{i}, b_{i}), (b_{i}, c_{i+1}) | i < n\} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}} , so könnte ein Prioritätsmulticounterautomat die Sprache

f_{SC}(b_{n}((c_{n}a_{1})^{+}b_{1}(c_{1}a_{2})^{+}b_{2}...(c_{n−1}a_{n})^{+}b_{n})^{+}(c_{n}a_{1})^{+}) ∩ c_{n}^{+}b_{n}((a_{1}c_{1})^{+}b_{1}(a_{2}c_{2})^{+}b_{2}...(a_{n}c_{n})^{+}b_{n})^{+}a_{1}^{+} ∩

{c_{n}^{n_{1}}b_{n}(a_{1}c_{1})^{n_{2}}b_{1}(a_{2}c_{2})^{n_{3}}b_{2}... | ∀j Σ_{i=1}^{j} n_{2i−1} − n_{2i} ≥ 0} ∩

{c_{n}^{n_{1}}b_{n}(a_{1}c_{1})^{n_{2}}b_{1}(a_{2}c_{2})^{n_{3}}b_{2}... | ∀j Σ_{i=1}^{j} n_{2i} − n_{2i+1} ≥ 0}

= {c_{n}^{k}b_{n}((a_{1}c_{1})^{k}b_{1}(a_{2}c_{2})^{k}b_{2}...(a_{n}c_{n})^{k}b_{n})^{m}a_{1}^{k} | m, k ∈ ℕ}

erkennen, was ein Widerspruch ist, da diese ebenfalls rational äquivalent zu der Sprache {(a^{n}b)^{m} | n, m ∈ ℕ} ist. Ein Teilstück mitten aus der Spur [w⟩ mit w ∈ b_{n}(c_{n}a_{1})^{+}b_{1}(c_{1}a_{2})^{+}b_{2}...(c_{n−1}a_{n})^{+}b_{n})^{+}(c_{n}a_{1})^{+} kann dabei z.B. die Form

[figure: ...; ...; b_{i−1}; c_{i−1}; a_{i}; c_{i−1}; a_{i}; b_{i}; c_{i}; a_{i+1}; c_{i}; a_{i+1}; b_{i+1}; ...; ...; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

haben.

[figure: w =; w′ =; c_{2}; c_{2}; c_{2}; c_{2}; b_{2}; b_{2}; a_{1}; a_{1}; c_{1}; c_{1}; c_{1}; c_{1}; a_{1}; a_{1}; b_{1}; b_{1}; a_{2}; a_{2}; c_{2}; c_{2}; c_{2}; c_{2}; a_{2}; a_{2}; b_{2}; b_{2}; a_{1}; a_{1}; a_{1}; a_{1}]

Durch die Verwendung der beiden Zähler ohne Nulltest wird in diesem Fall erreicht, daß sich ein c_{i} nicht vorwärts über ein b_{i+1} und ein a_{i+1} nicht rückwärts über ein b_{i} bewegt werden kann, obwohl das Semikommutationssystem dies zulassen würde. Völlig unklar ist, ob SD_{3} :=

[figure: a; b; c; d; e]

eine PCSD ist. Keine PCSD nach Theorem 5.9 ist SD_{4} :=

[figure: a; b; c; d]

Für eine reguläre Sprache R kann f_{SC_{4}}(R) bzw. f_{SC_{3}}(R) von einem blinden Zählerautomaten erkannt werden, der auf zwei bzw. drei Zählern unabhängig einen Natürlichkeitstest durchführen kann. Unter der Annahme, daß das Halteproblem für diese Automaten entscheidbar ist, sind auch die Fragen f_{SC}(R_{1}) ∩ R_{2} = ∅? und max_{SC}(R_{1}) = R_{1} für SD = SD_{4} bzw. SD = SD_{3} entscheidbar.

5.3 Unentscheidbare Fälle

Mit Theorem 5.9 ist noch nicht bewiesen, daß die Fragen f_{SC}(R_{1}) ∩ R_{2} = ∅? und max_{SC}(R_{1}) = R_{1} für diese Halbabhängigkeitsalphabete nicht entscheidbar sind. Für eine stärkere Einschränkung des induzierten Teilgraphen, bei der die Verwendung der beiden Zähler wie im Beweis von Theorem 5.9 nicht nötig ist, weil das Semikommutationssystem die unerwünschten Verschiebungen ohnehin nicht zuläßt, sind beide Fragen unentscheidbar. Zum Beweis wird folgendes Lemma benötigt:

Lemma 5.1 Für die Eingabe R ⊂ ℕ^{3}, |R| < ∞ und a, e ∈ ℕ ist nicht entscheidbar, ob m, a = n_{1}, ..., n_{m} = e ∈ ℕ existieren mit

∀i < m∃(r_{1}, r_{2}, r_{3}) ∈ R n_{i}/r_{1} = n_{i+1}/r_{2} ∈ ℕ ∧ ¬n_{i}/r_{3} ∈ ℕ.

Beweis: Bekannt ist aus [Min71] die Unentscheidbarkeit des Halteproblems für Multicounterautomaten mit Nulltest^{3}. Dieses werden wir nun mittels Primzahlcodierung der Konfigurationen reduzieren. Im Gegensatz zur Reduktion auf eine Ein-Registermaschine in [Min71] muß nun auch der Zustand mitcodiert werden. Gegeben sei ein Multicounterautomat A = (k, Z, δ, z_{0}, z_{t}) mit k Zählern, der Zustandsmenge Z = {z_{0}, z_{1}, ...z_{t}}, der Übergangsrelation

3Ein Zähler kann die Codierung eines Halbbandes einer Turingmaschine enthalten.

δ ⊆ (Z × {1, ...k}) × (Z × {0, 1}^{k} × {0, 1}^{k}),

dem Anfangszustand z_{0}, dem Endzustand z_{t}, der Konfigurationenmenge C_{A} = Z × ℕ^{k}, der Anfangs- und Endkonfiguration ⟨z_{0}, 0^{k}⟩ und ⟨z_{t}, 0^{k}⟩ und der Konfigurationsübergangsrelation

⟨z, c + d⟩ | \overline{A} ⟨z′, c + i⟩ gdw. z, z′ ∈ Z, ∃j ≤ k ⟨(z, j), (z′, i, d)⟩ ∈ δ und n_{j} = 0,

d.h. j ist die Nummer des Zählers, der bei diesem Übergang von z nach z′ auf Null getestet wird und i bzw. d sind Vektoren in {0, 1}^{k} um die die Zählerinhalte inkrementiert bzw. dekerementiert werden. (Wir können o.B.d.A. davon ausgehen, daß A seine Zähler auf 0 bringt, bevor er akzeptiert. Will A in einem Schritt mehrere Zähler auf 0 testen, so kann er dies auch sequentiell mit zusätzlichen Zwischenzuständen tun. Will A keinen Zähler auf 0 testen, so kann er einen Zähler, der nie verändert wird, auf 0 testen.) Seien p_{0}, p_{1}, ..., p_{k+t} die ersten k + t + 1 Primzahlen. Wir wollen nun die Konfigu-

rationen ⟨z_{k_{l}}, c_{l}⟩ des Automaten in Primzahlprodukte n_{l} = p_{k_{l}} Π_{h=1}^{k} p_{t+h}^{c_{l}(h)} codieren.

Setze a := p_{0} für die Anfangskonfiguration ⟨z_{0}, 0^{k}⟩, e := p_{t} für die Endkonfiguration ⟨z_{t}, 0^{k}⟩ und R :=

{(r_{1}, r_{2}, p_{t+j}) | ⟨(z_{v}, j), (z_{n}, i, d)⟩ ∈ δ ∧ r_{1} = p_{v} Π_{h=1}^{k} p_{t+h}^{d(h)} ∧ r_{2} = p_{n} Π_{h=1}^{k} p_{t+h}^{i(h)}}.

Die Division einer Konfigurationscodierung durch r_{1} bzw. durch r_{2} entspricht dem Entfernen des Zustandes und des Inkrements der Zähler (bzw. in umgekehrter Weise des Dekrements); die Nichtteilbarkeit durch r_{3} = p_{t+j} entspricht dem Nulltest des j-ten Zählers. Eine Konfigurationsfolge ⟨z_{k_{1}}, c_{1}⟩ = ⟨z_{0}, 0^{k}⟩, ⟨z_{k_{2}}, c_{2}⟩ bis ⟨z_{k_{m}}, c_{m}⟩ = ⟨z_{t}, 0^{k}⟩ existiert genau dann wenn a = n_{1}, ..., n_{m} = e ∈ ℕ existie-

ren mit n_{l} = p_{k_{l}} Π_{h=1}^{k} p_{t+h}^{c_{l}(h)} für alle 1 ≤ l ≤ m.

Wir können nun verschiedene Kriterien für die Unentscheidbarkeit der Frage max_{SC}(L) = L? angeben.

Theorem 5.10 Hat SD einen induzierten Teilgraphen der Form ({a, b, c, d}, E) mit \{(c, a), (a, c), (d, b), (b, d)\} ⊆ E ⊆ \overline{\{(a, d), (c, d), (c, b)\}}, a ≠ c, b ≠ d und existiert eine nicht symmetrische Kante (f, e) ∈ SD \ SD^{−1}, so ist für reguläre Stringsprachen L die Frage max_{SC}(L) = L unentscheidbar.

Das Kriterium ist also der Teilgraph

[figure: a; b; c; d; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

wobei gepunktete Linien eventuelle (nicht störende) Abhängigkeiten beschreiben.

Beweis: Sei R ⊂ ℕ^{3} mit |R| < ∞ und a, e ∈ ℕ wie in Lemma 5.1 gegeben. Die Sprache

R_{c,d} := {(c^{r_{1}}d^{r_{2}})^{mk} | (r_{1}m, r_{2}m, r_{3}) ∈ R ∧ ggT (r_{1}, r_{2}) = 1 ∧ ¬k/r_{3} ∈ ℕ}

ist regulär, da R endlich ist. Es gilt für alle n_{i}, n_{i+1} ∈ ℕ

∃(r_{1}, r_{2}, r_{3}) ∈ R n_{i}/r_{1} = n_{i+1}/r_{2} ∈ ℕ ∧ ¬n_{i}/r_{3} ∈ ℕ

genau dann wenn

∃w ∈ R_{c,d} |w|_{d} = n_{i} ∧ |w|_{c} = n_{i+1}.

Ferner ist R_{c,d} aus folgendem Grund maximal: Ist (d, c) ∉ SD, so ist die Maximalität trivial, andernfalls folgt aus (c^{r_{1}}d^{r_{2}})^{l} ⟹_{SC}^{∗} (c^{r′_{1}}d^{r′_{2}})^{l′} wegen r_{1}l = r′_{1}l′ und r_{2}l = r′_{2}l′ daß r_{1}r′_{2} = r′_{1}r_{2} gilt. Es gilt aber r_{1} ≥ r′_{1} und r_{2} ≥ r′_{2}, da der erste c-Block und der letzte d-Block nur kürzer werden können. Wegen ggT (r_{1}, r_{2}) = 1 muß also r_{1} = r′_{1} und r_{2} = r′_{2} gelten. Sei

L = feb(adR_{c,d}cb)^{+}a ∪ efbd^{n_{1}}a(b(cd)^{∗}a)^{∗}bc^{n_{m}}a.

Da die c’s und d’s die durch ba bzw. ab getrennten Blöcke nicht verlassen können, sind die beiden Teilmengen der Sprache L jeweils maximal. Die einzige Möglichkeit, daß L selbst nicht maximal ist, besteht also darin, daß ein Wort aus dem Teil feb(adR_{c,d}cb)^{+}a zu einem Wort in efbd^{n_{1}}a(b(cd)^{∗}a)^{∗}bc^{n_{m}}a abgeleitet werden kann. Könnte man entscheiden, ob die Sprache L maximal ist, so würde dies Lemma 5.1 widersprechen, da n_{2}, ...n_{m−1} mit der Bedingung genau dann existieren, wenn ein Wort w aus feb(adR_{c,d}cb)^{+}a abgeleitet werden kann zu einem Wort

w′ = efbd^{n_{1}}ab(cd)^{n_{2}}ab(cd)^{n_{3}}a...b(cd)^{n_{m−1}}abc^{n_{m}}a

in efbd^{n_{1}}a(b(cd)^{∗}a)^{∗}bc^{n_{m}}a. Die n_{i} d’s eines i-ten Blockes und die n_{i+1} d’s des folgenden i+1-ten Blockes von w′ befinden sich in w im gleichen Teilwort in R_{c,d}, wodurch für alle n_{i}, n_{i+1} die Bedingung

∃(r_{1}, r_{2}, r_{3}) ∈ R n_{i}/r_{1} = n_{i+1}/r_{2} ∈ ℕ ∧ ¬n_{i}/r_{3} ∈ ℕ

erfült ist. Ein Teilstück mitten aus der Spur [w⟩ wird exemplarisch dargestellt durch

[figure: ...; ...; c; b; a; d; c^{r_{2}}; d^{r_{1}}; c^{r_{2}}; d^{r_{1}}; c; b; a; d; ...; ...; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

wobei die gepunkteten Pfeile mögliche weiche Kanten darstellen, welche bei der Ableitung umgedreht werden.

Durch das Zusammenfassen von Zeichen ergibt sich anderes Kriterium.

Theorem 5.11 Hat SD einen induzierten Teilgraphen der Form ({a, b, c, d}, E) mit \{(c, a), (b, d)\} ⊆ E ⊆ \overline{\{(a, d), (c, d), (c, b), (a, b)\}}, a ≠ c, b ≠ d und existiert (f, e) ∈ SD\SD^{−1}, so ist für reguläre Stringsprachen L die Frage max_{SC}(L) = L unentscheidbar.

Das Kriterium ist also der Teilgraph

[figure: a; b; c; d; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

Beweis: Sei h ein Homomorphismus mit h(a) = ac, h(c) = ca, h(b) = bd, h(d) = db. Anstelle der Sprache L im Beweis von Theorem 5.10 verwenden wir nun h(L). Wird im einem Wort h(w) in h(L) ein Teilstück ac zu ca oder ein Teilstück db zu bd abgeleitet, so wird dabei entweder das Bild eines Wortes w′ erzeugt, welches aus w durch Ersetzen von a durch c bzw. von d durch b entsteht, oder es wird ein Wort erzeugt, welches kein Bildwort ist und von dem auch kein Bildwort mehr abgeleitet werden kann. In beiden Fällen kann damit kein Wort in h(L) erreicht werden, da die Anzahl der a’s und b’s in jedem Wort von L gleich sind. Somit verhalten sich die gepaarten Symbole in gleicher Weise wie die Urbilder im Beweis von Theorem 5.10.

Theorem 5.12 Hat SD einen induzierten Teilgraphen der Form

[figure: a; b; c; d]

(d.h. ({a, b, c, d}, {(a, b), (b, c), (c, d), (d, a)})), so ist für reguläre Stringsprachen L die Frage max_{SC}(L) = L unentscheidbar.

Beweis: Analog zum Beweis von Theorem 5.10 sei

R_{b,c} := {(b^{r_{1}}c^{r_{2}})^{mk} | (r_{1}m, r_{2}m, r_{3}) ∈ R ∧ ggT (r_{1}, r_{2}) = 1 ∧ ¬k/r_{3} ∈ ℕ}.

Wir betrachten die Maximalität der Sprache

L = (R_{b,c}(ad)^{+}(bc)^{+}(da)^{+})^{∗}(cb)^{+} ∪ b^{n_{1}}((cd)^{+}(ac)^{+}(ba)^{+}(db)^{+})^{∗}c^{n_{m}}.

Ein Teilstück aus der Spur [w⟩ für ein Wort w ∈ (R_{b,c}(ad)^{+}(bc)^{+}(da)^{+})^{∗}(cb)^{+} wird dabei exemplarisch dargestellt durch

[figure: ...; ...; c^{r_{2}m}; b^{r_{1}m}; a^{r_{2}m}; d^{r_{2}m}; b^{r_{2}m}; c^{r_{2}m}; d^{r_{2}m}; a^{r_{2}m}; c^{r′_{2}m′}; b^{r′_{1}m′}; a^{r′_{2}m′}; d^{r′_{2}m′}; ...; ...; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

wobei die Ableitung zu einem w′ ∈ b^{n_{1}}((cd)^{+}(ac)^{+}(ba)^{+}(db)^{+})^{∗}c^{n_{m}} nur dann erfolgreich sein kann, wenn r_{2}m = r′_{1}m′ ist.

Theorem 5.13 Hat SD einen induzierten Teilgraphen der Form ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E) oder ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E^{−1}) mit {(a_{i}, b_{i}), (b_{i}, a_{i+1}), (c_{i}, b_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}} oder {(a_{i}, b_{i}), (b_{i}, a_{i+1}), (c_{i}, a_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}} oder ∀i < n a_{i} ≠ a_{i+1} und \{(a_{i}, b_{i}), (c_{i}, a_{i+1}), (b_{i}, c_{i+1}) | i < n\} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}} und existiert (f, e) ∈ SD \ SD^{−1}, so ist für reguläre Stringsprachen L die Frage max_{SC}(L) = L unentscheidbar.

Beweis: Analog zum Beweis von Theorem 5.10, wobei die Sprache

L =feb_{n}(c_{n}R_{a_{1},c_{n}}a_{1}b_{1}(c_{1}a_{2})^{+}b_{2}...(c_{n−1}a_{n})^{+}b_{n})^{+}(c_{n}a_{1})^{+} ∪
efc_{n}^{n_{1}}b_{n}((a_{1}c_{1})^{+}b_{1}(a_{2}c_{2})^{+}b_{2}...(a_{n}c_{n})^{+}b_{n})^{+}a_{1}^{n_{m}}

verwendet wird und ein Teilstück von [w⟩ im Fall {(a_{i}, b_{i}), (b_{i}, a_{i+1}), (c_{i}, b_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E die Form

[figure: ...; ...; b_{i−1}; c_{i−1}; a_{i}^{r′′_{2}}; c_{i−1}^{r′′_{1}}; a_{i}; b_{i}; c_{i}; a_{i+1}^{r_{2}}; c_{i}^{r_{1}}; a_{i+1}; b_{i+1}; ...; ...; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

im Fall {(a_{i}, b_{i}), (b_{i}, a_{i+1}), (c_{i}, a_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E die Form

[figure: ...; ...; b_{i−1}; c_{i−1}; a_{i}^{r′′_{2}}; c_{i−1}^{r′′_{1}}; a_{i}; b_{i}; c_{i}; a_{i+1}^{r_{2}}; c_{i}^{r_{1}}; a_{i+1}; b_{i+1}; ...; ...; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

und im Fall ∀i < n a_{i} ≠ a_{i+1} und {(a_{i}, b_{i}), (c_{i}, a_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E die Form

[figure: ...; ...; b_{i−1}; c_{i−1}; a_{i}^{r′′_{2}}; c_{i−1}^{r′′_{1}}; a_{i}; b_{i}; c_{i}; a_{i+1}^{r_{2}}; c_{i}^{r_{1}}; a_{i+1}; b_{i+1}; ...; ...; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

haben können. Beispiel:

[figure: a; b_{1}; b_{2}; c_{1}; c_{2}]

Mit der gleichen Beweismethode kann auch die Unentscheidbarkeit der Frage f_{SC}(R_{1}) ∩ R_{2} = ∅? für zwei reguläre Sprachen gezeigt werden. Die Bedingung der Existenz einer asymmetrischen Kante (f, e) ∈ SD \ SD^{−1} ist dabei nicht mehr erforderlich.

Theorem 5.14 Hat SD einen induzierten Teilgraphen der Form

1. (\{a, b, c, d\}, E) mit \{(c, a), (a, c), (d, b), (b, d)\} ⊆ E ⊆ \overline{\{(a, d), (c, d), (c, b)\}}, a ≠ c, b ≠ d oder

2. (\{a, b, c, d\}, E) mit \{(c, a), (b, d)\} ⊆ E ⊆ \overline{\{(a, d), (c, d), (c, b), (a, b)\}}, a ≠ c, b ≠ d oder

3. ({a, b, c, d}, {(a, b), (b, c), (c, d), (d, a)}) oder

4. ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E) oder ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E^{−1}) mit {(a_{i}, b_{i}), (b_{i}, a_{i+1}), (c_{i}, b_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}} oder {(a_{i}, b_{i}), (b_{i}, a_{i+1}), (c_{i}, a_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}} oder ∀i < n a_{i} ≠ a_{i+1} und

{(a_{i}, b_{i}), (c_{i}, a_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E ⊆
\overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}}

so ist für zwei reguläre Sprachen die Frage f_{SC}(R_{1}) ∩ R_{2} = ∅? unentscheidbar.

Beweis: Im Fall 1 verwenden wir für wie in Lemma 5.1 gegebenes R ⊂ ℕ^{3} mit |R| < ∞ und a, e ∈ ℕ die Sprachen

R_{1} := b(adR_{c,d}cb)^{+}a und R_{2} := bd^{n_{1}}a(b(cd)^{∗}a)^{∗}bc^{n_{m}}a.

Könnte man entscheiden, ob f_{SC}(R_{1}) ∩ R_{2} = ∅ gilt, so würde dies Lemma 5.1 widersprechen, da n_{2}, ...n_{m−1} mit der Bedingung

∃(r_{1}, r_{2}, r_{3}) ∈ R n_{i}/r_{1} = n_{i+1}/r_{2} ∈ ℕ ∧ ¬n_{i}/r_{3} ∈ ℕ

genau dann existieren, wenn ein Wort w aus R_{1} abgeleitet werden kann zu einem Wort

w′ = bd^{n_{1}}ab(cd)^{n_{2}}ab(cd)^{n_{3}}a...b(cd)^{n_{m−1}}abc^{n_{m}}a

in R_{2}. Analog dazu wird im Fall 2

R_{1} := h(b(adR_{c,d}cb)^{+}a) und R_{2} := h(bd^{n_{1}}a(b(cd)^{∗}a)^{∗}bc^{n_{m}}a),

im Fall 3

R_{1} := (R_{b,c}(ad)^{+}(bc)^{+}(da)^{+})^{∗}(cb)^{+} und R_{2} := b^{n_{1}}((cd)^{+}(ac)^{+}(ba)^{+}(db)^{+})^{∗}c^{n_{m}}

und im Fall 4

\begin{matrix}R_{1} := b_{n}(c_{n}R_{a_{1},c_{n}}a_{1}b_{1}(c_{1}a_{2})^{+}b_{2}...(c_{n−1}a_{n})^{+}b_{n})^{+}c_{n}R_{a_{1},c_{n}}a_{1} und \\ R_{2} := c_{n}^{n_{1}}b_{n}((a_{1}c_{1})^{+}b_{1}(a_{2}c_{2})^{+}b_{2}...(a_{n}c_{n})^{+}b_{n})^{+}a_{1}^{n_{m}} \end{matrix}

verwendet.

Die Frage f_{SC}(R_{1}) ∩ f_{SC}(R_{2}) = ∅? bzw. f_{SC}(R_{1}) ∥ f_{SC}(R_{2}) ≠ ∅? nach der Synchronisierbarkeit zweier Halbspursprachen ist in dem durch Fall 2 beschriebenen Beispiel

[figure: a; b; c; d]

offensichtlich entscheidbar, da in diesem Fall SC konfluent ist, und somit gemäß [RW91] die Komposition von SC und SC^{−1} ein Semikommutationssystem und damit die Frage f_{SC}(R_{1}) ∥ f_{SC}(R_{2}) ≠ ∅ äquivalent zu der Frage f_{SC∪SC^{−1}}(R_{1}) ∩ R_{2} ≠ ∅ ist, was leicht zu entscheiden ist, da in diesem Fall SD∩SD^{−1} die Identität ist. Für andere Teile der Bedingung läßt sich aber, wie man durch Betrachten der Spurgraphen der vorhergehenden Beweise erkennen kann, der Unentscheidbarkeitsbeweis in gleicher Weise führen:

Theorem 5.15 Hat SD einen induzierten Teilgraphen der Form

1. (\{a, b, c, d\}, E) mit \{(c, a), (a, c), (d, b), (b, d)\} ⊆ E ⊆ \overline{\{(a, d), (c, d), (c, b)\}}, a ≠ c, b ≠ d oder

2. ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E) oder ({a_{1}, b_{1}, c_{1}, ..., a_{n} = a_{0}, b_{n} = b_{0}, c_{n} = c_{0}}, E^{−1}) mit {(a_{i}, b_{i}), (b_{i}, a_{i+1}), (c_{i}, b_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}} oder {(a_{i}, b_{i}), (b_{i}, a_{i+1}), (c_{i}, a_{i+1}), (b_{i}, c_{i+1}) | i < n} ⊆ E ⊆ \overline{\{(a_{i}, c_{i}), (b_{i}, c_{i}), (a_{i+1}, c_{i}) | i < n\}}

so ist für zwei reguläre Sprachen die Frage f_{SC}(R_{1}) ∥ f_{SC}(R_{2}) = ∅? unentscheidbar.

6 Die Konfluenz von Semikommutationssystemen

Definition Ein Semikommutationssystem SC heißt konfluent, wenn für alle

u, v, w ∈ A^{∗} mit u ⟸_{SC}^{∗} v ⟹_{SC}^{∗} w ein v′ ∈ A^{∗} existiert mit u ⟹_{SC}^{∗} v′ ⟸_{SC}^{∗} w. Dies

bedeutet, daß falls [u⟩ ⊆ [v⟩ und [w⟩ ⊆ [v⟩, so ist [u⟩ ∩ [w⟩ ≠ ∅.

Die Eigenschaft der Konfluenz ist besonders deswegen von Interesse, da ein System, das zugleich noethersch ist, die Möglichkeit bietet das Wortproblem durch Berechnen der irreduzieblen Normalform zu lösen. Ein System S ⊆ M × M heißt noethersch, wenn es keine unendliche Kette t_{1} ⟹_{S} t_{2} ⟹_{S} t_{3} … gibt. Im Gegensatz zu Semi-Thue-Systemen ist die Konfluenz endlicher noetherscher längenreduzierender Spurersetzungssysteme i.A. unentscheidbar [NO88]. Ein Beispiel für ein nicht konfluentes Semikommutationssystem ist folgender Abhängigkeitsgraph:

[figure: (A, SD); =; b; a; c; d]

Bei diesem gilt adcb ⟸_{SC} acbd ⟹_{SC} cbad, aber adcb und cbad sind irreduzibel, wie folgendes Bild zeigt:

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; ⟹_{S}; ⟸_{S}; d; a; b; c; c; b; d; a; b; c; d; a]

Allgemein hat eine Halbspur v die Möglichkeit zu einer nicht konfluenten Situa-

tion, d.h. ∃u, w ∈ A^{∗} mit u ⟸_{SC}^{∗} v ⟹_{SC}^{∗} w und ¬∃v′ ∈ A^{∗} mit u ⟹_{SC}^{∗} v′ ⟸_{SC}^{∗} w,

genau dann, wenn v einen sehnenlosen, gerichteten Kreis aus harten Kanten und mindestens zwei weichen Kanten in umgekehrter Richtung besitzt, wie folgende Abbildung zeigt:

[figure: [v⟩ =; y_{n}; y_{1}; x_{1}; x_{m}; ⋯; ⋯]

Theorem 6.1 Das folgende Problem ist NLOGSPACE-vollständig: Gegeben seien ein Halbabhängigkeitsalphabet (A, SD) und v ∈ A^{∗}.

Gilt ∃u, w ∈ A^{∗} mit u ⟸_{SC}^{∗} v ⟹_{SC}^{∗} w und ¬∃v′ ∈ A^{∗} mit u ⟹_{SC}^{∗} v′ ⟸_{SC}^{∗} w?

Beweis: Eine nichtdeterministische logarithmisch platzbeschränkte Turingmaschine rät zwei weiche Kanten a [figure]b und c [figure]d und überprüft, ob es einen Weg aus harten Kanten und umgekehrten weichen Kanten von a nach d und von c nach b gibt. (Es darf auch a = d oder c = b gelten aber natürlich nicht beides.) Mit Hilfe der Technik von [Imm88] und [Sze88] wird noch überprüft ob es keinen Weg aus harten Kanten von a nach b und von c nach d gibt. Die NLOGSPACE-Härte folgt durch Reduktion des monotonen Grapherreichbarkeitsproblems für gerichtete Graphen. Es werden zusätzliche Kanten (b, s) und (e, b) und ein zusätzlicher Knoten b hinzugefügt und bei dem so erzeugten Abhängigkeitsgraphen ({b, s, a_{2}, a_{3}, … a_{n−1}, e}, SD) überprüft, ob es eine nicht konfluente Situtation für [sb(a_{2}a_{3} … a_{n−1})^{n}e⟩ gibt.

Ein allgemeines Kriterium für Konfluenz ist folgendes:

Theorem 6.2 [DOR94] Sei (A, SD) ein Halbabhängigkeitsalphabet mit dem Semikommutationssystem SC = {ab ⟹ ba | (a, b) ∈ A × A \ SD}. SC ist nicht konfluent gdw. (A, SD) einen gerichteten Kreis (x_{1}, …, x_{n}) aus verschiedenen Knoten mit n ≥ 3, (x_{i}, x_{i+1}) ∈ SD für alle i mod n und mindestens 2 gerichtete Kanten enthält, der aber keine ungerichtete Sehne (x_{i}, x_{j}) ∈ SD ∩ SD^{−1} mit 2 ≤| j − i |≤ n − 2 besitzt.

[figure: x_{n}; x_{i+1}; x_{1}; x_{i}; ⋯; ⋯]

Da gemäß [RW91] ein Semikommutationssystem SC genau dann konfluent ist, wenn die Komposition von SC und SC^{−1} ein Semikommutationssystem ist, folgt dies auch aus folgender allgemeineren Aussage:

Theorem 6.3 [RW91] Für Halbabhängigkeitsalphabete (A, SD_{1}) und (A, SD_{2}) gilt: Die Komposition der beiden Semikommutationssysteme ist kein Semikommutationssystem gdw. (A, SD_{1} ∪ SD_{2}^{−1}) einen gerichteten Kreis (x_{1}, …, x_{n}) aus verschiedenen Knoten mit n ≥ 3, (x_{i}, x_{i+1}) ∈ SD_{1} ∪ SD_{2}^{−1} für alle i mod n und beiden Kanten (x_{0}, x_{n}) ∈ SD_{2} \ SD_{1} und (x_{i}, x_{i+1}) ∈ SD_{1} \ SD_{2} enthält, der aber keine Sehne (x_{h}, x_{j}) ∈ SD_{1} ∩ SD_{2} mit 0 ≤ h ≤ i und i + 1 ≤ j ≤ n besitzt.

Aus der Symmetrie in Theorem 6.2 folgt:

Korollar 6.1 [DOR94] Ein Semikommutationssystem SC ist konfluent gdw. SC^{−1} = {ba ⟹ ab | ab ⟹ ba ∈ SC} konfluent ist.

Theorem 6.2 ist eine Verallgemeinerung eines Resultates aus [MO87], welches besagt, daß ein Semikommutationssystem ohne symmetrische Regeln konfluent ist gdw. die Unabhängigkeitsrelation transitiv ist. Das Resultat verallgemeinert auch [Ott89], da sich die Frage nach der Existenz eines endlichen konfluenten noetherschen Spurersetzungssystems, welches ein Spurmonoid auf einem anderen Spurmonoid mit größerer Abhängigkeitsrelation definiert, auf die Existenz eines konfluenten Semikommutationssystems reduzieren läßt.

Theorem 6.4 [DOR94] Seien M = M(A, D), M′ = M(A, D′) zwei Spurmonoide mit D′ ⊆ D. Sei R ⊆ M × M ein endliches konfluentes noethersches Spurersetzungssystem M/R = M′ und sei S = {ab ⟹ ba ∈ R | a, b ∈ A}, so gilt M/S = M/R = M′ und S ist ein endliches konfluentes noethersches Spurersetzungssystem.

Mit Hilfe der Graphkonstruktion, mit welcher bestimmte beschränkt quantifizierter Boolescher Formeln, welche gemäß [Wra77] Σ_{2}^{P} -vollständig sind, reduziert werden, erhalten wir in [DOR94] folgende Resultate:

Theorem 6.5 Die folgenden zwei äquivalenten Probleme sind Σ_{2}^{P} -vollständig:

1. Gegeben zwei Halbanhängigkeitsalphabete (A, D) und (A, D′) mit D′ ⊆ D.

Gibt es ein konfluentes Semikommutationssystem SC mit

D = {(a, b) ∈ A × A | ab ⟹ ba ∉ SC ∩ SC^{−1}} und D′ = {(a, b) ∈ A × A | ab ⟹ ba ∉ SC ∪ SC^{−1}}?

2. Gegeben seien zwei Spurmonoide M = M(A, D) und M′ = M(A, D′) mit D′ ⊆ D.

Gibt es ein endliches konfluentes noethersches Spurersetzungssystem R ⊆ M × M mit M/R = M′?

Sei die Anzahl der asymmetrischen Abhängigkeiten durch eine Konstante k beschränkt, bzw. |D \ D′| ≤ k. Für k = 1 sind beide Probleme trivial.

Theorem 6.6 Sei k ≥ 2 konstant, so ist das Problem aus Theorem 6.5 beschränkt auf |D \ D′| ≤ k co-NP-vollständig.

Noch spezieller gilt: Es ist co-NP-vollständig für eine Eingabe der Form D = D′ ∪ {(a, b), (b, a), (c, d), (d, c)} zu entscheiden, ob ein endliches konfluentes noethersches Spurersetzungssystem R ⊆ M(A, D) × M(A, D) mit der Eigenschaft M(A, D)/R = M(A, D′) existiert.

Theorem 6.7 Auch für den Spezialfall, daß höchstens 2 asymmetrische Regeln vorhanden sind, ist es co-NP-vollständig zu entscheiden, ob ein Semikommutationssystem konfluent ist.

Mit Theorem 6.3 gilt auch folgendes:

Korollar 6.2 Es ist es co-NP-vollständig zu entscheiden, ob für Halbabhängigkeitsalphabete (A, SD_{1}) und (A, SD_{2}) die Komposition der beiden Semikommutationssysteme ein Semikommutationssystem ist.

Literatur

[AG91] C. Àlvarez and J. Gabarró. The parallel complexity of two problems on concurrency. Information Processing Letters, 38:61–70, 1991.

[AH89] IJ. J. Aalbersberg and H. J. Hoogeboom. Characterizations of the decidability of some problems for regular trace languages. Mathematical Systems Theory, 22:1–19, 1989.

[Ber79] J. Berstel. Transductions and context-free languages. Teubner Studienbücher, Stuttgart, 1979.

[BIS90] D.M. Barrington, N. Immerman, and H. Straubing. On uniformity within NC^{1}. J. of Comp. and Syst. Sciences, 41:274–306, 1990.

[BMS82] A. Bertoni, G. Mauri, and N. Sabadini. Equivalence and membership problems for regular trace languages. In Proceedings of the 9th International Colloquium on Automata, Languages and Programming, number 140 in Lecture Notes in Computer Science, pages 61–71, Berlin-Heidelberg-New York, 1982. Springer.

[CF69] P. Cartier and D. Foata. Problèmes combinatoires de commutation et réarrangements. Number 85 in Lecture Notes in Mathematics. Springer, Berlin-Heidelberg-New York, 1969.

[CG90] M. Clerbout and D. Gonzalez. Decomposition of semi commutations. In B. Rovan, editor, Proceedings of the 15th Symposium on Mathematical Foundations of Computer Science (MFCS’90), Banská Bystrica (Czechoslovakia) 1990, number 452 in Lecture Notes in Computer Science, pages 209–216, Berlin-Heidelberg-New York, 1990. Springer.

[CG94] M. Clerbout and D. Gonzalez. Atomic semi commutations. Theoretical Computer Science, 123:259–272, 1994.

[CGL^{+}92] M. Clerbout, D. Gonzalez, M. Latteux, E. Ochmanski, Y. Roos, and P.A. Wacrenier. Recognizable morphisms on semi commutations. Tech. Rep. LIFL I.T.-238, Université des Sciences et Technologies de Lille (France), 1992.

[CL87] M. Clerbout and M. Latteux. Semi-Commutations. Information and Computation, 73:59–74, 1987.

[Cle84] M. Clerbout. Commutations Partielles et Familles de Langages. Thèse, Université des Sciences et Technologies de Lille (France), 1984.

[Die90] V. Diekert. Combinatorics on Traces. Number 454 in Lecture Notes in Computer Science. Springer, Berlin-Heidelberg-New York, 1990.

[DOR94] V. Diekert, E. Ochmański, and K. Reinhardt. On confluent semicommutation systems – decidability and complexity results. Information and Computation, 110:164–182, 1994. A preliminary version was presented at ICALP’91, Lecture Notes in Computer Science 510 (1991).

[DV89] V. Diekert and W. Vogler. On the synchronization of traces. Mathematical Systems Theory, 22:161–175, 1989. A preliminary extended abstract appeared at MFCS 88, Lecture Notes in Computer Science 324 (1988) 271-279.

[Gon93] D. Gonzalez. Décomposition de semi-commutations. Thèse, Université des Sciences et Technologies de Lille (France), 1993.

[Gre78] S. Greibach. Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci., 7:311–324, 1978.

[Hau90] D. Hauschildt. Semiliearity of the Reachability Set is Decidable for Petri Nets. Dissertation, Universität Hamburg, 1990.

[HK89] D. V. Hung and E. Knuth. Semi-commutations and Petri nets. Theoretical Computer Science, 64:67–81, 1989.

[HU79] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[Iba78] O. H. Ibarra. Reversal-bounded multicounter machines and their decision problems. Journal of the Association of Computing Machinery, 25:116–133, 1978.

[Imm88] N. Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, 17(5):935–938, 1988.

[Kie89] A. Kiehn. A Structuring Mechanism for Petri Nets. Dissertation, Universität München, 1989.

[Kos84] S.R. Kosaraju. Decidability of reachability in vector addition systems. In Proceedings 14th Ann. ACM STOC, pages 267–281, 1984.

[Lat92] M. Latteux. Some results on semi-commutations. In M. Ito, editor, Proceedings of the International Colloquium on Words, Languages and Combinatorics (Kyoto 1990). World Scientific, Singapore, 1992. Appeared also as Technical Report I.T 201 Université de Lille.

[LR90] K.-J. Lange and P. Rossmanith. Two Results on Unambiguous Circuits. SFB-Bericht 342/3/90 A, I9006, Institut für Informatik, Technische Universität München, 1990.

[LR94] K.-J. Lange and K. Reinhardt. Empty alternation. In B. Rovan, editor, Proc. of 19th MFCS, number 841 in LNCS, pages 494–503, Kosice, Slovakia, August 1994. Springer-Verlag.

[May84] E. Mayr. An algorithm for the general Petri net reachability problem. Siam J. Comput., 13:441–459, 1984.

[Maz77] A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977.

[Maz87] A. 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.

[Min71] M. L. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1971.

[MO87] Y. Métivier and E. Ochmański. On lexicographic semi-commutations. Information Processing Letters, 26:55–59, 1987.

[NO88] P. Narendran and F. Otto. Preperfectness is undecidable for Thue systems containing only length-reducing rules and a single commutation rule. Information Processing Letters, 29:125–130, 1988.

[Och90] E. Ochmański. Semi-Commutation and Petri Nets. In V. Diekert, editor, Proceedings of the ASMICS workshop Free Partially Commutative Monoids, Kochel am See 1989, Report TUM-I9002, Technical University of Munich, pages 151–166, 1990.

[Och92] E. Ochmański. Modelling concurrency with semi-commutations. 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 412–420, Berlin-Heidelberg-New York, 1992. Springer.

[Ott89] F. Otto. On deciding confluence of finite string rewriting systems modulo partial commutativity. Theoret. Comput. Sci., 67:19–36, 1989.

[Par90] Ian Parberry. A primer on the complexity theory of neural networks. In R.B. Banerji, editor, Formal Techniques in Artificial Intelligence, Amsterdam, 1990. North-Holland.

[Rei89] K. Reinhardt. Hierarchien mit alternierenden Kellerautomaten, alternierenden Grammatiken und finiten Transducern. Diplomarbeit, Universität Stuttgart, Breitwiesenstr. 22, D-70565 Stuttgart, September 1989.

[Rei90] K. Reinhardt. Hierarchies over the context-free languages. In J. Dassow and J. Kelemen, editors, Proc. of 6th IMYCS, number 464 in LNCS, pages 214–224. Springer-Verlag, 1990.

[Rei92a] K. Reinhardt. Counting and empty alternating pushdown automata. In J. Dassow, editor, Developments in Theoretical Computer Science: Proc. of 7th IMYCS, number 6 in Topics in Computer Mathematics, pages 123–132. Gordon and Breach Science Publishes S.A., 1992.

[Rei92b] K. Reinhardt. Sorting in-place with a worst case complexity of n log n−1.3n + o(log n) comparisons and ε n log n + o(1) transports. In Ibaraki et al., editor, Proceedings of the 3rd International Symposium on Algorithms and Computation, number 650 in LNCS, pages 489–498. Springer-Verlag, 1992.

[Rei94] K. Reinhardt. Das Erreichbarkeitsproblem bei Petrinetzen mit inhibitorischen Kanten. Manuscript, 1994.

[Ruz81] W. L. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22:365–383, 1981.

[RW91] Y. Roos and P. A. Wacrenier. Composition of two semi commutations. In A. Tarlecki, editor, Proceedings of the 16th Symposium on Mathematical Foundations of Computer Science (MFCS’91), Kazimierz Dolny (Poland) 1991, number 520 in Lecture Notes in Computer Science, pages 406–414, Berlin-Heidelberg-New York, 1991. Springer.

[Sei74] D. Seinsche. On a property of the class of n-colorable graphs. Journal of Combinatorial Theory B, B(16):191–193, 1974.

[Sto77] L. J. Stockmeyer. The polynomial time hierarchy. Theoretical Computer Science, 3:1–22, 1977.

[SV84] L. Stockmeyer and U. Vishkin. Simulation of parallel random access machines by circuits. SIAM Journal on Computing, 13(2):409–422, May 1984.

[Sze88] R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279–284, 1988.

[Teo93] Dan Teodosiu. Bereichseigenschaften komplexer Spuren. Diplomarbeit, Universität Stuttgart, 1993.

[Wol65] E.S. Wolk. A note on ’the comparability graph of a tree. In Proc. Amer. Math. Soc. 16, pages 17–20, 1965.

[Wra77] C. Wrathall. Complete sets and the polynomial hierarchie. Theoretical Computer Science, 3:23–33, 1977.

Index

M^{∗}, 14 NC^{k}, 12 T C^{0}, 12 ℕ, 7 ℕ_{+}, 7 Σ^{∗}, 7 Σ^{+}, 7 Σ_{k}^{P}, 10 Σ_{2}^{P}, 54 ℤ, 7 ·, 14 λ, 7 ≤^{f}, 11 ≤^{log}, 10 ≤^{nf}, 11 | M |, 7 | w |_{x}, 7 ∥, 9

⟹^{∗}, 7

⟹^{+}, 7

∗, 7, 14 +, 7 co−, 11 f_{SC}, 9

abgeschlossen, 11 Abhängigkeitsaphabet, 8 Abhängigkeitsrelation, 8 abstrakte Familie von Sprachen, 11,

21 AFL, 11, 21, 23 Alphabet, 7 atomar, 29

BLIND, 26 blinde Zähler, 26

CFL, 11 co-, 11 Cographen, 35 CSD, 30

diagonal, 34

DLOGTIME-Uniformität, 12

DSPACE, 9 DTIME, 9

Elementartransition, 15 endlicher Transducer, 10 erreichbarkeitsäquivalent, 18 Erreichbarkeitsmenge, 17 Erreichbarkeitsproblem, 13, 21 erweiterte Erreichbarkeitsmenge, 17

frei, 17

ggT, 7, 46

größte gemeinsame Teiler, 7

Grammatik, 7

Graphersetzungssystem, 8

Halbabhängigkeitsalphabet, 8 Halbabhängigkeitsrelation, 8 Halbspur, 8 Halbspurspache

Maximalität einer, 29 Halbspursprache, 9, 29

Maximalität einer, 31, 45, 48 Halbsursprache

Synchronisierbarkeit von, 50 Halteproblem, 21, 23 harte Kanten, 8

inhibitorische Kante, 13

Inhibitorkante, 13

Kante harte, 8 inhibitorische, 13 weiche, 8

Kommutationssystem, 8 Komposition, 9, 53 konfluent, 52 Kongruenz, 11 Konkatenation, 7 Konstantenmultimenge, 15 kontextfrei, 7

Leerheit einer Sprache, 21 LIN, 11, 26 linear, 7 LOG, 11 logarithmische Hülle, 11 logarithmischer Transducer, 10

Matrix, 14 maximal, 29 Maximalitat, 29 MC, 23, 26, 30 Monoid, 7 Multicounterautomat, 21 Multicountersprachen, 21, 23, 30 Multimenge, 14

NLOGSPACE, 10 noethersch, 52 NP, 10 NSPACE, 9 NTIME, 9

OCL, 11, 26 Orakel, 10

P, 10 PBLIND, 26 PCSD, 30 Periodenmultimengen, 15 Pfades, 15 PMC, 23 polynomielle Hierarchie, 10 PRAM, 12 Prioritätsmulticounterautomat, 21 Prioritätsmulticountersprachen, 23 Prioritätsnatürlichkeitstest, 27, 44 Produktionsregel, 7 Projektion, 7, 9 rationale Relation, 11 rationale Transduktion, 11 rationaler Transducer, 10 regulär, 7 reguläre Relation, 11 ROCL, 11, 26

Schaltbarkeitsproblem, 18, 20

schwache Zähler, 21 Semi-Dyck-Sprache, 11 Semikommutationen, 8 Semikommutationssystem, 8

atomares, 29 Semispur=Halbspur, 8 Semitrace=Halbspur, 8 Spiegelung, 7 Sprache, 7 Spuren, 8 Sternoperator, 7 Synchronisation, 9 Synchronisation von Halbspuren, 9 synchronisierbar, 9 Synchronisierbarkeit

von Halbsursprachen, 50

transitiver Wald, 34 Turingreduktion, 10

Unternetz, 16

vollständig, 11

Wörter, 7

weiche Kanten, 8

Zähler blinde, 26 schwache, 11, 21 starke, 11

Zählerhalbabhängigkeit, 30 Zählersemikommutationen, 30