Collapse operation increases expressive power of deterministic higher order pushdown automata

DOI10.4230/LIPICS.STACS.2011.603MaRDI QIDQ3113723zbMATH OpenFDO

Authors Paweł Parys

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_1196.html

zbMATH Keywords

collapsibledeterministic second level pushdown automatapushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the significance of the collapse operation
• Collapsible pushdown automata and recursion schemes
• scientific article; zbMATH DE number 5825969
• Strictness of the collapsible pushdown hierarchy
• Higher-order pushdown systems with data

Cited in

(4)

• On first-order logic and CPDA graphs
• On the significance of the collapse operation
• Higher-order pushdown systems with data
• On the expressive power of higher-order pushdown systems

This page was built for publication: Collapse operation increases expressive power of deterministic higher order pushdown automata

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