An automata-theoretical characterization of the OI-hierarchy

DOI10.1016/S0019-9958(86)80016-XzbMath0628.68061OpenAlexW1971835879MaRDI QIDQ3765259

Werner Damm, Andreas Goerdt

Publication date: 1986

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80016-x

zbMATH Keywords

OI-hierarchylevel-n grammarsn-iterated pushdown automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (27)

On Boolean closed full trios and rational Kripke frames ⋮ The grammar of mammalian brain capacity ⋮ Transducers and the decidability of independence in free monoids ⋮ High level tree transducers and iterated pushdown tree transducers ⋮ General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond ⋮ Parameter-reduction of higher level grammars ⋮ The OI-hierarchy is closed under control ⋮ Unnamed Item ⋮ Simply typed fixpoint calculus and collapsible pushdown automata ⋮ Word-mappings of level 2 ⋮ Unnamed Item ⋮ On the structure of graphs in the Caucal hierarchy ⋮ Krivine machines and higher-order schemes ⋮ Iterated stack automata and complexity classes ⋮ On the expressive power of finitely typed and universally polymorphic recursive procedures ⋮ Iterated pushdown automata and sequences of rational numbers ⋮ Basic tree transducers ⋮ Look-ahead on pushdowns ⋮ Weighted automata with storage ⋮ General decidability results for asynchronous shared-memory programs: higher-order and beyond ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ Principal abstract families of weighted tree languages ⋮ Games on Higher Order Multi-stack Pushdown Systems ⋮ Regular sets over extended tree structures ⋮ Domains for Higher-Order Games ⋮ Model-Checking Games for Typed λ-Calculi ⋮ MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies

This page was built for publication: An automata-theoretical characterization of the OI-hierarchy