We present an overview of results on the complexity of the membership problem for families of languages generated by several types of generalized grammars. In particular, we consider generalized grammars based on context-independent rewriting, i.e., grammars consisting of a finite number of (non)deterministic substitutions, and on iterated context-dependent rewriting , i.e., grammars composed of a finite number of transductions. We give some conditions on the classes of these substitutions and transductions that guarantee the solvability of this membership problem within certain time and space bounds. As consequences we obtain additional closure properties of some time- and space-bounded complexity classes.
|Title of host publication||Essays on concepts, formalisms, and tools|
|Subtitle of host publication||A collection of papers dedicated to Leo A.M. Verbeek|
|Editors||P.R.J. Asveld, A. Nijholt|
|Place of Publication||Amsterdam|
|Publisher||Centrum voor Wiskunde en Informatica|
|Number of pages||17|
|Publication status||Published - 1987|
|Publisher||Centre for Mathematics and Computer Science|
- HMI-SLT: Speech and Language Technology
Asveld, P. R. J. (1987). Complexity Aspects of Iterated Rewriting: A Survey. In P. R. J. Asveld, & A. Nijholt (Eds.), Essays on concepts, formalisms, and tools: A collection of papers dedicated to Leo A.M. Verbeek (pp. 89-105). (CWI Tract; Vol. 42). Amsterdam: Centrum voor Wiskunde en Informatica.