Theories of Automatic Structures and Their Complexity
Theories of Automatic Structures and Their Complexity
复制标题
自动结构及其复杂性理论
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Kuske
中科院分区：
文献类型：
--
作者：
D. Kuske
对于自动结构，有几种逻辑已经被证明是可判定的：一阶逻辑，它的无限量词的扩展，模计数量词，甚至二阶量化的限制形式。我们回顾这些可判定性证明。作为一个新的结果，我们确定了一阶逻辑的数据，表达式和量词类的组合复杂性。最后，我们还记得，一阶逻辑成为初等判定有界度的自动结构。
For automatic structures, several logics have been shown decidable: first-order logic, its extension by the infinity quantifier, by modulo-counting quantifiers, and even by a restricted form of second-order quantification. We review these decidability proofs. As a new result, we determine the data, the expression, and the combined complexity of quantifier-classes for first-order logic. Finally, we also recall that first-order logic becomes elementary decidable for automatic structures of bounded degree.