scientific article; zbMATH DE number 3997179
[For the entire collection see Zbl 0596.00021.] The OI-hierarchy is an infinite, strictly increasing chain \(L_ 0\), \(L_ 1\), \(L_ 2,..\). of classes of string languages. Every class \(L_ n\) is generated by so-called n-level grammars; in an n-level grammar G, to every nonterminal a functional type of level at most n is associated. A sentential form s is rewritten by a rule r of G by replacing an instance of the left-hand side of r by the corresponding instance of its right-hand side. These gramars were introduced by \textit{W. Damm} [Theor. Comput. Sci. 20, 95-207 (1982; Zbl 0478.68012)] to model recursive function procedures with parameters of functional type. The OI-hierarchy starts with the classes of regular languages \((n=0)\), context-free languages \((n=1)\), and OI macro languages \((n=2).\) The control considered in this paper is motivated by the usual L- controlled ETOL-systems [\textit{S. Ginsburg} and \textit{G. Rozenberg}, Inf. Control 27, 109-125 (1975; Zbl 0294.68027)] (where L is a class of string languages): they can be viewed as context-free grammars (equivalent to 1- level grammars) of which the rewriting process is controlled by strings of a given language taken from L. Roughly speaking, at every stage of derivation the control string prescribes the table of rules which can be applied at that moment. Generalizing this kind of control on context-free grammars to n-level grammars, yields the so-called L-controlled n-level grammars. The main theorem of this paper states the following: the language generated by an \(L_ m\)-controlled n-level grammar can be generated by an \((n+m+1)\)-level grammar. This theorem follows from a generalization of the characterization of n-level grammars by iterated pushdown automata [\textit{W. Damm} and \textit{A. Goerdt}, Inf. Control 71, 1-32 (1986), and Lect. Notes Comput. Sci. 140, 141-153 (1982; Zbl 0487.68070)] proved by \textit{J. Engelfriet} and the author [High level tree transducers and iterated pushdown machines, Rep. No.85-12, University of Leiden (1985); see also: Lect. Notes Comput. Sci. 194, 171-178 (1985; Zbl 0602.68076)] and the fact that the simulation of the control mechanism requires an additional pushdown.
- The OI-hierarchy is closed under control
- The IO and OI hierarchies revisited
- scientific article; zbMATH DE number 3917739 (Why is no real title available?)
- scientific article; zbMATH DE number 3940754 (Why is no real title available?)
- An automata-theoretical characterization of the OI-hierarchy
- The IO and OI hierarchies revisited
- Basic tree transducers
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723316)