Extended Linear Macro Grammars, Iteration Grammars, and Register Programs

Peter R.J. Asveld, Joost Engelfriet

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    19 Downloads (Pure)

    Abstract

    Extended macro grammars (of the linear basic type only) are introduced as a generalization of those in [5], and it is shown that they have the same language generating power as (parallel) iteration grammars. In particular the OI and OI versions of extended macro grammars correspond to the deterministic and the (usual) nondeterministic iteration grammars respectively. Hence iterated substitution can be formulated using extended macro grammars. A nondeterministic register program without tests may be viewed as a macro grammar. IO-extension of this macro grammar corresponds to the use of nonrecursive function procedures in the register program. OI-extended macro grammars correspond to register programs which compute on sets. Hence these features of register programs can be investigated by means of (extended) parallel rewriting systems.
    Original languageEnglish
    Pages (from-to)259-285
    Number of pages27
    JournalActa informatica
    Volume11
    Issue number3
    DOIs
    Publication statusPublished - 1979

      Fingerprint

    Keywords

    • HMI-SLT: Speech and Language Technology
    • MSC-68F05
    • Information systems
    • Operating systems
    • Data structure
    • Communication networks
    • Information theory

    Cite this