Games on partial orders and other relational structures

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.