The Complexity of the Diagonal Problem for Recursion Schemes

DOI10.4230/LIPIcs.FSTTCS.2017.45zbMath1491.68101OpenAlexW2792967318MaRDI QIDQ5136337

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)

Related Items (7)

General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond ⋮ Unnamed Item ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Unnamed Item ⋮ Unnamed Item ⋮ General decidability results for asynchronous shared-memory programs: higher-order and beyond ⋮ Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered

Cites Work

• Unnamed Item
• The IO- and OI-hierarchies
• The IO and OI hierarchies revisited
• Strictness of the Collapsible Pushdown Hierarchy
• A Note on Decidable Separability by Piecewise Testable Languages
• Saturation-Based Model Checking of Higher-Order Recursion Schemes.
• Simply typed fixpoint calculus and collapsible pushdown automata
• An Approach to Computing Downward Closures
• The Complexity of Downward Closure Comparisons
• The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
• Pumping Lemma for Higher-order Languages
• Types and higher-order recursion schemes for verification of higher-order programs
• Pumping by Typing
• Collapsible Pushdown Automata and Recursion Schemes
• A characterization of lambda-terms transforming numerals
• A type-directed abstraction refinement approach to higher-order model checking
• Unsafe Order-2 Tree Languages Are Context-Sensitive
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Indexed Grammars—An Extension of Context-Free Grammars
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus

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