Controlled Iteration Grammars and Full Hyper-AFL's (revised and extended version).

P.R.J. Asveld

    Research output: Book/ReportReportOther research output


    We investigate derivation-controlled $K$-iteration grammars, called $(\Gamma,K)$-iteration grammars, where $\Gamma$ stands for a family of control languages. The control consists of a language in the family $\Gamma$ over the indices ("names") of the substitutions, prescribing the specific order in which one has to apply the substitutions. We show that under certain restrictions on the families $\Gamma$ and $K$ (which we tried to keep as simple as possible) the following holds. (1) Regular control does not increase the generating power of $K$-iteration grammars. (2) For each $(\Gamma,K)$-iteration grammar there exists an equivalent propagating $(\Gamma,K)$-iteration grammer. (3) The family of $(\Gamma,K)$-iteration languages is a full hyper-AFL. (4) For each arbitrary $(\Gamma,K)$-iteration grammar there exists an equivalent $(\Gamma,K)$-iteration grammar with exactly two substitutions. Finally, we discusssome consequences and additional properties of (uncontrolled) $K$-iteration grammars and controlled (deterministic) ETOL systems and their languages.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Number of pages41
    Publication statusPublished - 1976


    • EWI-3675
    • HMI-SLT: Speech and Language Technology

    Cite this