Variants of collapsible pushdown systems

DOI10.4230/LIPICS.CSL.2012.500MaRDI QIDQ4649568zbMATH OpenOpenAlexFDO

Authors Paweł Parys

Publication date 22 November 2012

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

zbMATH Keywords

collapsible pushdown systemsdeterminizationinfinite hierarchyreachabilityshrinking lemma

Mathematics Subject Classification ID

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

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

Cited in

(6)

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

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)