Projekt A20 - Alternierende Automaten und Grammatiken

(geplante Laufzeit: 04/2001 bis 12/2013)

Alternierenden Pushdown-Automaten charakterisieren gerade die Zeitkomplexitätsklasse EXPTIME = \bigcup_{c>0} (∪c>0) DTIME(2^{c\cdot n}) (2c·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?

Mitarbeiter:

Dieter Hofbauer

Maria Huber

Etsuro Moriya
(Department of Mathematics, Waseda University, Tokyo, Japan)

Technische Reports:

Moriya, E. and Otto, F.:
On alternating non-context-free grammars
Kasseler Informatikschriften (KIS) 6/2007, Universität Kassel, November 2007.
Moriya, E., Hofbauer, D., Huber, M. and Otto, F.:
On State-Alternating Context-free Grammars.
Mathematische Schriften Kassel 1/04, Universität Kassel, Februar 2004.
Moriya, E., Hofbauer, D., Huber, M. and Otto, F.:
On State-Alternating Context-free Grammars - With Detailed Proofs and Supplementary Results -.
Technical Report 2003-5, Advanced Research Institute for Science and Engineering, Waseda University, November 2003.
Otto, F. and Moriya, E.:
Shrinking alternating two-pushdown automata.
New Aspects of Theoretical Computer Science, RIMS Kokyuroku 1325, S. 191-196, Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan, May 2003.
Otto, F. and Moriya, E.:
Shrinking alternating two-pushdown automata.
Mathematische Schriften Kassel 12/01, Universität-GH Kassel, August 2001.

Veröffentlichungen:

Moriya, E. and Otto, F.:
On alternating phrase-structure grammars
Int. Journal of Foundations of Computer Science 2010, 21:1--25.
Otto, F. and Moriya, E.:
On alternating phrase-structure grammars.
In: Martin-Vide, C., Otto, F. and Fernau, H. (eds.), Language and Automata Theory and Applications, LATA 2008, Proc. Lecture Notes in Computer Science 5196, pages 397-408, Springer, Berlin, 2008.
Moriya, E. and Otto, F.:
Two ways of introducing alternation into context-free grammars and pushdown automata.
IEICE Trans. Inf. & Syst. 2007, E90-D:889--894.
Moriya, E., Hofbauer, D., Huber, M. and Otto, F.:
On State-Alternating Context-free Grammars.
Theoretical Computer Science 2005, 337:183--216.
Otto, F. and Moriya, E.:
Shrinking alternating two-pushdown automata.
IEICE Trans. Inf. & Syst. 2004, E87-D:959-966.