Complexity Aspects of Iterated Rewriting: A Survey

Peter R.J. Asveld

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    13 Downloads (Pure)


    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.
    Original languageEnglish
    Title of host publicationEssays on concepts, formalisms, and tools
    Subtitle of host publicationA collection of papers dedicated to Leo A.M. Verbeek
    EditorsP.R.J. Asveld, A. Nijholt
    Place of PublicationAmsterdam
    PublisherCentrum voor Wiskunde en Informatica
    Number of pages17
    ISBN (Print)90-6196-326-5
    Publication statusPublished - 1987

    Publication series

    NameCWI Tract
    PublisherCentre for Mathematics and Computer Science


    • MSC-68Q15
    • MSC-68Q50
    • HMI-SLT: Speech and Language Technology


    Dive into the research topics of 'Complexity Aspects of Iterated Rewriting: A Survey'. Together they form a unique fingerprint.

    Cite this