Published by MIT Press. Copyright 1996 Massachusetts Institute of Technology.
Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.
This paper introduces weakly growing context-sensitive grammars. Such grammars generalize the class of growing context-sensitive grammars (studied by several authors), in that these grammars have rules that "grow" according to a position valuation.
If a position valuation coincides with the initial part of an exponential function, it is called a steady position valuation. All others are called unsteady. The complexity of the language generated by a grammar depends crucially on whether the position valuation is steady or not. More precisely, for every unsteady position valuation, the class of languages generated by WGCSGs with this valuation coincides with the class CSL of context-sensitive languages. On the other hand, for every steady position valuation, the class of languages generated corresponds to a level of the hierarchy of exponential time-bounded languages in CSL. We show that the following three conditions are equivalent: