Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!harpo!seismo!hao!hplabs!sri-unix!pereira
From: pereira@sri-unix.UUCP
Newsgroups: net.lang.prolog
Subject: Re: Breadth-First Traversal: O(v) ???
Message-ID: <500@sri-unix.UUCP>
Date: Wed, 2-May-84 03:39:48 EDT
Article-I.D.: sri-unix.500
Posted: Wed May  2 03:39:48 1984
Date-Received: Fri, 4-May-84 02:59:33 EDT
References: uicsl.17400001
Lines: 8

Your criticism of Sanjai's article is not quite correct. It is true that in
most Prolog systems the complexity would be O(n^2) because of the
clause search for succ, but this not necessarily so. On DEC-10/20 Prolog,
for example, clauses are indexed on their first argument and so the
succ lookup would be O(1). I think that some other Prolog systems
(LM-Prolog comes to mind) have similar facilities.

-- Fernando Pereira