The Complexity of the Diagonal Problem for Recursion Schemes

DOI10.4230/LIPICS.FSTTCS.2017.45MaRDI QIDQ5136337zbMATH OpenOpenAlexFDO

Authors Paweł Parys

Publication date 25 November 2020

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

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)

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

Cites work

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

Cited in

(10)

• Diagonalization in proof complexity
• General decidability results for asynchronous shared-memory programs: higher-order and beyond
• scientific article; zbMATH DE number 7199579 (Why is no real title available?)
• scientific article; zbMATH DE number 7526052 (Why is no real title available?)
• Unboundedness problems for machines with reversal-bounded counters
• General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond
• The diagonal problem for higher-order recursion schemes is decidable
• A type system describing unboundedness
• Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered
• 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)