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:

- The hierarchy of exponential time-bounded languages in CSL collapses.
- There exists a class defined by an 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 exists a class defined by a steady position valuation that is closed under inverse homomorphisms.

- Preformatted versions of the article
- DVI (211,540 bytes)
**PostScript**(495,300 bytes)- PDF (509,448 bytes)
- Audio by
**AsTeR**(to appear)

- Source materials for custom formatting
**LaTeX**(`cj96-04.tex`, 149,245 bytes)**BIBTeX**(`cj96-04.bib`, 13,126 bytes)- Parameter settings for custom
formatting (
`cjropts.tex`, 273 bytes) - Self citation in
**BIBTeX**(273 bytes)

- Online discussion
- Instructions for Readers

DOI: 10.4086/cjtcs.1996.004

Article 3 Article 5

Volume 1996 Published articles

Article 3 Article 5

Volume 1996 Published articles

Last modified: 24 March 1997