Extended macro grammars and stack controlled machines
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.
- A relationship between ETOL and EDTOL languages
- An Approach to a Unified Theory of Automata
- Bounded nesting in macro grammars
- Chains of full AFL's
- Checking automata and one-way stack languages
- Controlled iteration grammars and full hyper-AFL's
- Extended linear macro grammars, iteration grammars, and register programs
- Full AFLs and nested iterated substitution
- Hierarchies of hyper-AFLs
- scientific article; zbMATH DE number 3646311 (Why is no real title available?)
- scientific article; zbMATH DE number 3648125 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3683038 (Why is no real title available?)
- scientific article; zbMATH DE number 3466545 (Why is no real title available?)
- scientific article; zbMATH DE number 3483582 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 3509706 (Why is no real title available?)
- scientific article; zbMATH DE number 3540387 (Why is no real title available?)
- scientific article; zbMATH DE number 3566198 (Why is no real title available?)
- scientific article; zbMATH DE number 3566209 (Why is no real title available?)
- scientific article; zbMATH DE number 3569855 (Why is no real title available?)
- Indexed Grammars—An Extension of Context-Free Grammars
- IO and OI. II
- L systems
- Nested Stack Automata
- On acceptors of iteration languages
- One-way stack automata
- Programming Language for Automata
- Some definitional suggestions for automata theory
- Stack Machines and Classes of Nonnested Macro Languages
- Hierarchies of hyper-AFLs
- Pushdown machines for the macro tree transducer
- Tree transducers, L systems, and two-way machines
- Iterated stack automata and complexity classes
- An implementation of syntax directed functional programming on nested- stack machines
- The power of two-way deterministic checking stack automata
- Iterated pushdown automata and sequences of rational numbers
- Pushdown tree automata
- Basic tree transducers
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)