Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!unixhub!stanford.edu!lucid.com!karoshi!fy From: fy@lucid.com (Frank Yellin) Newsgroups: comp.lang.lisp Subject: Re: EQUAL on circular lists Message-ID: Date: 8 Jun 91 00:45:01 GMT References: <2849@prles2.prl.philips.nl> Sender: usenet@lucid.com Organization: Lucid, Inc., Menlo Park, CA Lines: 17 In-Reply-To: fy@lucid.com's message of 7 Jun 91 16:15:31 A few comments on the super-equal algorithm I just sent. 1) Yes, I do know the difference between a stack and a queue and should have used the term "stack" throughout. The Finite State Automata algorithm I emulated uses a queue. Stacks are easier to implement in Lisp. It's not immediately obvious to me whether a depth-first search (from a stack) or a breadth-first search (from a queue) will give a faster result. Sorry for the name confusion. 2) The FSA algorithm is attributed to E.F. Moore. Don't know any more. 3) The algorithm must terminate, since the number of pairs you need to look at is at most sizeof(a) * sizeof(b), where "size" is the number of cons cells and atoms in the object.