without external funding
Church-Rosser Sprachen und wachsend kontext-sensitive Sprachen
Project Details
Project duration: 01/1994–12/2005
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 | |
2005 | |
2003 | |
2003 | |
2002 | |
2000 | |
2000 | |
1998 |