Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/13016
Title: Exploring linear size-change terminating programs
Authors: NORMAN HUGH ANDERSON
Keywords: Program verification, termination, runtime, static analysis
Issue Date: 27-Nov-2007
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/13016
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

OPEN

NoneView/Download

Page view(s)

246
checked on Dec 2, 2017

Download(s)

218
checked on Dec 2, 2017

Google ScholarTM

Check


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