Extended macro grammars and stack controlled machines

From MaRDI portal





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.



Cites work









This page was built for publication: Extended macro grammars and stack controlled machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1064075)