CD-Systeme von Restart Automaten - Forschungsinformationssystem | Universität Kassel

ohne Drittmittelfinanzierung

CD-Systeme von Restart Automaten

Details zum Projekt

Projektlaufzeit: 01/2006–12/2010

Webseite: http://www.theory.informatik.uni-kassel.de/projekte

Zusammenfassung

Restart-Automaten sind ein formalsprachliches Modell fuer die in der Linguistik verwendete Analyse durch Reduktion. Tatsaechlich 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 koennen.

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 Komplexitaet und die Freiheit der Wortordnung einer Sprache modellieren.

Publikationen

2011	Messerschmidt, H., Otto, F., 2011. A hierarchy of monotone deterministic non-forgetting restarting automata. Theory of Computing Systems 343–373. https://doi.org/10.1007/s00224-009-9247-x
2010	Otto, F., 2010. CD-systems of restarting automata governed by explicit enable and disable conditions, in: van Leeuwen, J. (Hrsg.), SOFSEM 2010: Theory and Practice of Computer Science, Proc. Springer, Berlin, S. 627–638.
2008	Otto, F., 2008. Lower bounds for nonforgetting restarting automata and CD-systems of restarting automata. Universität Kassel, Kassel.
2007	Messerschmidt, H., Otto, F., 2007. Cooperating distributed systems of restarting automata. International Journal of Foundations of Computer Science 18, 1333–1342. https://doi.org/10.1142/S0129054107005376
2007	Messerschmidt, H., Otto, F., 2007. Strictly deterministic CD-systems of restarting automata, in: Csuhaj-Varju, E. and E. (Hrsg.), Fundamentals of Computation Theory, FCT 2007, Proc. Springer, Berlin, S. 424–434.