Path: utzoo!attcan!uunet!husc6!bbn!uwmcsd1!ig!arizona!debray
From: debray@arizona.edu (Saumya Debray)
Newsgroups: comp.lang.prolog
Subject: Re: Probabilistic 'or'?
Summary: almost always complete systems
Message-ID: <6570@megaron.arizona.edu>
Date: 6 Aug 88 11:38:55 GMT
References: <613@etive.ed.ac.uk>
Organization: U of Arizona CS Dept, Tucson
Lines: 21

In article <613@etive.ed.ac.uk>, jha@lfcs.ed.ac.uk (Jamie Andrews) writes:
> 
>      Does anyone know of a Prolog or other LP system with a
> probabilistic 'or' or probabilistic clause selection?  What I mean by
> this is a clause selection rule or disjunct selection rule which
> randomly selects which branch to follow and which to put in the
> backtrack stack. 

This is something I've thought about on and off.  One reason it would be
useful is that while a complete logic programming system would require
a fair clause selection rule (fair literal selection if you have negation),
and fairness is typically expensive to implement.  However, one could use
randomized clause selection to implement a system that would be complete
with probability 1 (i.e., almost always).  Of course, you randomize if and
only if you're about to create a choice point, so deterministic goals
aren't penalized.
-- 
Saumya Debray		CS Department, University of Arizona, Tucson

     internet:   debray@arizona.edu
     uucp:       arizona!debray