University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Computability over abstract data types.

Byers, Patrick. (1990) Computability over abstract data types. Doctoral thesis, University of Surrey (United Kingdom)..

Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (6MB) | Preview


This thesis extends the study of the notion of termination equivalence of abstract structures first proposed by Kfoury. The connection with abstract data types (ADTs) is made by demonstrating that many kinds of equivalence between ADT implementations are in fact instances of termination equivalence between their underlying algebras. The results in the thesis extend the original work in two directions. The first is to consider how the termination equivalence of structures is dependent upon the choice of programming formalism. The termination equivalences for all of the common classes of programs and for some new classes of non-computable schemes are studied, and their relative strengths are established. The other direction is a study of a congruence property of equivalences relative to the join or addition datatype building operation. We decide which of the termination equivalences are congruences for all structures and for all computable structures, and for those equivalences which are not, we characterise those congruences closest to them (both stronger and weaker). These programmes of work involved the use of constructions and properties of structures relating to program termination which are of interest in themselves. These are examined and are used to prove some general results about the relative strengths of termination equivalences.

Item Type: Thesis (Doctoral)
Divisions : Theses
Authors :
Byers, Patrick.
Date : 1990
Contributors :
Depositing User : EPrints Services
Date Deposited : 09 Nov 2017 12:18
Last Modified : 20 Jun 2018 11:57

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800