Skip to main content

Determinacy and Determinacy Analysis

Hill, Pat, King, Andy (1997) Determinacy and Determinacy Analysis. Journal of Programming Languages, 5 (1). pp. 135-171. ISSN 0963-9306.

Abstract

One unique feature of logic languages is their ability to succinctly and declaratively express non-determinacy and hence search. Improving search efficiency is one of the main goals of AI and, by studying how redundant search may be factored out, this paper contributes to this goal. In logic programming, alternatives can be specified by a set of sentences defining the same predicate. By backtracking, considering in turn each of these sentences, these alternatives can be explored until a solution (if one exists) is found. However, though backtracking is essential for certain parts of a program, typically many predicates are deterministic, and most queries to a program have no more than one solution. Providing for non-determinacy can slow down the execution of a program on a uniprocessor and limit the scope for parallel execution on a multiprocessor. As a consequence, programmers are often forced to resort to the non-logical features of the language to ensure any determinacy is fully exploited. A number of papers on determinacy and its detection have been published. However, because of the diversity of applications for determinacy analysis, there has been a similar diversity of definitions of determinacy and its related concepts. This paper reformulates the determinacy definitions in a uniform way, identifying and contrasting the different approaches. Techniques for detecting and exploiting determinacy are also reviewed together with some directions for future research

Item Type: Article
Subjects: A General Works
Divisions: Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Andy King
Date Deposited: 12 Dec 2013 20:43 UTC
Last Modified: 29 May 2019 11:40 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/37586 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year