2009/12/21 by Alexander Kartzow, Kartzow, Alexander · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, programming, and type systems #math.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0912.4110
12 pages Accepted for STACS 2010
openalex publication_date 2009/12/21 · arxiv created 2010/02/03 · arxiv updated 2010/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that graphs generated by collapsible pushdown systems of level 2 are tree-automatic. Even when we allow ε-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.