No label defined (Q4723316)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3997179
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3997179 |
Statements
1986
0 references
OI-hierarchy
0 references
string languages
0 references
regular languages
0 references
context-free languages
0 references
OI macro languages
0 references
control string
0 references
L-controlled n-level grammars
0 references
iterated pushdown automata
0 references
0.8968114852905273
0 references
0.8309249877929688
0 references
0.7577694058418274
0 references
[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.
0 references