An automata-theoretical characterization of the OI-hierarchy

DOI10.1016/S0019-9958(86)80016-XzbMATH Open0628.68061OpenAlexW1971835879MaRDI QIDQ3765259FDOQ3765259

Authors: 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

Recommendations

• scientific article; zbMATH DE number 3997179
• scientific article; zbMATH DE number 3940754
• scientific article; zbMATH DE number 19775
• Deep pushdown automata
• Iterated stack automata and complexity classes

zbMATH Keywords

OI-hierarchylevel-n grammarsn-iterated pushdown automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (32)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3765259)