Determinacy and Determinacy Analysis

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