Back to search

University of Southampton

Judgement day : terminating logic problems

Abstract

dc:description.abstract

<p>This thesis studies termination of logic programs and termination of program specialisation in particular. Two approaches to the latter are traditionally recognised. The <i>offline</i> approach divides the specialisation process into two phases; the first is an analysis phase which gathers termination information which is used to guide the specialisation proper in the second phase. This separation of components provides an identifiable termination component within a tool and is good software engineering practice. It also offers a number of other advantages over the <i>online</i> approach where the two phases are intertwined. In logic programming, however, the focus of attention has been on online techniques since they have generally offered better potential for optimisation.</p><p>This thesis proposes the first solution to automatic, offline specialisation of logic programs which compares favourably with current online techniques with regard to its optimisation capability. Specifically, it is the first offline technique in logic programming to pass the, so called, KMP test which has become the acid test for program specialisation techniques; the automatic generation of a fast pattern nuclear from a naive one.</p><p>To this end, a number of techniques for termination analysis are developed culminating in the identification of a useful termination criterion for coroutining logic programs. Such programs are notoriously difficult to prove terminating, yet they provide an extremely useful model for an essential part of the program specialisation process. Tackling this problem in turn leads to the establishment of a solid link between the fields of program specialisation and termination analysis, laying the foundation for the proposed offline approach.</p>

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2000

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Martin, Jonathan Charles

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Martin, Jonathan Charles. Judgement day : terminating logic problems. doctoral thesis, University of Southampton, 2000.