Collapsible pushdown automata and recursion schemes

DOI10.1145/3091122MaRDI QIDQ5369241zbMATH OpenOpenAlexFDO

Authors

Publication date 16 October 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/lics.2008.34

zbMATH Keywords

higher-order (collapsible) pushdown automatahigher-order recursion schemes

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Collapsible pushdown automata and labeled recursion schemes, equivalence, safety and effective selection
• Recursive schemes, Krivine machines, and collapsible pushdown automata
• scientific article; zbMATH DE number 5825969
• Recursion schemes, collapsible pushdown automata and higher-order model checking
• Variants of collapsible pushdown systems

Cited in

(34)

• General decidability results for asynchronous shared-memory programs: higher-order and beyond
• Colored nested words
• Higher-order recursion schemes and their automata models
• Reachability for dynamic parametric processes
• Collapsible pushdown automata and labeled recursion schemes, equivalence, safety and effective selection
• On the significance of the collapse operation
• Krivine machines and higher-order schemes
• scientific article; zbMATH DE number 5825969 (Why is no real title available?)
• Collapse operation increases expressive power of deterministic higher order pushdown automata
• Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
• FO Model Checking on Nested Pushdown Trees
• Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes
• On Global Model Checking Trees Generated by Higher-Order Recursion Schemes
• Games on Higher Order Multi-stack Pushdown Systems
• The recursion hierarchy for PCF is strict
• Variants of collapsible pushdown systems
• Recursive schemes, Krivine machines, and collapsible pushdown automata
• Recursion schemes, collapsible pushdown automata and higher-order model checking
• Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
• Parity to safety in polynomial time for pushdown and collapsible pushdown systems
• Collapsible pushdown parity games
• On the expressivity of linear recursion schemes
• Recursion schemes, the MSO logic, and the \textsf{U} quantifier
• Domains for Higher-Order Games
• On the expressive power of higher-order pushdown systems
• On the termination problem for probabilistic higher-order recursive programs
• The Complexity of the Diagonal Problem for Recursion Schemes
• Cost Automata, Safe Schemes, and Downward Closures
• Probabilistic verification beyond context-freeness
• Profinite lambda-terms and parametricity
• Implicit automata in typed -calculi I: aperiodicity in a non-commutative logic
• Extending the WMSO+U logic with quantification over tuples
• The structure of trees in the pushdown hierarchy
• Higher-order model checking step by step

This page was built for publication: Collapsible pushdown automata and recursion schemes

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