The IO- and OI-hierarchies

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

Werner Damm

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 semanticstyped lambda-calculuscontrol structurescall-by-valuefixed-point operatorscall-by-nameprogram schemesclass of level-n schemescontext-freefinite modesmacro languagesrecursion on higher typesrecursive 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 (61)

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

• Unnamed Item
• LCF
• ALGOL 60

Cites Work

• A representation of trees by languages. II
• Attribute grammars and recursive program schemes. I. II
• On procedures as open subroutines. II
• Two-way nested stack automata are equivalent to two-way stack automata
• A generalized approach to formal languages
• LCF considered as a programming language
• IO and OI. II
• On formalised computer programs
• A lattice-theoretical fixpoint theorem and its applications
• The Semantics of Call-By-Value and Call-By-Name in a Nondeterministic Environment
• The Standardization Theorem for λ‐Calculus
• The denotational semantics of programming languages
• The Relation between Computational and Denotational Properties for Scott’s ${\text{D}}_\infty $-Models of the Lambda-Calculus
• Initial Algebra Semantics and Continuous Algebras
• Three hierarchies of transducers
• Correspondence between ALGOL 60 and Church's Lambda-notation
• Algebraic automata and context-free sets
• Indexed Grammars—An Extension of Context-Free Grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The IO- and OI-hierarchies