Jumping Automata on Graphs

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.