Abstract
dc:description.abstractThis 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.
Degree
thesis:*- Name dc:type.qualificationname
- Ph.D
- Level dc:type.qualificationlevel
- doctoral
- Grantor dc:publisher.institution
- University of Leeds
- Year dc:date.issued
- 2019
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Barker, Carolyn Suzanne
- Advisor dc:contributor.advisor
-
- Truss, John
Rights
- Language dc:language.dcterms_iso639_2
- eng
Identifiers
dc:identifier.*- Identifier
- uk.bl.ethos.804530
- Dc Identifier Grantnumber
- 110 Anniversary scholarship