@inbook{d2368618351a4f86ad68754d831d047e,
title = "Complexity Aspects of Iterated Rewriting: A Survey",
abstract = "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.",
keywords = "MSC-68Q15, MSC-68Q50, HMI-SLT: Speech and Language Technology",
author = "Asveld, \{Peter R.J.\}",
year = "1987",
language = "English",
isbn = "90-6196-326-5",
series = "CWI Tract",
publisher = "Centrum voor Wiskunde en Informatica",
pages = "89--105",
editor = "P.R.J. Asveld and A. Nijholt",
booktitle = "Essays on concepts, formalisms, and tools",
address = "Netherlands",
}