LIPIcs.STACS.2010.2480.pdf
- Filesize: 301 kB
- 12 pages
Document
Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
Author
-
Part of:
Volume:
27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2010-03-09
Cite As Get BibTex
Alexander Kartzow. Collapsible Pushdown Graphs of Level 2 are Tree-Automatic. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 501-512, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.STACS.2010.2480
Abstract
We show that graphs generated by collapsible pushdown systems of level $2$ are tree-automatic. Even when we allow $\varepsilon$-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.
Subject Classification
Keywords
- Tree-automatic structures
- collapsible pushdown graphs
- collapsible pushdown systems
- first-order decidability
- reachability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads