Project without external funding

Church-Rosser Sprachen und wachsend kontext-sensitive Sprachen

Project Details
Project duration: 01/199412/2005

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.

Principal Investigator



Last updated on 2017-11-07 at 14:49