Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Controlled Iteration Grammars and Full Hyper-AFL's

Share/Save/Bookmark

Asveld, Peter R.J. (1977) Controlled Iteration Grammars and Full Hyper-AFL's. Information and Control, 34 (3). pp. 248-269. ISSN 0019-9958

[img]
Preview
PDF
998Kb
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.
Item Type:Article
Copyright:© 1977 Elsevier Science
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/65592
Official URL:http://dx.doi.org/10.1016/S0019-9958(77)90308-4
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page