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.

Abstract

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

Last modified: 24 March 1997