Projekt 1 - CD-Systeme von Restart-Automaten

(Beginn: 01/2006)

Restart-Automaten sind ein formalsprachliches Modell für die in der Linguistik verwendete Analyse durch Reduktion. Tatsächlich besteht dieser Analyseprozess aber aus wenigstens drei Stufen: der Annotierung, der Disambiguierung und der eigentlichen Reduktionsanalyse. Statt jede dieser Stufen durch ein eigenes theoretisches Modell zu beschreiben, bietet es sich an, den Gesamtprozess durch ein kooperierendes, verteiltes System (d.h. ein CD-System) von Restart-Automaten zu modellieren. Dies hat den Vorteil, dass alle Stufen in einer einheitlichen Form beschrieben werden, und dass sie enger miteinander verzahnt werden können.

Im Rahmen dieses Projekts sollen die verschiedenen Varianten der CD-Systeme von Restart-Automaten untersucht und in Beziehung zueinander und zu den mehr klassischen Sprachfamilien und Automatenmodellen gesetzt werden. Dabei sind solche Varianten von besonderem Interesse, die linguistisch relevante Konzepte wie etwa die Komplexität und die Freiheit der Wortordnung einer Sprache modellieren.

Mitarbeiter:

Hartmut Messerschmidt

Technische Reports:

Otto, F.:
Lower bounds for nonforgetting restarting automata and CD-systems of restarting automata
Kasseler Informatikschriften (KIS) 2/2008, Universität Kassel, October 2008.

Veröffentlichungen:

Messerschmidt, H. and Otto, F.:
A hierarchy of monotone deterministic non-forgetting restarting automata.
Theory of Computing Systems 48 (2011) 343-373.
Otto, F.:
CD-systems of restarting automata governed by explicit enable and disable conditions.
In van Leeuwen, J., Muscholl, A., Peleg, D., Pokorný, J. and Rumpe, B., editors, SOFSEM 2010: Theory and Practice of Computer Science, Proc., Lecture Notes in Computer Science 5901, pages 627-638, Springer, Berlin, 2010.
Messerschmidt, H. and Otto, F.:
On deterministic CD-systems of restarting automata.
Int. Journal of Foundations of Computer Science 20 (2009) 185-209.
Messerschmidt, H.:
CD-Systems of Restarting Automata
Dissertation, Fachbereich Elektrotechnik/Informatik, Universität Kassel, 2008.
Messerschmidt, H. and Otto, F.:
Cooperating distributed systems of restarting automata.
Int. Journal of Foundations of Computer Science 18 (2007) 1333-1342.
Messerschmidt, H. and Otto, F.:
Strictly deterministic CD-systems of restarting automata.
In Csuhaj-Varjú, E. and Ésik, Z., editors, Fundamentals of Computation Theory, FCT 2007, Proc., Lecture Notes in Computer Science 4639, pages 424-434, Springer, Berlin, 2007.