Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

We show that graphs generated by collapsible pushdown systems of level 2 aretree-automatic. Even if we allow epsilon-contractions and reachabilitypredicates (with regular constraints) for pairs of configurations, thestructures remain tree-automatic whence their first-order logic theories aredecidable. As a corollary we obtain the tree-automaticity of the second levelof the Caucal-hierarchy.Comment: Journal version of arXiv:0912.4110, accepted for publication in LMC