Extended linear macro grammars, iteration grammars, and register programs

descriptionPublicationkeyboard_double_arrow_right Article 01 Jan 1979 Netherlands English Publisher:Springer Science and Business Media LLCJournal:Acta Informatica, volume 11, pages 259-285 (issn: 0001-5903, eissn: 1432-0525,

Copyright policy )

Authors: Asveld, Peter R.J.; Engelfriet, Joost;

doi: 10.1007/bf00289071

Extended linear macro grammars, iteration grammars, and register programs

- Summary
- Subjects
- Metrics

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.

Country

Netherlands

Related Organizations

University of Twente
Netherlands
University of Technology
Russian Federation

Keywords

EXTENDED LINEAR MAC, Information theory, General topics in the theory of software, Formal languages and automata, Communication networks, Data structure, HMI-SLT: Speech and Language Technology, Information systems, ITERATION GRAMMARS, MSC-68F05, PARALLEL REWRITING SYSTEMS, Operating systems

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	7
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%