DETERMINACY AND DETERMINACY ANALYSIS

One unique feature of logic languages is their ability to succinctly a nd declaratively express non-determinacy and hence search. Improving s earch efficiency is one of the main goals of AI and, by studying how r edundant search may be factored out, this paper contributes to this go al. In logic programming, alternatives can be specified by a set of se ntences defining the same predicate. By backtracking, considering in t urn each of these sentences, these alternatives can be explored until a solution (if one exists) is found. However, though backtracking is e ssential for certain parts of a program, typically many predicates are deterministic, and most queries to a program have no more than one so lution. 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 dete rminacy is fully exploited. A number of papers on determinacy and its detection have been published. However, because of the diversity of ap plications for determinacy analysis, there has been a similar diversit y of definitions of determinacy and its related concepts. This paper r eformulates 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 direction s for future research.