Variants of collapsible pushdown systems

DOI10.4230/LIPICS.CSL.2012.500zbMATH Open1252.68120OpenAlexW2293153760MaRDI QIDQ4649568FDOQ4649568

Authors: Paweł Parys 

Publication date: 22 November 2012

Full work available at URL: http://frontiersinai.com/turingfiles/September/39.pdf

Recommendations

• On the significance of the collapse operation
• Collapsible pushdown automata and recursion schemes
• Strictness of the collapsible pushdown hierarchy
• Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
• Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

zbMATH Keywords

reachabilitydeterminizationinfinite hierarchyshrinking lemmacollapsible pushdown systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited In (6)

• A Saturation Method for Collapsible Pushdown Systems
• Saturation of Concurrent Collapsible Pushdown Systems
• Strictness of the collapsible pushdown hierarchy
• On the significance of the collapse operation
• Collapsible pushdown automata and recursion schemes
• The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic

This page was built for publication: Variants of collapsible pushdown systems

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