10.4230/LIPICS.STACS.2010.2480
Kartzow, Alexander
Alexander
Kartzow
Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2010
Article
Tree-automatic structures
collapsible pushdown graphs
collapsible pushdown systems
first-order decidability
reachability
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
2010
2010-03-09
2010-03-09
2010-03-09
en
urn:nbn:de:0030-drops-24801
10.4230/LIPIcs.STACS.2010
978-3-939897-16-3
1868-8969
10.4230/LIPIcs.STACS.2010
LIPIcs, Volume 5, STACS 2010
27th International Symposium on Theoretical Aspects of Computer Science
2013
5
44
501
512
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2010
5
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
308412 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 5, 27th International Symposium on Theoretical Aspects of Computer Science, pages 501-512