Hill, Pat, King, Andy (1997) Determinacy and Determinacy Analysis. Journal of Programming Languages, 5 (1). pp. 135-171. ISSN 0963-9306. (KAR id:37586)
PDF
Language: English |
|
Download this file (PDF/1MB) |
Preview |
Request a format suitable for use with assistive technology e.g. a screenreader | |
Official URL: http://www.informatik.uni-trier.de/~ley/db/journal... |
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: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing |
Depositing User: | Andy King |
Date Deposited: | 12 Dec 2013 20:43 UTC |
Last Modified: | 16 Nov 2021 10:14 UTC |
Resource URI: | https://kar.kent.ac.uk/id/eprint/37586 (The current URI for this page, for reference purposes) |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):