Extended macro grammars and stack controlled machines (Q1064075): Difference between revisions

The main purpose of the paper consists in introducing a new type of operation on languages, called basic substitution. This operation is used within another paper of the first author [J. Comput. Syst. Sci. 30, 86- 115 (1985; Zbl 0565.68072)] as a technical tool in order to prove the existence of an infinite hierarchy of full hyper-AFLs inside the class of indexed languages. The authors assert that it ''seems impossible to prove, without the concepts introduced in this paper, that the nested stack automata form an infinite hierarchy with respect to depth of nesting of stacks''. The basic substitution is defined in terms of extended basic macro grammars, which are also introduced in this paper. The main closure properties of the basic substitution are investigated and a machine characterization for the full AFLs closed under the new operation is also provided.