Projekt ohne Drittmittelfinanzierung

Alternierende Automaten und Grammatiken


Details zum Projekt
Projektlaufzeit: 04/200112/2011


Zusammenfassung
Alternierende Pushdown-Automaten charakterisieren gerade
die Zeitkomplexitätsklasse
EXPTIME = igcup_{c>0} DTIME(2^{ccdot n})
[Chandra, Kozen, Stockmeyer 1981], d.h.,
durch die Erweiterung
zum alternierenden Pushdown-Automaten wird die Ausdruckskraft
des gewöhnlichen Pushdown-Automaten erheblich ausgeweitet.
Kann man nun die kontext-freien Grammatiken entsprechend erweitern?
Dabei kann man den Ansatz wählen, die Menge der Nichtterminale
in existenzielle und universelle Nichtterminale aufzuteilen, oder
man kann Grammatiken mit Zuständen versehen, wobei man dann
zwischen existenziellen und universellen Zuständen unterscheidet.
Wie verhalten sich die durch diese Grammatikklassen definierten Sprachklassen
zueinander und zur obigen Klasse EXPTIME? Wie können alternierende
Varianten der kontext-sensitiven und der allgemeinen Phrasenstrukturgrammatiken
definiert werden?
Die schrumpfenden Zweikeller-Automaten (sTPDA) akzeptieren gerade die
wachsend kontext-sensitiven Sprachen [Buntrock, Otto 1998].
Durch die entsprechende Verallgemeinerung erhält man die
schrumpfenden alternierenden Zweikeller-Automaten sATPDA.
Welche Sprachklasse wird von diesen Automaten akzeptiert?
Desweiteren kann man alternierende Varianten anderer Automatenmodelle
definieren und analysieren, wie zum Beispiel die
Restart-Automaten.
Wie verändert sich jeweils die Ausdruckskraft dieser Automatenmodelle,
und welche Abschlusseigenschaften und Entscheidbarkeitseigenschaften
haben die entstehenden Sprachklassen?


Projektleitung


Publikationen

2010
2008
2007
2005
2004
2003
2003

Zuletzt aktualisiert 2017-11-07 um 14:51