Göller, Stefan ;
Lohrey, Markus
The FirstOrder Theory of Ground Tree Rewrite Graphs
Abstract
We prove that the complexity of the uniform firstorder 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 firstorder 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 nonelementary firstorder theory.
BibTeX  Entry
@InProceedings{gller_et_al:LIPIcs:2011:3322,
author = {Stefan G{\"o}ller and Markus Lohrey},
title = {{The FirstOrder Theory of Ground Tree Rewrite Graphs}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {276287},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897347},
ISSN = {18688969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3322},
URN = {urn:nbn:de:0030drops33220},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.276},
annote = {Keywords: ground tree rewriting systems, firstorder theories, complexity}
}
2011
Keywords: 

ground tree rewriting systems, firstorder theories, complexity 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Related Scholarly Article: 


Issue date: 

2011 
Date of publication: 

2011 