Abstract:
We prove that the automatic isomorphism problem for automatic structures, the automatic automorphism problem for an automatic structure, and the automatic embedding problem for automatic structures are $\Sigma_1^0$-complete. We also prove that the embedding problem for automatic structures is $\Sigma_1^1$-complete.