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.
展开▼
