Kartzow, Alexander - Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

lmcs:1220 - Logical Methods in Computer Science, March 20, 2013, Volume 9, Issue 1
Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

Authors: Kartzow, Alexander

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.

Source : oai:arXiv.org:1303.2453
DOI : 10.2168/LMCS-9(1:12)2013
Volume: Volume 9, Issue 1
Published on: March 20, 2013
Submitted on: August 2, 2011
Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory,Mathematics - Logic,F.4.1


Consultation statistics

This page has been seen 39 times.
This article's PDF has been downloaded 15 times.