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

文章基本信息

  • 标题:Tree-Automatic Well-Founded Trees
  • 本地全文:下载
  • 作者:Martin Huschenbett ; Alexander Kartzow ; Jiamou Liu
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2013
  • 卷号:9
  • 期号:2
  • 页码:1
  • DOI:10.2168/LMCS-9(2:10)2013
  • 出版社:Technical University of Braunschweig
  • 摘要:We investigate tree-automatic well-founded trees. Using Delhomme's decomposition technique for tree-automatic structures, we show that the (ordinal) rank of a tree-automatic well-founded tree is strictly below omega^omega. Moreover, we make a step towards proving that the ranks of tree-automatic well-founded partial orders are bounded by omega^omega^omega: we prove this bound for what we call upwards linear partial orders. As an application of our result, we show that the isomorphism problem for tree-automatic well-founded trees is complete for level Delta^0_{omega^omega} of the hyperarithmetical hierarchy with respect to Turing-reductions.
  • 其他关键词:hyperarithmetical hierarchy, isomorphism problem, ordinal rank, tree-automatic structures, well-founded trees.
国家哲学社会科学文献中心版权所有