Summary: We consider \(\omega ^{n}\)-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length \(\omega ^{n}\) for some integer \(n\geq 1\). We show that all these structures are \(\omega \)-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for \(\omega ^{2}\)-automatic (resp. \(\omega ^{n}\)-automatic for \(n>2\)) Boolean algebras (respectively, partial orders, rings, commutative rings, non-commutative rings, non-commutative groups) is not determined by the axiomatic system of ZFC. We infer from the proof of the above result that the isomorphism problem for \(\omega ^{n}\)-automatic Boolean algebras, \(n\geq 2\) (respectively, rings, commutative rings, non-commutative rings, non-commutative groups) is neither a \(\Sigma^1_{2}\)-set nor a \(\Pi^1_{2}\)-set. We obtain that there exist infinitely many \(\omega ^{n}\)-automatic, hence also \(\omega \)-tree-automatic, atomless Boolean algebras \(\mathcal B_{n}\), \(n\geq 1\), which are pairwise isomorphic under the continuum hypothesis CH and pairwise non-isomorphic under an alternative axiom, AT, strengthening a result of [the authors, Cent. Eur. J. Math. 8, No. 2, 299–313 (2010; Zbl 1207.03050)].