Growing context-sensitive languages and Church-Rosser languages

The growing context-sensitive languages are characterized by a nondeterministic machine model, the so-called shrinking two-pushdown automaton. Then the deterministic Version of this automaton is considered, and it is shown that it characterizes the class of generalized Church-Rosser languages. 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. (1988, J. Assoc. Comput. Math. 35, 324-344). Finally, we prove that each growing context-sensitive language is accepted in polynomial time by some one-way auxiliary pushdown automaton with a logarithmic space bound, which improves upon a result of Dahlhaus and Warmuth (1986, J. Comput. System Sci. 33, 456-472). (C) 1998 Academic Press.