This thesis makes a contribution to the classification of certain specific relational structures
under the relation of n-equivalence, where this means that Player II has a winning strategy
in the n-move Ehrenfeucht-Fraı̈ssé game played on the two structures. This provides a
finer classification of structures than elementary equivalence, since two structures A and
B are elementarily equivalent if and only if they are n-equivalent for all n. On each move
of such a game, Player I picks a member of either A or B, and Player II responds with a
member of the other structure. Player II wins the game if the map thereby produced from
a substructure of A to a substructure of B is an isomorphism of induced substructures.
Certain ordered structures have been studied from this point of view in papers by
Mostowski and Tarski, for ordinals [22], and Mwesigye and Truss, for ordinals [25], some
scattered orders, and finite coloured linear orders [24]. Here we extend the known results
on linear orders by classifying them all up to 3-equivalence (which had previously been
done for 2-equivalence), of which there are 281, using the method of characters.
We also classify all partial orders up to 2-equivalence (there are 39), and discuss the
difficulties of extending this to 3-equivalence, since the method of characters is not as
effective as in the linear case. We classify (total) circular orders up to 3-equivalence, and
relate the classification of partial circular orders to both these and to partial orders. A
variety of related structures are discussed: trees, directed and undirected graphs, and
unars (sets with a single unary function), which we categorise up to 2-equivalence.
In a pebble game, the players of an otherwise standard Ehrenfeucht-Fraı̈ssé game are in
addition provided with two identical sets of k distinguishable pebbles, and on each move
they place a pebble on their chosen point. On each move, Player I may choose either to
move a pebble to another point, or else use a new pebble, if any remain, and Player II must
place the corresponding partner pebble. Such games correspond to logics in which there
are only k variables, and moving a pebble corresponds to reusing the variable. Here we
extend some work of Immerman and Kozen [14] on pebble games played on linear orders.
