Complexity of some natural problems in automatic structures

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 ∑ 1 0 -complete. We also prove that the embedding problem for automatic structures is ∑ 1 1 -complete.