The Complexity of the Diagonal Problem for Recursion Schemes

DOI10.4230/LIPICS.FSTTCS.2017.45zbMATH Open1491.68101OpenAlexW2792967318MaRDI QIDQ5136337FDOQ5136337

Authors: Paweł Parys 

Publication date: 25 November 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2017.45

Recommendations

• The diagonal problem for higher-order recursion schemes is decidable
• The Complexity of Diagonalization
• Diagonalization in proof complexity
• Diagonalization strikes back: some recent lower bounds in complexity theory
• Diagonalizations over polynomial time computable sets
• Publication:4734760
• The complexity of recursive constraint satisfaction problems
• scientific article; zbMATH DE number 4108743
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity
• The Computational Complexity of Simultaneous Diophantine Approximation Problems

zbMATH Keywords

intersection typeshigher-order recursion schemesdownward closurediagonal problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• The IO- and OI-hierarchies
• Indexed Grammars—An Extension of Context-Free Grammars
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Types and higher-order recursion schemes for verification of higher-order programs
• Complexity of model checking recursion schemes for fragments of the modal mu-calculus
• A type-directed abstraction refinement approach to higher-order model checking
• A Note on Decidable Separability by Piecewise Testable Languages
• Unsafe order-2 tree languages are context-sensitive
• An approach to computing downward closures
• The diagonal problem for higher-order recursion schemes is decidable
• Collapsible pushdown automata and recursion schemes
• Saturation-Based Model Checking of Higher-Order Recursion Schemes.
• Strictness of the collapsible pushdown hierarchy
• The IO and OI hierarchies revisited
• Ordered tree-pushdown systems
• The complexity of downward closure comparisons
• Simply typed fixpoint calculus and collapsible pushdown automata
• Pumping Lemma for Higher-order Languages
• Pumping by typing
• A characterization of lambda-terms transforming numerals

Cited In (10)

• Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered
• General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond
• Title not available (Why is that?)
• Unboundedness problems for machines with reversal-bounded counters
• The diagonal problem for higher-order recursion schemes is decidable
• A type system describing unboundedness
• General decidability results for asynchronous shared-memory programs: higher-order and beyond
• Title not available (Why is that?)
• Diagonalization in proof complexity
• Homogeneity without loss of generality

This page was built for publication: The Complexity of the Diagonal Problem for Recursion Schemes

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