Abstract grammars based on transductions

Peter R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    82 Downloads (Pure)


    We study an abstract grammatical model in which the effect (or application) of a production - determined by a so-called transduction - plays the main part rather than the notion of production itself. Under appropriately chosen assumptions on the underlying family T of transductions, we establish elementary, decidability, and complexity properties of the corresponding family L(T) of languages generated by T-grammars. These results are special instances of slightly more general properties of so-called Γ-controlled T-grammars, since regular control does not increase the generating power of T-grammars. In a Γ-controlled T-grammar we strict the iteration of T-transductions to those sequences of transductions that belong to a given control language, taken from a family Γ of control languages.
    Original languageEnglish
    Pages (from-to)269-288
    Number of pages20
    JournalTheoretical computer science
    Issue number2
    Publication statusPublished - 1991


    • HMI-SLT: Speech and Language Technology


    Dive into the research topics of 'Abstract grammars based on transductions'. Together they form a unique fingerprint.

    Cite this