首页    期刊浏览 2024年12月11日 星期三
登录注册

文章基本信息

  • 标题:Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
  • 作者:Alexander Kartzow
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2010
  • 卷号:5
  • 页码:501-512
  • DOI:10.4230/LIPIcs.STACS.2010.2480
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Tree-automatic structures; collapsible pushdown graphs; collapsible pushdown systems; first-order decidability; reachability
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有