Projekt A17 - Restart-Automaten: Varianten, Abschlußeigenschaften und Komplexität von Entscheidungsproblemen

(Laufzeit: 07/2001 bis 06/2007)

Die Restart-Automaten sind ein theoretisches Modell für die in der Linguistik verwendete Analyse durch Reduktion, bei der Sätze analysiert werden, indem sie durch das wiederholte Ersetzen von Satzteilen vereinfacht werden. Dabei wird dieser Ersetzungsprozeß solange iteriert, bis entweder ein Fehler entdeckt wird, oder bis ein korrekter elementarer Satz erreicht wird. Durch die verschiedenen Varianten der Restart-Automaten, wie deterministisch oder nicht-deterministisch, monoton oder nicht-monoton, etc. ergibt sich eine ganze Hierarchie von Sprachklassen, wobei die kontext-freien Sprachen, die deterministischen kontext-freien Sprachen und die Church-Rosser Sprachen als spezielle Klassen auftreten.

Im Rahmen dieses Projekts soll der Einfluß weiterer syntaktischer Faktoren auf die Ausdruckskraft der verschiedenen Varianten der Restart-Automaten untersucht werden. Eine zentrale Frage ist dabei die nach dem Bezug der sich jeweils ergebenden Sprachklasse zu den wachsend kontext-sensitiven Sprachen auf der einen Seite und zu den allgemeinen kontext-sensitiven Sprachen auf der anderen Seite. Ferner interessiert insbesondere, inwieweit die Trennung der eigentlichen Reduktionsschritte von den Restart-Schritten die Ausdruckskraft dieser Automaten erhöht.

Dieses Projekt ist in der Zeit von Juni 2003 bis September 2006 durch die DFG gefördert worden. Inzwischen liegt der Abschlussbericht für die DFG vor.

Mitarbeiter:

Tomasz Jurdzinski
(jetzt: Institute of Computer Science, University of Wroclaw, Polen)

Krzysztof Lorys
(Institute of Computer Science, University of Wroclaw, Polen)

Frantisek Mráz
(Department of Computer Science, Charles University Praha, Czech Republic)

Gundula Niemann
(jetzt: SAP Deutschland)

Martin Plátek
(Department of Computer Science, Charles University Praha, Czech Republic)

Technische Reports:

Messerschmidt, H., Mráz, F., Otto, F. and Plátek, M.:
On the descriptional complexity of simple RL-automata
Mathematische Schriften Kassel 4/06, Universität Kassel, April 2006.
Mráz, F., Otto, F. and Plátek, M.:
On the Gap-Complexity of Simple RL-Automata
Mathematische Schriften Kassel 2/06, Universität Kassel, März 2006.
Mráz, F., Otto, F. and Plátek, M.:
Learning analysis by reduction from positive data
Mathematische Schriften Kassel 7/05, Universität Kassel, September 2005.
Mráz, F., Otto, F. and Plátek, M.:
Degrees of Free Word-Order and Freely Rewriting Restarting Automata
Mathematische Schriften Kassel 5/05, Universität Kassel, Juli 2005.
Jurdzinski, T. and Otto, F.:
Restarting Automata with Restricted Utilization of Auxiliary Symbols
Mathematische Schriften Kassel 2/05, Universität Kassel, April 2005.
Jurdzinski, T. and Otto, F.:
Shrinking restarting automata
Mathematische Schriften Kassel 1/05, Universität Kassel, Februar 2005.
Jurdzinski, T., Mráz, F., Otto, F. and Plátek, M.:
Cut hierarchies for restarting automata and Marcus t-contextual grammars
Mathematische Schriften Kassel 21/04, Universität Kassel, Dezember 2004.
Jurdzinski, T., Mráz, F., Otto, F. and Plátek, M.:
Deterministic two-way restarting automata and Marcus contextual grammars
Mathematische Schriften Kassel 18/04, Universität Kassel, November 2004.
Jurdzinski, T. and Otto, F.:
Sequential monotonicity for restarting automata
Mathematische Schriften Kassel 10/04, Universität Kassel, September 2004.
Jurdzinski, T., Mráz, F., Otto, F. and Plátek, M.:
Deterministic two-way restarting automata don't need auxiliary symbols if they are (right-, left-, or right-left-) monotone
Mathematische Schriften Kassel 7/04, Universität Kassel, September 2004.
Otto, F.:
Restarting Automata - Notes for a Course at the 3rd International PhD School in Formal Languages and Applications
Mathematische Schriften Kassel 6/04, Universität Kassel, Juni 2004.
Jurdzinski, T., Otto, F., Mráz, F. and Plátek, M.:
On the complexity of 2-monotone restarting automata
Mathematische Schriften Kassel 4/04, Universität Kassel, Juni 2004.
Otto, F., and Jurdzinski, T.:
On left-monotone restarting automata.
Mathematische Schriften Kassel 17/03, Universität Kassel, November 2003.
Plátek, M., Otto, F., Mráz, F. and Jurdzinski, T.:
Restarting automata and variants of j-monotonicity
Mathematische Schriften Kassel 9/03, Universität Kassel, Oktober 2003.
Jurdzinski, T. and Lorys, K. and Niemann, G. and Otto, F.:
Some results on RRW- and RRWW-automata and their relationship to the class of growing context-sensitive languages.
Mathematische Schriften Kassel 14/01, Universität-GH Kassel, Dezember 2001.
Niemann, G. and Otto, F.:
On the power of RRWW-automata.
Mathematische Schriften Kassel 8/01, Universität-GH Kassel, Mai 2001.
Veröffentlicht in: Words, Semigroups, and Transductions. Essays in Honour of Gabriel Thierrin, On the Occasion of His 80th Birthday.
Otto, F.:
Restarting automata and their relations to the Chomsky hierarchy.
Mathematische Schriften Kassel 5/03, Universität-GH Kassel, März 2003.
Mráz, F. and Otto, F.:
Hierarchies of Weakly Monotone Restarting Automata.
Mathematische Schriften Kassel 8/03, Universität Kassel, April 2003.

Veröffentlichungen:

Jurdzinski, T. and Otto, F.:
Sequential monotonicity for restarting automata.
RAIRO Informatique Theorique et Applications 2007, 41:157--175
Jurdzinski, T. and Otto, F.:
Shrinking restarting automata.
Int. Journal of Foundations of Computer Science 2007, 18:361--385
Jurdzinski, T., Mráz, F., Otto, F. and Plátek, M.:
Degrees of non-monotonicity for restarting automata.
Theoretical Computer Science 2006, 369:1--34
Mráz, F., Otto, F., Plátek, M. and Jurdzinski, T.:
Marcus t-contextual grammars and cut hierarchies and monotonicity for restarting automata.
Theoretical Computer Science 2006, 366:272--296
Jurdzinski, T. and Otto, F.:
Restarting automata with restricted utilization of auxiliary symbols.
Theoretical Computer Science 2006, 363:162--181
Mráz, F., Otto, F. and Plátek, M.:
Learning analysis by reduction from positive data
In Sakakibara, Y., Kobayashi, S., Sato, K., Nishino, T. and Tomita, E., editors, Proceedings ICGI 2006, pages 125--136, Lecture Notes in Articial Intelligence 4201, Springer-Verlag, Berlin.
Messerschmidt, H., Mráz, F., Otto, F. and Plátek, M.:
Correctness preservation and complexity of simple RL-automata
In Ibarra, O. and Yen, H.-C., editors, Proceedings CIAA 2006, pages 162--172, Lecture Notes in Computer Science 4094, Springer-Verlag, Berlin.
Otto, F.:
Restarting automata.
In Esik, Z., Martin-Vide, C. and Mitrana, V., editors, Recent Advances in Formal Languages and Applications, pages 269--303, Studies in Computational Intelligence 25, Springer-Verlag, Berlin.
Mráz, F., Otto, F. and Plátek, M.:
On the gap-complexity of simple RL-automata
In Ibarra, O. and Dang, Z., editors, Developments in Language Theory Proceedings DLT 2006, pages 83--94, Lecture Notes in Computer Science 4036, Springer-Verlag, Berlin.
Messerschmidt, H. and Otto. F.:
On nonforgetting restarting automata that are deterministic and/or monotone
In Grigoriev, D., Harrison, J. and Hirsch, E.A., editors, Conference on , Proceedings CRS 2006, pages 247--258, Lecture Notes in Computer Science 3967, Springer-Verlag, Berlin.
Jurdzinski, T. and Otto, F.:
Restricting the use of auxiliary symbols for restarting automata.
In Farré, J., Litovsky, I. and Schmitz, S., editors, Tenth International Conference on Implementation and Application of Automata, Proceedings CIAA 2005, pages 176--187, Lecture Notes in Computer Science 3845, Springer-Verlag, Berlin.
Jurdzinski, T., Otto. F., Mráz, F. and Plátek, M.:
Cut hierarchies for restarting automata and Marcus t-contextual grammars.
In Bozapalidis, S., Kalampakas, A. and Rahonis, G., editors, Conference on Algebraic Informatics, Proceedings CAI 2005, pages 157--171, Aristotle University, Thessaloniki.
Jurdzinski, T. and Otto, F.:
Shrinking restarting automata.
In Jedrzejowicz, J. and Szepietowski, A., editors, Mathematical Foundations of Computer Science, Proceedings MFCS 2005, pages 532--543, Lecture Notes in Computer Science 3618, Springer-Verlag, Berlin.
Jurdzinski, T. and Otto, F.:
Sequential monotonicity for restarting automata.
In Vojtás, P., editor, ITAT 2004, Information Technologies - Applications and Theory, Proceedings, pages 39--48, Department of Computer Science, Faculty of Science, Pavol Jozef Safárik University, Kosice.
Jurdzinski, T., Mráz, F., Otto, F. and Plátek, M.:
Monotone deterministic RL-automata don't need auxiliary symbols.
In De Felice, C. and Restivo, A., editors, Developments in Language Theory, Proceedings DLT 2005, pages 284--295, Lecture Notes in Computer Science 3572, Springer-Verlag, Berlin.
Otto, F., Mráz, F. and Plátek, M.:
Degrees of monotonicity and Marcus t-contextual grammars.
In Ésik, Z. and Fülöp, Z., editors, Automata and Formal Languages, Proceedings AFL 2005, pages 249--262, Institute of Informatics, University of Szeged
Mráz, F. and Otto, F.:
Hierarchies of weakly monotone restarting automata.
RAIRO Informatique Théorique et Applications 2005, 39:325--342
Jurdzinski, T., Otto, F., Mráz, F. and Plátek, M.:
Deterministic two-way restarting automata and Marcus contextual grammars.
Fundamenta Informaticae 2005, 64:217--228
Jurdzinski, T., Lorys, K., Niemann, G. and Otto, F.:
Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages
Journal of Automata, Languages and Combinatorics 2004, 9:407--437
Jurdzinski, T., Otto, F., Mráz, F. and Plátek, M.:
On left-monotone deterministic restarting automata.
In Calude, C.S., Calude, E. and Dinneen, M.J., editors, Developments in Language Theory, Proceedings DLT 2004, pages 249-260, Lecture Notes in Computer Science 3340, Springer-Verlag, Berlin, 2004.
Jurdzinski, T., Otto, F., Mráz, F. and Plátek, M.:
On the complexity of 2-monotone restarting automata.
In Calude, C.S., Calude, E. and Dinneen, M.J., editors, Developments in Language Theory, Proceedings DLT 2004, pages 237-248, Lecture Notes in Computer Science 3340, Springer-Verlag, Berlin, 2004.
Mráz, F., Otto, F. and Plátek, M.:
Restarting automata and combinations of constraints
In Voitás, P., editor, ITAT 2003, Information Technologies - Applications and Theory, Proc., pages 83-91, Department of Cumputer Science, Faculty of Science, Pavol Jozef Safárik University, Kosice, 2004.
Niemann, G. and Otto, F.:
Further results on restarting automata.
In Ito, M. and Imaoka, T., editors, Words, Languages and Combinatorics III, Proc., pages 352-369, World Scientific, Singapore, 2003.
Plátek, M., Otto, F. and Mráz, F.:
Restarting automata and variants of j-monotonicity.
In Descriptional Complexity of Formal Systems, Proceedings DCFS 2003 pages 303-312, MTA SZTAKI, Budapest, 2003.
Otto, F.:
Restarting automata and their relations to the Chomsky hierarchy.
In Esik, Z. and Fülöp, Z., editors, Developments in Language Theory, Proceedings DLT 2003 , pages 55-74, Lecture Notes in Computer Science 2710, Springer-Verlag, Berlin, 2003.
Niemann, G. and Otto, F.:
On the power of RRWW-automata,
In: Ito, M. and Paun, G. and Yu, S. (editors), Words, Semigroups, and Transductions. Essays in Honour of Gabriel Thierrin, On the Occasion of His 80th Birthday. pages 341-355 World Scientific, Singapore, 2001.