  We show that graphs generated by collapsible pushdown systems of level 2 are
tree-automatic. Even if we allow epsilon-contractions and reachability
predicates (with regular constraints) for pairs of configurations, the
structures remain tree-automatic whence their first-order logic theories are
decidable. As a corollary we obtain the tree-automaticity of the second level
of the Caucal-hierarchy.
