Controlled Iteration Grammars and Full Hyper-AFL's

P.R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    27 Citations (Scopus)
    59 Downloads (Pure)

    Abstract

    We investigate derivation-controlled $K$-iteration grammars, called $(\Gamma,K)$-iteration grammars, where $\Gamma$ can be any family of control languages. We prove that already under very weak restrictions on $\Gamma$ and $K$ the following hold: (i) Regular control does not increase the generating power of $K$-iteration grammars, (ii) for each $(\Gamma,K)$-iteration grammar there exists an equivalent propagating $(\Gamma,K)$-iteration grammar, (iii) the family of $(\Gamma,K)$-iteration languages is a full hyper-AFL, (iv) for each $(\Gamma,K)$-iteration grammar there exists an equivalent $(\Gamma,K)$-iteration grammar with exactly two substitutions. We also discuss some additional properties and applications of (uncontrolled) $K$-iteration grammars and controlled (deterministic) ET0L systems and their languages in a wider context.
    Original languageEnglish
    Pages (from-to)248-269
    Number of pages22
    JournalInformation and Control
    Volume34
    Issue number3
    DOIs
    Publication statusPublished - 1977

    Keywords

    • HMI-SLT: Speech and Language Technology
    • MSC-68A30

    Fingerprint Dive into the research topics of 'Controlled Iteration Grammars and Full Hyper-AFL's'. Together they form a unique fingerprint.

  • Cite this