The ETOL Hierarchy is in the oi Hierarchy

There exist several interesting hierarchies of classes of formal languages that start with rather small well-known classes (such as the regular or context-free languages) and contain larger and larger classes, obtained by the iteration of some simple concept. Well-known examples of such hierarchies are the OI hierarchy and the IO hierarchy CWan,Mai,Masl,EngSch,DamJ, the ETOL (control) hierarchy [AsvvLe,Eng2], the 2-way GSM hierarchy [Gre2,Eng2], and the top-down tree transducer hierarchy [OgdRou,Bak,Eng2]. As a contribution to the comparison of these hierarchies we show that the ETOL hierarchy is contained in the OI hierarchy (note that the 2-way GSM hierarchy is contained in the ETOL hierarchy). Since the ETOL hierarchy is obtained by iterating control on ETOL systems (studied in [Nie,GinRoz,Asv,EngRozSlu,Lan]), and the OI hierarchy can be obtained, as recently proved in [DamGoe] (see also [Mas2,EngVog2]), by iterating pushdowns as storage for one-way automata, this is another indication that iterated control is related to iterated pushdowns [Vog].