Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2015/16 / Komplexitätstheorie / JAGs + Cook Rackoff


Inhaltsbereich

JAGs + Cook Rackoff

Plain Text icon jags.txt — Plain Text, 21 KB (21817 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
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<t
S(Ct)=S(Ct')=S, wobei P/S<P

Die Anzahl der Aequivalenzklassen von R1 ist hoechstens

R1 := (A0+1)*Q*P^P*Q ^ ^ ----- Display beim Zusammentreffen |
       |_________ Startzustand (der Berechnungsfolge) |
       _______________ Zeitpunkt des ersten Zusammentreffens (einschl
       oo)


Wir beachten, dass die Displays (im Falle C =1 C') auch noch ueber
dieses erste Zusammentreffen hinaus gleich bleiben, naemlich
zumindestens bis wiederum bei einem der beiden Berechnungen wieder
Pebbles zusammentreffen. Dies aus demselben Grund wie oben, weil eben
die Zuege nur von den Displays abhaengen.

Ja selbst ein weiteres Zusammentreffen von Pebbles muss die
Uebereinstimmung nicht zerstoeren, und zwar dann nicht, wenn die
zusammentreffenden Pebbles wieder die vom Zeitpunkt t sind, denn die
haben sich ja dann seit t in der exakt gleichen Weise (bei beiden
Berechnungen) auseinanderbewegt und treffen deshalb, wenn sie es in
der einen Berechnung tun, auch zur selben Zeit in der anderen
zusammen.

Mithilfe der Aequivalenzrelation =1 koennen wir nun auch die Zahl der
moeglichen Konfigurationen in einer Berechnung abschaetzen, in der
einmal Pebbles unerwartet zusammentreffen. Sei also C=C0,C1,... eine
solche Berechnung. Nach spaetestens R1 Schritten sehen wir naemlich
dieselbe =1-Aequivalenzklasse und ab da wiederholen sich also die
Zuege mit Periode R1.

Es ergibt sich also fuer die Anzahl A1 dieser Konfigurationen die
Abschaetzung

A1 <= R1 + (P + m*P!)*R1 = (1+P+m*P!) * R1

Um uns in dieser Weise weiter vorarbeiten zu koennen, muessen wir das
Konzept des "unerwarteten Zusammentreffens sauber definieren und
fuehren dazu "Superdisplays" ein. Ein Superdisplay besteht aus einem
Zustand und einer Funktion

               d : PxP -> (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<min(COAL_2(C),
COAL_2(C')).

Wir definieren jetzt allgemein

C =n C' <==> 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 <m
Inkrementen der 1. Komponente, gefolgt von <m Inkrementen der zweiten
Komponente etc.

Der lexikografische Nachfolger eines Punktes c ist wie ueblich
definiert, also 1. Komponente inkrementieren, falls <m-1. Sind die
ersten k Komponenten alle =m-1 und die k+1-te <m-1, dann die ersten k
auf Null setzen (oder inkrementieren, was denselben Effekt hat) und
die k+1-te inkrementieren.

Der Automat arbeitet nun in Runden; nach Abschluss jeder Runde wurde
das Laufpebble auf den lexikografischen Nachfolger seiner Position zu
Beginn der Runde gesetzt. Auf diese Weise durchlaeuft das Laufpebble
also alle Knoten.

Eine einzelne Runde verlaeuft nun so: Der Automat raet
nichtdeterministisch einen kanonischen Pfad von n hin zum Laufpebble
und verschiebt m entlang dieses Pfades. Zu Beginn liegt also m bei n;
dann wird eine bestimmte (nichtdeterministisch zu ratende Zahl von
Malen) die 1. Komponente inkrementiert, dann die zweite etc. Trifft
das Pebble m dann auf c, so wird weitergemacht, anderenfalls
abgebrochen ("FAIL"). In dem Masse, wie sich m auf c zubewegt, kann
nun m' in einer solchen Weise, dass es am Ende auf der
lexikografischen Nachfolgerposition liegt. Man muss naemlich nur m' an
den richtigen Stellen jeweils einmal oefter inkrementieren als m.

So kann man also im Erfolgsfalle dann c auf m' setzen. 

Weitere Arbeiten der LFE TCS im Bereich der Komplexitaetstheorie
betreffen Charakterisierungen von P und PSPACE durch syntaktisch
eingeschraenkte funktionale Programme, insbesondere Einschraenkungen
bei der Rekursion. Dies liefert auch Anwendungen auf die konkrete
Laufzeitanalyse. Eine Einfuehrung mit Bezug auf diese Vorlesung findet
sich in der ASCII Notiz proglang.txt, die ebenfalls verlinkt ist.

Artikelaktionen


Funktionsleiste