In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game ? We (...) provide algorithms for solving the Ehrenfeucht–Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n. (shrink)

The main result of this paper states that the isomorphism problem for ω-automatic trees of finite height is at least has hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies showing that the isomorphism problem for ω-automatic structures is not in . Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for ω-automatic trees of finite height is recursively equivalent with second-order arithmetic. On the way to (...) our main results, we show lower and upper bounds for the isomorphism problem for ω-automatic trees of every finite height: It is decidable , for height 1 , -hard and in for height 3, and - and -hard and in for height . All proofs are elementary and do not rely on theorems from set theory. (shrink)