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

lmcs:1220 - Logical Methods in Computer Science, March 20, 2013, Volume 9, Issue 1 - https://doi.org/10.2168/LMCS-9(1:12)2013
Collapsible Pushdown Graphs of Level 2 are Tree-AutomaticArticle

Authors: Alexander Kartzow

    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.

    https://doi.org/10.2168/LMCS-9(1:12)2013
    Source: arXiv.org:1303.2453
    Volume: Volume 9, Issue 1
    Published on: March 20, 2013
    Imported on: August 2, 2011
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory,Mathematics - Logic,F.4.1
    Licence: arXiv.org - Non-exclusive license to distribute

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    4 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 1500 times.
    This article's PDF has been downloaded 326 times.