Dynamic Detection of Deterministic Computations in Non-Deterministic Functional-Logic Programs

Abstract. The detection of deterministic computations at run-time can be used to introduce dynamic cuts pruning the search space and thus in-creasing the efficiency of Functional-Logic systems. This idea was intro-duced in an early work of R. Loogen and S. Winkler. However the pro-posal of these authors cannot be used in current implementations because it did not consider non-deterministic functions and was not oriented to the demand driven strategy. Our work adapts and extends the technique, both showing how to deal with non-deterministic computations and how definitional trees can be employed to locate the places where the cuts will be introduced. An implementation based on a Prolog-translation is proposed, making the technique easy to implement in current systems generating Prolog code. Some experiments showing the effectiveness of the cut are presented.