### Abstract

For a full semi-AFL K, B(K) is defined as the family of languages generated by all K-extended basic macro grammars, while H(K) B(K) is the smallest full hyper-AFL containing K; a full basic-AFL is a full AFL K such that B(K) = K (hence every full basic-AFL is a full hyper-AFL). For any full semi-AFL K, K is a full basic-AFL if and only if B(K) is substitution closed if and only if H(K) is a full basic-AFL. If K is not a full basic-AFL, then the smallest full basic-AFL containing K is the union of an infinite hierarchy of full hyper-AFLs. If K is a full principal basic-AFL (such as INDEX, the family of indexed languages), then the largest full AFL properly contained in K is a full basic-AFL. There is a full basic-AFL lying properly in between the smallest full basic-AFL and the largest full basic-AFL in INDEX.

Original language | English |
---|---|

Pages (from-to) | 86-115 |

Journal | Journal of computer and system sciences |

Volume | 30 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1985 |

## Fingerprint Dive into the research topics of 'Hierarchies of hyper-AFLs'. Together they form a unique fingerprint.

## Cite this

Engelfriet, J. (1985). Hierarchies of hyper-AFLs.

*Journal of computer and system sciences*,*30*(1), 86-115. https://doi.org/10.1016/0022-0000(85)90006-6