Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

Alexander Kartzow

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 cons…