Abu Zaid, Faried ;
Kuske, Dietrich ;
Lindner, Peter
Climbing up the Elementary Complexity Classes with Theories of Automatic Structures
Abstract
Automatic structures are structures that admit a finite presentation via automata. Their most prominent feature is that their theories are decidable. In the literature, one finds automatic structures with nonelementary theory (e.g., the complete binary tree with equallevel predicate) and automatic structures whose theories are at most 3fold exponential (e.g., Presburger arithmetic or infinite automatic graphs of bounded degree). This observation led DurandGasselin to the question whether there are automatic structures of arbitrary high elementary complexity.
We give a positive answer to this question. Namely, we show that for every h >=0 the forest of (infinitely many copies of) all finite trees of height at most h+2 is automatic and it's theory is complete for STA(*, exp_h(n, poly(n)), poly(n)), an alternating complexity class between hfold exponential time and space. This exact determination of the complexity of the theory of these forests might be of independent interest.
BibTeX  Entry
@InProceedings{abuzaid_et_al:LIPIcs:2018:9670,
author = {Faried Abu Zaid and Dietrich Kuske and Peter Lindner},
title = {{Climbing up the Elementary Complexity Classes with Theories of Automatic Structures}},
booktitle = {27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
pages = {3:13:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770880},
ISSN = {18688969},
year = {2018},
volume = {119},
editor = {Dan Ghica and Achim Jung},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9670},
URN = {urn:nbn:de:0030drops96701},
doi = {10.4230/LIPIcs.CSL.2018.3},
annote = {Keywords: Automatic Structures, Complexity Theory, Model Theory}
}
2018
Keywords: 

Automatic Structures, Complexity Theory, Model Theory 
Seminar: 

27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Issue date: 

2018 
Date of publication: 

2018 