WEAKLY GROWING CONTEXT-SENSITIVE GRAMMARS

This paper introduces weakly growing context-sensitive grammars. Such grammars generalize the class of growing context-sensitive grammars (s tudied by several authors), in that these grammars have rules that ''g row'' according to a position valuation. If a position valuation coinc ides with the initial part of an exponential function, it is called a steady position valuation. All others are called unsteady. The complex ity of the language generated by a grammar depends crucially on whethe r the position valuation is steady or not. More precisely, for every u nsteady 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, th e class of languages generated corresponds to a level of the hierarchy of exponential time-bounded languages in CSL. We show that the follow ing three conditions are equivalent: The hierarchy of exponential time -bounded languages in CSL collapses. There exists a class defined by a n unsteady position valuation such that there is also a normal form of order 2 (e.g., Cremers or Kuroda normal form) for that class. There e xists a class defined by a steady position valuation that is closed un der inverse homomorphisms. Some of these results were presented at LAT IN'95 at Valparaiso, Chile.