Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

DOI10.4230/LIPICS.STACS.2010.2480MaRDI QIDQ3113775zbMATH OpenOpenAlexFDO

Authors Alexander Kartzow

Publication date 23 January 2012

Full work available at URL https://arxiv.org/abs/0912.4110, http://subs.emis.de/LIPIcs/frontdoor_21bb.html

zbMATH Keywords

collapsible pushdown graphscollapsible pushdown systemsfirst-order decidabilityreachabilitytree-automatic structures

Mathematics Subject Classification ID

Logic in computer science (03B70) Formal languages and automata (68Q45)

Abstract: We show that graphs generated by collapsible pushdown systems of level 2 are tree-automatic. Even when we allow $epsilon$-contractions and add a reachability predicate (with regular constraints) for pairs of configurations, the structures remain tree-automatic. Hence, their FO theories are decidable, even when expanded by a reachability predicate. As a corollary, we obtain the tree-automaticity of the second level of the Caucal-hierarchy.

Recommendations

• Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
• A pumping lemma for collapsible pushdown graphs of level 2
• Collapsible pushdown automata and recursion schemes
• A pumping lemma for pushdown graphs of any level
• Collapsibility for directed acyclic graphs
• Strictness of the collapsible pushdown hierarchy
• Collapsible pushdown automata and labeled recursion schemes, equivalence, safety and effective selection
• Collapsible graphs and reductions of line graphs
• Two collapsing hierarchies of subregularly tree controlled languages
• scientific article; zbMATH DE number 2038738

Cited in

(10)

• Extensions of the Caucal hierarchy?
• A pumping lemma for pushdown graphs of any level
• Strictness of the collapsible pushdown hierarchy
• Krivine machines and higher-order schemes
• First-order model checking on generalisations of pushdown graphs.
• Variants of collapsible pushdown systems
• Krivine machines and higher-order schemes
• Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
• On the expressive power of higher-order pushdown systems
• On the structure of graphs in the Caucal hierarchy

This page was built for publication: Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

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