Autor:	Kartzow, Alexander
Rok vydání:	2013
Předmět:	Computer Science - Logic in Computer Science Computer Science - Formal Languages and Automata Theory Mathematics - Logic F.4.1
Zdroj:	Logical Methods in Computer Science, Volume 9, Issue 1 (March 20, 2013) lmcs:1220
Druh dokumentu:	Working Paper
DOI:	10.2168/LMCS-9(1:12)2013
Popis:	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. Comment: Journal version of arXiv:0912.4110, accepted for publication in LMCS
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1303.2453 Zobrazit plný text záznamu View this record from Arxiv