文章基本信息

标题：Climbing up the Elementary Complexity Classes with Theories of Automatic Structures
本地全文：下载
作者：Faried Abu Zaid ; Dietrich Kuske ; Peter Lindner 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：119
页码：1-16
DOI：10.4230/LIPIcs.CSL.2018.3
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Automatic Structures; Complexity Theory; Model Theory