inria-00455744, version 1
Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010 (2010) 501-512
Résumé : 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.
- 1 : Fachbereich Mathematik
- TU Darmstadt
- Domaine : Mathématiques/Logique
- Mots-clés : tree-automatic structures – collapsible pushdown graphs – collapsible pushdown systems – first-order decidability – reachability
- inria-00455744, version 1
- http://hal.inria.fr/inria-00455744
- oai:hal.inria.fr:inria-00455744
- Contributeur : Publications Loria
- Soumis le : Jeudi 11 Février 2010, 09:56:52
- Dernière modification le : Jeudi 11 Février 2010, 14:09:43
Documents associés
PDF : 
Voir aussi
Exporter