Jumping Automata on Graphs
jags.txt
—
Plain Text,
9 KB (9580 bytes)
Dateiinhalt
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 ungerichteten Graphen besuchen.
Artikelaktionen