Projekt A14 - Church-Rosser Sprachen und wachsend kontext-sensitive Sprachen

(until 12/05)

The growing context-sensitive languages (GCSL) are defined as those languages that can be generated by context-sensitive grammars that contain length-increasing production rules only. We have characterized this class of languages by a nondeterministic machine model, the so-called shrinking two-pushdown automaton (sTPDA). The deterministic version of this automaton (sDTPDA) has also been considered. As it turns out it characterizes the class of generalized Church-Rosser languages (GCRL), which is obtained from the Church-Rosser languages of McNaughton, Narendran and Otto (1988) through a straightforward generalization. Finally, it has been shown that each growing context-sensitive language is accepted in polynomial time by some one-way auxiliary pushdown automaton that has a logarithmic space bound. As a consequence we obtain the result that the class of (generalized) Church-Rosser languages and the class of context-free languages are incomparable under set inclusion, thus verifying a conjecture of McNaughton et al.

Mitarbeiter:

Gundula Niemann
(jetzt: SAP, Deutschland)

Gerhard Buntrock
(Fachbereich Informatik, Medizinische Universität Lübeck)

Markus Holzer
(Institut für Informatik, TU München, Garching)

Interne Berichte:

Niemann, G. and Otto, F.:
Restarting automata and prefix-rewriting systems.
Mathematische Schriften Kassel 18/99, Universität-GH Kassel, Dezember 1999.
Niemann, G. and Otto, F.:
Restarting automata, Church-Rosser languages, and confluent internal contextual languages.
Mathematische Schriften Kassel 4/99, Universität-GH Kassel, März 1999.
Niemann, G. and Otto, F. :
The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages.
Mathematische Schriften Kassel 8/97, Universität-GH Kassel, August 1997.
results presented at FoSSaCS'98.
Buntrock, G. and Otto, F. :
Growing context-sensitive languages and Church-Rosser languages.
Schriftenreihe der Institute für Informatik/Mathematik A-95-22, Medizinische Universität zu Lübeck, 1995.
published in
Information and Computation in revised form.

Veröffentlichungen:

Holzer, M. and Otto, F.:
Shrinking multi-pushdown automata.
In Liskiewicz, M. and Reischuk, R., editors, Fundamentals of Computation Theory, Proceedings FCT 2005, pages 305--316, Lecture Notes in Computer Science 3623, Springer-Verlag, Berlin.
Niemann, G., Otto, F.:
The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages.
Information and Computation 2005, 197:1--21
Niemann, G. and Otto, F.:
The Church-Rosser languages and their relationship to other language classes.
In Martin-Vide, C. and Mitrana, V., editors, Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back, Taylor and Francis, London, 2003.
Niemann, G. and Otto, F.:
Restarting automata, Church-Rosser languages, and representations of r.e. languages.
In Rozenberg, G. and Thomas, W., editors, Developments in Languages Theory - Foundations, Applications, and Perspectives, Proceedings DLT 1999, pages 103-114, World Scientific, Singapore, 2000.
Niemann, G. and Otto, F. :
Confluent internal contextual languages
In Martin-Vide, C. and Paun, G., editors, Recent Topics in Mathematical and Computational Linguistics, pages 234-244, The Publishing House of the Romanian Academy, Bucharest, 2000.
Niemann, G. and Otto, F.:
Restarting automata, Church-Rosser languages, and representations of r.e.\ languages.
In Thomas, W., editor, DLT 99, Preproceedings, pages 49-62, Aachener Informatik-Berichte 99-5, RWTH Aachen, 1999.
Niemann, G. and Otto, F.:
The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages.
In Nivat, M., editor, Foundations of Software Science and Computation Structures, Proceedings FoSSaCS'98, Lecture Notes in Computer Science 1378, pages 243-257. Springer-Verlag, Berlin.
Buntrock, G. and Otto,F. :
Growing Context-Sensitive Languages and Church-Rosser languages.
Information and Computation, 141, pages 1-36, 1998.
Buntrock, G. and Otto, F. :
Growing context-sensitive languages and Church-Rosser languages.
In Mayr, E. and Puech, C., editors, Proc. of STACS 95, Lecture Notes in Computer Science 900, pages 313-324. Springer-Verlag 1995, Berlin.