TY - BOOK

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

AU - Asveld, P.R.J.

AU - Engelfriet, Joost

N1 - The work of the first author has been supported by Netherlands Organization for the Advancement of Pure Research (ZWO).

PY - 1978

Y1 - 1978

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 IO 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 correspond 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 viewed by means of (extended) parallel rewriting systems.
---------
[5] P.J. Downey, Formal Languages and Recursion Schemes, PhD Thesis 1974, Harvard Univ. Cambridge, MA.

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 IO 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 correspond 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 viewed by means of (extended) parallel rewriting systems.
---------
[5] P.J. Downey, Formal Languages and Recursion Schemes, PhD Thesis 1974, Harvard Univ. Cambridge, MA.

KW - EWI-3716

KW - HMI-SLT: Speech and Language Technology

M3 - Report

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

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -