2026-07-22T19:10:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9670 2024-03-06T10:44:47Z ddc:004 open_access

Climbing up the Elementary Complexity Classes with Theories of Automatic Structures Abu Zaid, Faried Kuske, Dietrich Lindner, Peter Automatic Structures Complexity Theory Model Theory 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 non-elementary theory (e.g., the complete binary tree with equal-level predicate) and automatic structures whose theories are at most 3-fold exponential (e.g., Presburger arithmetic or infinite automatic graphs of bounded degree). This observation led Durand-Gasselin 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 h-fold exponential time and space. This exact determination of the complexity of the theory of these forests might be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Faried Abu Zaid and Dietrich Kuske and Peter Lindner 2018 Is Part Of LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2018.3 urn:nbn:de:0030-drops-96701 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode