Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!harvard!husc6!panda!genrad!decvax!decwrl!logic.dec.com!vantreeck
From: vantreeck@logic.dec.com.UUCP
Newsgroups: net.lang.prolog
Subject: Depth First Iterative Deepening in parallel PROLOGs
Message-ID: <3145@decwrl.DEC.COM>
Date: Wed, 21-May-86 13:08:09 EDT
Article-I.D.: decwrl.3145
Posted: Wed May 21 13:08:09 1986
Date-Received: Sat, 24-May-86 03:09:34 EDT
Sender: daemon@decwrl.DEC.COM
Organization: Digital Equipment Corporation
Lines: 17

I've read that parallel processor implementations of PROLOG machines use some
variant of breadth first search. I was wondering if anybody has designed a
parallel implementation using DFID (Depth First Iterative Deepening). Because
it has been proven that DFID is the asymptotically optimal brute-force tree
search algorithm (asymptotically optimal in cost of solution, space, and time),
I was thinking that perhaps it may have usefulness in parallelism. 

Would it be worth while for me to try and develop an DFID-PROLOG for a single
processor, e.g., on my Apple Macintosh? Or are their some problems that would
would make such a PROLOG to large for the Mac? Is the algorithm applicable
to a parallel PROLOG?

						George Van Treeck
						Digtal Equip. Corp.

PS: If you're not familiar with the algorithm, it's description and proof
of optimality can be found in: ARTIFICAL INTELLIGENCE 27(1985) 97-109