Zeigerstrukturen und Graphautomaten =================================== Zeigerstrukturen ---------------- Sei Sigma eine endliche Menge von "Zeigern". Eine Sigma-Zeigerstruktur ist ein Paar (V,E) wobei V eine endliche Menge von Knoten ist und E : V x Sigma -> V eine Funktion, die Kantenfunktion, ist. Man schreibt auch v.l fuer E(v,l). Man kann sich die Knoten einer Zeigerstruktur als Objekte vorstellen und Sigma als Menge der Feldnamen. Eine Zeigerstruktur modelliert dann einen UML Objektgraphen. Ein regulaerer ungerichteter Graph vom Grad d besteht aus einer Menge von Knoten, sodass jeder Knoten genau d Nachbarn hat und diese Nachbarknoten angeordnet sind. Ausserdem ist die Nachbarrelation symmetrisch. Formal kann man einen d Graphen modellieren als Menge V von Knoten und eine Funktion Adj:V->V^d, die jedem Knoten v seine d Nachbarn als Adjazenzliste zuordnet. Zu jedem v,i gibt es v',j mit v'=Adj(v)_i und v=Adj(v')_j. Da diese v',j eindeutig bestimmt sind, kann man die Rotationsabbildung Rot : V x D -> V x D durch Rot(v,i) = (v',j) wie oben definieren, wobei D ={1,...,d} Offensichtlich kann solch ein regulaerer ungerichteter Graph als Zeigerstruktur mit Sigma=D aufgefasst werden. Auch regulaere gerichtete Graphen lassen sich in aehnlicher Weise als Zeigerstrukturen repraesentieren, wobei man unterscheiden kann, ob Kanten nur in einer, oder in beiden Richtungen navigierbar sein sollen. In letzterem Falle wird man Sigma=Sigma_V+Sigma_R waehlen, wobei Sigma_V die Vorwaerts- und Sigma_R die Rueckwaertskanten repraesentiert. Will man nicht-regulaere Graphen repraesentieren, deren Knoten also nicht alle denselben Grad haben, aber nach wie vor lokal angeordnet sind, so repraesentiert man die Adjazenzlisten nicht als d-Tupel, sondern als einfach oder doppelt verkettete, oder zirkulaere Listen. D.h. man hat Sigma={adj,next,elem} o.ae., wobei die Adjazenzliste von v der Laenge l durch l viele Hilfsknoten repraesentiert wird, naemlich v.adj, v.adj.next. v.adj.next.next, .... wobei v.adj.next^l=v.adj. Fuer jeden dieser Hilfsknoten w liefert w.elem, den ihnen zugeordneten Graphknoten. Fuer die Graphknoten definiert man z.B v.elem=v, sodass auf diese Weise die Graphknoten von den Hilfsknoten unterschieden werden koennen. Man kann auch Graphen ohne lokale Ordnung auf den Nachbarn eines Knotens als Zeigerstrukturen repraesentieren: Ist naemlich ein Graph G=(V,E) mit E <= VxV gegeben, so kann man diesen z.B. durch eine Zeigerstruktur ueber V+E mit Alphabet Sigma={s,t} repraesentieren, wobei v.s=v.t=v fuer v:V und (v,v').s = v und (v,v').t = v' fuer (v,v'):E. Unter Verwendung der aus der objektorientierten Modellierung bekannten Muster lassen sich auch viele andere Datenstrukturen als Zeigerstrukturen darstellen. Fuer die Theorie wichtig sind besondere Zeigerstrukturen, die sich aus Gruppen mit Erzeugern ergeben. Ist naemlich G eine Gruppe mit Erzeugern d_1,...,d_n, so erhaelt man eine Zeigerstruktur ueber Sigma={1,..,n} oder {d_1,...,d_n} und V=G, wobei fuer g:V dann v.i = v*d_i gesetzt wird. Man nennt den so entstehenden Graphen, den Cayley Graphen der Gruppe G, bzw ihrer Praesentation. Beispiel: G = Z_5, Sigma={1}. Der Cayley-Graph besteht aus fuenf Knoten, die auf einem Kreis angeordnet sind. Beispiel: G = Z_5^2, Sigma={(1,0), (0,1)}. Die Elemente von G sind Paare von Zahlen mod 5, die komponentenweise addiert werden. Der Cayleygraph bildet einen 2D-Torus. Jumping Automata on Graphs -------------------------- Cook und Rackoff haben "Jumping Automata on Graphs" (JAG) eingefuehrt als Abstraktion von Berechnungen auf Zeigerstrukturen, die eine konstante Zahl von Knoten speichern koennen und ausserdem auf Graphknoten nur abstrakt zugreifen koennen, also als Elemente eines abstrakten Datentyps, der nur den Gleichheitstest und das Verfolgen von Kanten unterstuetzt. So waere beispielsweise die Tiefensuche auf zykelfreien Graphen mit der Rechte-Hand-Regel (so gehen, dass man die rechte Hand nicht von der Wand nehmen muss) auf einem JAG implementierbar; die allgemeine Tiefensuche aber nicht (da man sich mehr als eine konstante Zahl von Knoten merken muss). JAGs koennen in logarithmischem Platz simuliert werden, da ein einzelner Knoten mit log. Platz gespeichert werden kann und somit auch eine konstante Zahl von denselben. Die Umkehrung gilt nicht; so kann man z.B. in log. Platz feststellen, ob die Zahl der Knoten eines gegebenen Graphen eine bestimmte Eigenschaft hat, z.B. eine Zweierpotenz ist. Auch kann ein JAG nicht feststellen, ob ein gegebener Graph eine bestimmte Konfiguration, etwa eine 5er Clique enthaelt. Formal wird ein JAG definiert als Tupel AA = (Sigma,Q,q0,P,delta,F) wobei * Sigma ein endliches Alphabet von Richtungen oder Zeigern ist, * Q eine endliche Menge von Zustaenden ist, * q0:Q der Startzustand ist * P eine endliche Menge von Pebbles (Marken, (Zeiger)-Variablen) ist, * delta eine Uebergangsrelation ist, s.u. * F das Terminierungs- und Akzeptanzverhalten definiert, z.B. durch Festlegung von akzeptierenden und verwerfenden Haltezustaenden. delta ist eine Menge von Quadrupeln der Form (q,S,q',m), wobei q der aktuelle und q' der Folgezustand ist, S eine Aequivalenzrelation auf P, die aktuelle Inzidenzrelation ist und m:P->P+Sigma die Bewegungen jeder Marke beschreibt. Der Automat ist deterministisch, wenn zu jedem q,S genau ein q',m existiert mit (q,S,q',m):delta. Man schreibt dann wie ueblich delta(q,S)=(q',m). Man kann beispielsweise einen Irrgarten durch eine Zeigerstruktur ueber Sigma={S,N,O,W} repraesentieren, mit der Massgabe, dass Knoten Feldern entsprechen, wobei v' := v.S das suedliche Nachbarfeld zu v repraesentiert, wenn v'=/=v und kein suedliches Nachbarfeld vorhanden ist, wenn v'=v'. Folgender JAG bewegt die Marke b ("Besucher") immer in die naechste freie Richtung, bis entweder die Zielmarke t erreicht ist, oder kein Zug moeglich ist. Pseudocode: 1: done:=false; 2: accept:=false; 3: while(!done) { 4: if b==t then accept=true;done = true;break; 5: c=b;b=b.S; 6; if b =/= c break; 7: b=b.N; 8: if b =/= c break; 9: b=b.O; 10: if b=/=c break; 11: b=b.W; 12: if b =/= c break; 13: done:=true;} 14:; Formal: Q = {(p,done,accept) | p:{1,2..,14}, done:{true,false}, accept:{true,false}} 56 Zustaende q0 = (1,false,false) F = {(p,done,accept) | p=10, accept=true} u {(p,done,accept) | p=10, accept=false} P = {b,c,t} delta((1,done,accept),S) = (2,false,accept),id delta((2,done,accept),S) = (3,false,false),id delta((3,true,accept),S) = (10,true,accept),id delta((3,false,accept),S) = (4,false,accept),id delta((4,done,accept),S) = (3,true,true),id falls (b,t):S delta((4,done,accept),S) = (5,done,accept),id falls (b,t) nicht in S delta((5,done,accept),S) = (6,done,accept),bcS delta((6,done,accept),S) = (3,done,accept),id falls (b,c) nicht in S delta((6,done,accept),S) = (7,done,accept),id falls (b,c) in S delta((7,done,accept),S) = (8,done,accept),bN ... Hierbei ist id(p)=p, bcS(c)=b, bcS(b)=S, bcS(t)=t, bN(c)=c, bN(b)=N, bN(t)=t, Definition: Eine globale Konfiguration eines JAG auf einer Zeigerstruktur (V,E) ueber demselben Alphabet ist ein Paar C=(q,M), wobei q:Q und M : P -> V jedem Pebble einen Knoten zuweist. Jeder solchen Belegung M weist man eine Aequivalenzrelation S(M) auf den Pebbles durch (i,j):S(M)<=>M(i)=M(j) (Inzidenzrelation). Eine Bewegung m:P->P+Sigma wirkt auf Belegungen M durch m(M)(i) = M(j), falls m(i)=j; m(M)(i)=M(i).l, falls m(i)=l:Sigma. Die Ein-Schritt-Relation zwischen globalen Konfigurationen ist gegeben durch (q,M) -> (q',m(M)), falls (q,S(M),q',m);delta. Ist der Automat deterministisch, so existiert genau eine Folgekonfiguration. Man erhält dann aus einer Stratkonfiguration C=C0 eine eindeutig bestimmte Folge von Konfigurationen C0->C1->C2->C3-> ... Man sagt, der deterministische Automat besuche Knoten v von s aus, wenn ausgehend von C0=(q0,M0) mit M0(p)=s fuer alle s, der Knoten v irgendwann in der Folge (Ci)i auftaucht, also i existiert mit Ci=(qi,Mi) und Mi(p)=v fuer ein p:P und i:N. Im Falle eines nichtdeterministischen Automaten gibt es mehrere Berechnungsfolgen. Man fixiert hier zwei besondere Zustaende FAIL und DONE, sowie ein besonderes Pebble c (Cursor). Eine Berechnungsfolge ausgehend von C0=(q0,M0) ist gueltig, genau dann, wenn der Zustand FAIL in ihr nicht auftritt und der Zustand DONE auftritt. Eine Folge mit FAIL ist also ungueltig und ebenso unendliche Folgen, in denen zwar FAIL nicht vorkommt, DONE aber auch nicht. Man koennte FAIL nach einem DONE erlauben, aber auch leicht durch Umbau des Automaten ausschliessen. Ein nichtdeterministischer Automat zaehlt eine Teilmenge U der Knoten auf, wenn es eine gueltige Berechungsfolge gibt und in jeder gueltige Berechungsfolge das Pebble c die Elemente von U besucht und zwar in einer festen Reihenfolge und jedes nur einmal. Satz von Cook-Rackoff --------------------- Es sei G die Gruppe G=(Z_m)^d. Ihre Elemente sind d-Tupel von Zahlen modulo m mit punktweiser Addition. Als Generatoren verwenden wir e1..ed, und d1..dd wobei ei die i-te Komponente inkrementiert und di diese dekrementiert. Also z.B. e2=(0,1,0,..,0). Wir betrachten den Cayley-Graphen CG(G) von G als Zeigerstruktur ueber Sigma={e1..ed,d1..dd}. Satz von Cook-Rackoff: Es gibt eine Konstante c>0 mit der folgenden Eigenschaft. Sei A ein det JAG mit Q Zustaenden und P Pebbles. Ausgehend von einem beliebigen Startknoten kann A in CG(Z_m^d) hoechstens (mQ)^c^P Knoten besuchen. Korollar: Kein fester det. JAG kann alle erreichbaren Knoten eines beliebigen ungerichteten Graphen besuchen. Korollar: Kein fester det. JAG kann entscheiden, ob zwei (durch Pebble) gegebene Knoten eines ungerichteten Graphen miteinander durch einen Pfad verbunden sind (STCONN). Beweis des Satzes von Cook-Rackoff: - - - - - - - - - - - - - - - - - - Seien fuer den Beweis des Satzes Parameter d,m, entsprechende Zeigerstruktur V = (Z_m)^d, und ein JAG mit Komponenten Q,P,delta, fixiert. Wir kuerzen |P| mit P und |Q| mit Q ab. Ist C=(q,M) eine Konfiguration, so bezeichnen wir D(C) := (q,S(M)) als "Display" der Konfiguration. Lemma: Sei alpha = m1;m2;m3...;ml eine Folge von Zuegen, also mi:P->P->Sigma. Es gibt Funktionen f : P->(Z_m), g : P->P, die alpha in folgendem Sinne implementieren. Ist M eine Markierung und M'=alpha(M)=ml(m(l-1)(...m2(m1(M))...). Dann ist M'(p) = f(p) + M(g(p)) Beweis: Durch Induktion ueber l. Leicht. Lemma: Sei M0,M1,M2,... eine Folge von Markierungen (Funktionen P->V) gegeben und alpha=m1;...;ml eine feste Zugfolge, sodass M(i+1)=alpha(Mi) im Sinne des Lemmas, dann gilt M_{P+k*m*P!} = M_P fuer alle k>=0. D.h. nach einer Einschwingzeit von P wiederholen sich die Markierungen mit Periode m*P! (oder einem echten Teiler davon). Beweis: Fuer jede Funktion g:P->P gilt g^P = g^{P+k*P!} fuer alle k, da der nach spaetestens P Schritten ein Zyklus erreicht wird und alle Zyklen Groesse hoechstens P haben. Jedes gemeinsame Vielfache aller Zykellaengen ist eine passende Periode; P! ist eine solche. [] Wir betrachten eine Berechnungsfolge C0,C1,C2,.... wobei Ci=(qi,Mi) und---das ist ein seltener Spezialfall!--- |P/S(Mi)|=P, d.h. zu Beginn liegen alle Pebbles auf unterschiedlichen Knoten und das bleibt auch waehrend der gesamten Berechnung so. Wir betrachten die Folge der Displays D(C0), D(C1), D(C2), ... und beachten, dass Ci+1 nur von D(Ci), nicht aber von Ci selbst abhaengt. Da die Zahl der Displays durch Q abgeschaetzt werden kann (nur der Zustand aendert sich), muss es i < j <= Q geben, sodass D(Ci) = D(Cj). Das bedeutet, dass die Zuege sich ab Zeitpunkt i mit Periode j-i wiederholen. Sei alpha die entsprechende Zugfolge der Laenge j-i. Wenden wir das vorhergehende Lemma auf dieses alpha an, so sehen wir, dass die gesamte Berechnungsfolge hoechstens A0 := Q + Q * (P + m * P!) viele unterschiedliche Konfigurationen enthaelt, egal wie weit wir sie verfolgen. Nun kann es aber sein, dass im Verlaufe der Berechnung irgendwann zwei oder auch mehrere Pebble aufeinandertreffen. Nachdem bis zu diesem ersten Aufeinandertreffen nach dem Vorhergesagten hoechstens A0 viele verschiedene Konfigurationen moeglich sind, passiert ein solches entweder nach spaetestens A0 Schritten oder ueberhaupt nicht. Wir definieren die Aequivalenzrelation =1 auf Konfigurationen wie folgt: C =1 C' <==> das erstmalige Zusammentreffen zweier Pebble von C und C' aus erfolgt zur gleichen Zeit und bis einschliesslich dahin stimmen die Displays ueberein. Formal: D(Ci) = D(Ci') fuer i=0..t P/S(Ci) = P/S(Ci') = P fuer alle i (Z_d)^m + {?} die bekannte Abstaende modellieren soll. Es muss daher gelten: d(p,p')=d(p',p) und d(p,p)=0 und d(p,p')=z != ? und d(p',p'')=z' != ? ==> d(p,p'') = z+z' Jeder Berechnungsfolge C=C0->C1->C2->... ordnet man nun eine Superdisplay-Folge SD_0, SD_1, ... zu beginnend mit SD_0=q0,d0, wobei d0(p,p)=0, d(p,p')=?, sonst. Das jeweils naechste Superdisplay ergibt sich in offensichtlicher Weise durch Fortschalten gemaess der entsprechenden Zuege. Definition: Die n-te Koalition einer Konfigurationsfolge beginnend bei C ist der Zeitpunkt t des n-ten unerwarteten Zusammentreffens von Pebbles. Formal ist t der erste Zeitpunkt zu dem die durch SD_t induzierte Aequivalenzrelation auf den Pebbles P-n Klassen oder weniger hat. NB: "durch d induzierte Aequivalenzrelation: p~p'<=>d(p,p') != ? Wir schreiben COAL_n(C) fuer diesen Zeitpunkt. Liegen z.B. in C alle Pebbles auf demselben Knoten, so ist COAL_n(C)=0 fuer alle n. Gibt es drei Pebbles p,p',p'' und liegen diese in C auf (0,0), (1,0), (1,1) und sind die ersten drei Bewegungen p:=p+(1,0) und p':=p'' und p=p+(0,1), p'':=p''-(1,0) so entsteht die Markierungsfolge 0 (0,0), (1,0), (1,1) 1 (1,0), (1,0), (1,1) 2 (1,0), (1,1), (1,1) 3 (1,1), (1,1), (0,1). Die erste Koalition findet zur Zeit 1 statt (p und p' treffen zusammen). Zur Zeit 2 gibt es kein unerwartetes Zusammentreffen; die zweite Koalition passiert erst zur Zeit 3. Hier sind alle relativen Pebbleabstaende bekannt. Ist also C =1 C', so folgt D(Ci)=D(Ci') fuer alle t COAL_n(C)=COAL_n(C')=:t und D(Ci)=D(Ci') fuer alle i<=t Rn := Anzahl der Aequivalenzklassen von =n An := Anzahl der verschiedenen Konfigurationen in einer Berechnung von einer beliebigen Startkonfiguration bis zur n-ten Koalition. Durch Verallgemeinerung des Vorhergesagten ergeben sich die folgenden Abschaetzungen: (I) An <= (1 + P + m*P!) * Rn (II) R(n+1) <= Rn * (An * P^P + 1)* Q * P^P Begruendung: (I): Nach Rn Schritten wiederholt sich die Rn-Klasse und damit die Zugfolge. Damit wiederholen sich aufgrund des Lemmas nach jeweils P+mP! Wiederholungen auch die Konfigurationen. (II): Damit zwei Konfigurationen =(n+1) aequivalent sind, muessen sie =n aequivalent sein (Rn Moeglichkeiten), die Zeitpunkte der n+1 Koalition muessen uebereinstimmen (An * P^P +1 Moeglichkeiten: An viele Konfigurationen, zusaetzlich muss die durch das SD induzierte Aequivalenzrelation uebereinstimmen (P^P), oder oo). Zu diesem Zeitpunkt muessen dann Zustand und Display gleich sein (Q*P^P). Aus diesen Abschaetzungen folgt durch reines Rechnen A_P <= (mQ)^c^P fuer geeignetes c und A_P beschraenkt die Zahl der besuchbaren Positionen. PURPLE ------ Bei JAGs spielt der Art der Praesentation einer Datenstruktur eine wichtige Rolle, etwa ob Kanten nur einseitig oder bidirektional navigierbar sind. Ausserdem koennen unerreichbare Knoten grundsaetzlich nicht besucht werden. Wir (Uli Schoepp und MH) haben daher die Programmiersprache PURPLE eingefuehrt, die JAGs um eine for Schleife erweitert, welche es erlaubt alle Knoten der Eingabe in einer bestimmten Reihenfolge zu durchlaufen. Diese Reihenfolge ist nicht spezifiziert und sie kann auch bei jedem Durchlauf eine andere sein. Damit ein PURPLE Programm eine bestimmte Funktion berechnet, muss es das unabhaengig von der Durchlaufreihenfolge tun. Man kann auf diese Weise zum Beispiel Kanten in umgekehrter Richtung navigieren, oder nach bestimmten Konfigurationen suchen, z.B. eine 5er Clique. Wir haben gezeigt, dass auch PURPLE Programme das Problem STCONN nicht entscheiden koennen. Hierzu werden Cayley Graphen ueber einer komplizierteren nichtkommutativen Gruppe betrachtet und gezeigt, dass sie auf dieser Gruppe durch JAGs mit sehr grosser Zustandszahl simuliert werden. Daraus ergab sich auch die Loesung einer offenen Frage ueber Definierbarkeit in einem bestimmten logischen System (first-order + deterministic transitive closure). Schoepp+MH: Pure pointer programs with iteration. ACM Trans. Comput. Log. 11(4), 2010. Wir haben dann versucht, Erweiterungen von PURPLE zu finden, mit denen zwar STCONN loesbar ist, aber moeglicherweise das P-vollstaendige Problem HORNSAT nicht, was dann als Evidenz fuer L != P gedeutet werden koennte. Die bisher probierten Erweiterungen, wie Rekursion und Arithmetik erwiesen sich allerdings als fuer diesen Zweck ungeeignet, da sie die Ausdrucksmaechtigkeit gleich auf LOGSPACE oder gar P erhoehen. Ein erfolgversprechender Kandidat ist allerdings verblieben: Nichtdeterministische JAGs, bzw nichtdeterministisches PURPLE. Wir konnten zeigen, dass mit einem nichtdeterministischen JAG (ndJAG) alle Knoten des Cayley Graphen zu (Z_m)^d besucht werden koennen und dass dies auch fuer viele weitere Cayley Graphen der Fall ist. Wir versuchen daher im Moment zu zeigen, dass ndJAGs gleichmaechtig mit NL sind (was eine interessante neue Charakterisierung von NL darstellen wuerde) und gleichzeitig, dass HORN nicht mit ndJAGs entschieden werden kann. Beides zusammen wuerde NL von P trennen, was uns kaum gelingen wird, aber es bleibt zu hoffen, dass eines der beiden Resultate erreichbar sein koennte. [Ramyaa and MH: Computing with a fixed number of pointers (Invited Talk). Annual Conference on Foundations of Software Technology and Theoretical Computer Science, {FSTTCS} 2013, December 12-14, 2013, Guwahati, India http://dblp.uni-trier.de/rec/bib/conf/fsttcs/0001R13 Zum Abschluss hier die Konstruktion eines ndJAG zur Aufzaehlung aller Knoten von (Z_m)^d. Wir benutzen ein Laufpebble c, zwei Hilfspebble m,m' und ein Nullpebble n, welches immer an einem festen Knoten liegenbleibt, oBdA dem Nullpunkt. Der "kanonische Pfad" von n zu einem beliebigen Punkt c besteht aus