Göller, Stefan and Lohrey, Markus - The First-Order Theory of Ground Tree Rewrite Graphs

lmcs:1223 - Logical Methods in Computer Science, February 12, 2014, Volume 10, Issue 1
The First-Order Theory of Ground Tree Rewrite Graphs

Authors: Göller, Stefan and Lohrey, Markus

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.


Source : oai:arXiv.org:1107.0919
DOI : 10.2168/LMCS-10(1:7)2014
Volume: Volume 10, Issue 1
Published on: February 12, 2014
Submitted on: October 30, 2012
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity


Share

Consultation statistics

This page has been seen 51 times.
This article's PDF has been downloaded 36 times.