Extended Linear Macro Grammars, Iteration Grammars, and Register Programs

Peter R.J. Asveld; Joost Engelfriet

doi:10.1007/BF00289071

Extended Linear Macro Grammars, Iteration Grammars, and Register Programs

Peter R.J. Asveld, Joost Engelfriet

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

47 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 language	English
Pages (from-to)	259-285
Number of pages	27
Journal	Acta informatica
Volume	11
Issue number	3
DOIs	https://doi.org/10.1007/BF00289071
Publication status	Published - 1979

Keywords

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

Access to Document

10.1007/BF00289071

Asveld1979extendedFinal published version, 1.38 MB

Cite this

@article{58dd1dbf1c074acbb651aec35a447cbf,

title = "Extended Linear Macro Grammars, Iteration Grammars, and Register Programs",

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.",

keywords = "HMI-SLT: Speech and Language Technology, MSC-68F05, Information systems, Operating systems, Data structure, Communication networks, Information theory",

author = "Asveld, {Peter R.J.} and Joost Engelfriet",

year = "1979",

doi = "10.1007/BF00289071",

language = "English",

volume = "11",

pages = "259--285",

journal = "Acta informatica",

issn = "0001-5903",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - Extended Linear Macro Grammars, Iteration Grammars, and Register Programs

AU - Asveld, Peter R.J.

AU - Engelfriet, Joost

PY - 1979

Y1 - 1979

N2 - 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.

AB - 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.

KW - HMI-SLT: Speech and Language Technology

KW - MSC-68F05

KW - Information systems

KW - Operating systems

KW - Data structure

KW - Communication networks

KW - Information theory

U2 - 10.1007/BF00289071

DO - 10.1007/BF00289071

M3 - Article

SN - 0001-5903

VL - 11

SP - 259

EP - 285

JO - Acta informatica

JF - Acta informatica

IS - 3

ER -

Extended Linear Macro Grammars, Iteration Grammars, and Register Programs

Abstract

Keywords

Access to Document

Fingerprint

Cite this