The IO- and OI-hierarchies

DOI10.1016/0304-3975(82)90009-3zbMath0478.68012OpenAlexW2007098021MaRDI QIDQ1161273

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90009-3

zbMATH Keywords

denotational semantics typed lambda-calculus control structures call-by-value fixed-point operators call-by-name program schemes class of level-n schemes context-free finite modes macro languages recursion on higher types recursive procedures in ALGOL 68

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65) Recursive functions and relations, subrecursive hierarchies (03D20) General topics in the theory of software (68N01) Combinatory logic and lambda calculus (03B40)

Related Items

On Boolean closed full trios and rational Kripke frames, The grammar of mammalian brain capacity, On the \(\lambda Y\) calculus, Pushdown machines for the macro tree transducer, Transducers and the decidability of independence in free monoids, On the effect of the IO-substitution on the Parikh image of semilinear full AFLs, High level tree transducers and iterated pushdown tree transducers, Equivalences and transformations of regular systems - applications to recursive program schemes and grammars, Algebraic solutions to recursion schemes, 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, Unnamed Item, Recursion Schemes and the WMSO+U Logic, Unnamed Item, Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable, The generative power of delegation networks, On higher-order reachability games vs may reachability, Iterated linear control and iterated one-turn pushdowns, Simply typed fixpoint calculus and collapsible pushdown automata, Unnamed Item, Unnamed Item, Tree-stack automata, On rational definitions in complete algebras without rank, Krivine machines and higher-order schemes, Multidimensional trees, Iterated stack automata and complexity classes, On the expressive power of finitely typed and universally polymorphic recursive procedures, Basic notions of universal algebra for language theory and graph grammars, Krivine Machines and Higher-Order Schemes, Variable Tree Automata over Infinite Ranked Alphabets, Functional programs as compressed data, On the membership problem for non-linear abstract categorial grammars, Unnamed Item, Iterated pushdown automata and sequences of rational numbers, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity, Basic tree transducers, Look-ahead on pushdowns, Weighted automata with storage, A Survey on Decidable Equivalence Problems for Tree Transducers, On Global Model Checking Trees Generated by Higher-Order Recursion Schemes, Unnamed Item, General decidability results for asynchronous shared-memory programs: higher-order and beyond, Unnamed Item, ALGEBRAIC LINEAR ORDERINGS, Decidability of the finiteness of ranges of tree transductions, Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered, Principal abstract families of weighted tree languages, Wythoff games, continued fractions, cedar trees and Fibonacci searches, Domains for Higher-Order Games, Correctness of programs with Pascal-like procedures without global variables, \(L(A)=L(B)\)? decidability results from complete formal systems, Fundamental properties of infinite trees, Model-Checking Games for Typed λ-Calculi, The IO and OI hierarchies revisited, The Complexity of the Diagonal Problem for Recursion Schemes, The evaluation of first-order substitution is monadic second-order compatible, MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies, Output string languages of compositions of deterministic macro tree transducers, Macro tree transducers

Uses Software

Cites Work