Hierarchies of hyper-AFLs (Q1058860)

The attention is focused on the ''AFL-structure'' of the family of indexed languages. 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)\(\subseteq B(K)\) is the smallest full hyper-AFL containing K. \(B^*(K)\) denotes \(\cup \{B^ n(K)| n\geq 1\}\). The main result of the paper shows that B is hierarchical: If \(K\varsubsetneq B(K)\), then, for every \(n\geq 1\), \(B^ n(K)\varsubsetneq H(B^ n(K))\varsubsetneq B^{n+1}(K)\), \(B^ n(K)\) is not substitution closed, and \(B^*(K)\) is the union of an infinite hierarchy of full hyper-AFLs containing K. A full basic-AFL is a full AFL K such that \(B(K)=K\). The paper establishes the existence of infinitely many full-AFLs and of three basic-AFLs properly contained in the family of indexed languages.