The IO and OI hierarchies revisited

DOI10.1016/j.ic.2014.12.015zbMath1327.68145OpenAlexW2175025672MaRDI QIDQ2347807

Sylvain Salvati, Gregory M. Kobele

Publication date: 9 June 2015

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

Full work available at URL: https://doi.org/10.1016/j.ic.2014.12.015

zbMATH Keywords

membership problemsimply typed lambda-calculusformal language theoryMontague semanticshigher-order grammarsIOOI

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic of natural languages (03B65) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Combinatory logic and lambda calculus (03B40)

Related Items

Cost Automata, Safe Schemes, and Downward Closures ⋮ Unnamed Item ⋮ Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable ⋮ Unnamed Item ⋮ The Complexity of the Diagonal Problem for Recursion Schemes

Cites Work

• An alternate proof of Statman's finite completeness theorem
• On the membership problem for non-linear abstract categorial grammars
• The IO- and OI-hierarchies
• Iterated stack automata and complexity classes
• On the Significance of the Collapse Operation
• Loader and Urzyczyn Are Logically Related
• A Datalog Recognizer for Almost Affine λ-CFGs
• Recognizability in the Simply Typed Lambda-Calculus
• Completeness, invariance and λ-definability
• Recursive Schemes, Krivine Machines, and Collapsible Pushdown Automata
• CoTAGs and ACGs
• Semantic Evaluation, Intersection Types and Complexity of Simply Typed Lambda Calculus
• Indexed Grammars—An Extension of Context-Free Grammars
• Foundations of Software Science and Computational Structures
• The Safe Lambda Calculus
• 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 revisited