Hierarchies of hyper-AFLs

Joost Engelfriet

    Research output: Contribution to journalArticleAcademic

    5 Citations (Scopus)
    86 Downloads (Pure)


    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 languageEnglish
    Pages (from-to)86-115
    JournalJournal of computer and system sciences
    Issue number1
    Publication statusPublished - 1985

    Cite this