Please use this identifier to cite or link to this item:
Title: Exploring linear size-change terminating programs
Keywords: Program verification, termination, runtime, static analysis
Issue Date: 27-Nov-2007
Citation: NORMAN HUGH ANDERSON (2007-11-27). Exploring linear size-change terminating programs. ScholarBank@NUS Repository.
Abstract: This thesis explores an area of research into the analysis of a particular set of programs. The set of programs is known as the "linear size-change terminating" programs, a significant subset of all programs, whose termination can be decided with an automated technique: size-change termination analysis. This analysis technique begins by generating size-change graphs from program sources, which are then analyzed using graphical analysis techniques. The work outlines progressive research developments, firstly replacing the traditional size-change graphs used in size-change termination analysis, with affine-based graphs, in which affine relations among parameters are expressed by Presburger formulC&. In this approach, the data-types of the parameters that control the termination of a program must be well-founded, and (eventually) reducing. The termination analysis is extended in various ways to include not just reducing well-founded parameters, but those which are bounded in some domain. This development is termed "Bounded termination", and extends the set of size-change terminating programs. Finally, the polynomial and exponential runtime and stack depth costs of a subset of the programs can be precisely calculated. The thesis concludes with an outline of some possibilities of future research directions.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Thesisv11.singlespaced.pdf966.78 kBAdobe PDF



Page view(s)

checked on Apr 19, 2019


checked on Apr 19, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.