The class of growing context-sensitive languages (GCSL) is a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. GCSL and its deterministic counterpart called Church-Rosser Languages CRL complement the Chomsky hierarchy in a natural way. In this paper, the extension of GCSL} obtained by closures of this class under boolean operations are investigated. We show that there exists an infinite intersection hierarchy, answering an open problem from [G.Buntrock, K.Lorys, On growing context-sensitive languages, ICALP 1992, LNCS 623, 77--88. Further, we compare expressive power of boolean closures of GCSL, CRL, CFL and LOGCFL.
|
|