Сложность некоторых естественных проблем в автоматных структурах

Доказано, что проблема автоматного изоморфизма автоматных структур, проблема существования нетривиального автоматного автоморфизма автоматной структуры, проблема автоматной вложимости автоматных структур $\Sigma_1^0$-полны. Также показана $\Sigma_1^1$-полнота проблемы вложения автоматных структур.