1 results
AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
-
- Journal:
- The Journal of Symbolic Logic / Volume 84 / Issue 4 / December 2019
- Published online by Cambridge University Press:
- 29 April 2019, pp. 1630-1669
- Print publication:
- December 2019
-
- Article
- Export citation
-
A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is
${\rm{\Sigma }}_1^1 $-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.
