Complexity Aspects of Iterated Rewriting: A Survey

Peter R.J. Asveld

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

    6 Downloads (Pure)

    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.
    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
    Pages89-105
    Number of pages17
    ISBN (Print)90-6196-326-5
    Publication statusPublished - 1987

    Publication series

    NameCWI Tract
    PublisherCentre for Mathematics and Computer Science
    Volume42

    Keywords

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

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

  • Cite this

    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.