Church-Rosser Sprachen und wachsend kontext-sensitive Sprachen - Research Information System | University of Kassel

without external funding

Church-Rosser Sprachen und wachsend kontext-sensitive Sprachen

Project Details

Project duration: 01/1994–12/2005

Website: http://www.theory.informatik.uni-kassel.de/

Abstract

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. Lately the correspondence between
the class of Church-Rosser languages and the various classes of
languages defined by certain types of restarting automata has
become one of the main points of interest for this project.

Publications

2005	Holzer, M., Otto, F., 2005. Shrinking multi-pushdown automata. Fundamentals of Computation Theory, Proceedings FCT 2005, 305–316.
2005	Niemann, G., Otto, F., 2005. The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Information and Computation 197, 1–21. https://doi.org/10.1016/j.ic.2004.09.003
2003	Beaudry, M., Holzer, M., Niemann, G., Otto, F., 2003. McNaughton families of languages. Theoretical Computer Science 290, 1581–1628. https://doi.org/10.1016/S0304-3975(02)00070-1
2003	Niemann, G., Otto, F., 2003. The Church-Rosser languages and their relationship to other language classes, in: Martin-Vide, C. and M. (Hrsg.), Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back. Taylor and Francis, London.
2002	Beaudry, M., Holzer, M., Niemann, G., Otto, F., 2002. On the relationship between the McNaughton families of languages and the Chomsky hierarchy, in: Kuich, W. (Hrsg.), Developments in Language Theory, Proceedings DLT 2001. Springer, Berlin, S. 340–348.
2000	Niemann, G., Otto, F., 2000. Confluent internal contextual languages, in: C. Martin-Vide, G.P. (Hrsg.), Recent Topics in Mathematical and Computational Linguistics. The Publishing House of the Romanian Academy, Bucharest, S. 234–244.
2000	Niemann, G., Otto, F., 2000. Restarting automata, Church-Rosser langauges and representations of r.e. languages, in: G. Rozenberg, W.T. (Hrsg.), Developments in Language Theory - Foundations, Applications and Perspectives, Proceedings DLT’99. World Scientific, Singapore, S. 103–114.
1998	Niemann, G., Otto, F., 1998. The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages, in: Nivat, M. (Hrsg.), Foundations of Software Science. Springer, Berlin, S. 243–257.