The Boolean Closure of Growing Context-Sensitive Languages

Tomasz Jurdzinski


Abstract

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.


Server START Conference Manager
Update Time 20 Feb 2006 at 20:05:03
Maintainer zdang@eecs.wsu.edu.
Start Conference Manager
Conference Systems