文章基本信息

标题：The First-Order Theory of Ground Tree Rewrite Graphs
本地全文：下载
作者：Stefan G{\"o}ller ; Markus Lohrey
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：13
页码：276-287
DOI：10.4230/LIPIcs.FSTTCS.2011.276
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that the complexity of the uniform first-order theory of ground tree rewrite graphs is in ATIME(2^{2^{poly(n)}},O(n). Providing a matching lower bound, we show that there is some fixed ground tree rewrite graph whose first-order theory is hard for ATIME(2^{2^{poly(n)}},poly(n)) with respect to logspace reductions. Finally, we prove that there exists a fixed ground tree rewrite graph together with a single unary predicate in form of a regular tree language such that the resulting structure has a non-elementary first-order theory.
关键词：ground tree rewriting systems; first-order theories; complexity