Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!rpi!zaphod.mps.ohio-state.edu!tut.cis.ohio-state.edu!att!dptg!ulysses!andante!alice!pereira
From: pereira@alice.UUCP (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Does It Unify?
Message-ID: <10838@alice.UUCP>
Date: 18 May 90 14:56:47 GMT
References: <1990May7.132305.15989@agate.berkeley.edu> <189@qt.cs.utexas.edu> <24861@pasteur.Berkeley.EDU> <191@qt.cs.utexas.edu> <10809@alice.UUCP> <194@qt.cs.utexas.edu> <40089@brunix.UUCP>
Reply-To: pereira@alice.UUCP ()
Distribution: usa
Organization: AT&T, Bell Labs
Lines: 17

In article <40089@brunix.UUCP> mj@cs.brown.edu (Mark Johnson) writes:
>It is computationally cheaper to implement safe unification and eq-tests
>than to implement the occurs check.
It is not clear that this is the case asymptotically , see for instance

``An Almost Linear Robinson Unification Algorithm'' by Peter Ruzicka (missing
some diacritics) and Igor Privara, Acta Informatica 27, pp.61-71, 1989.

Unfortunately, the real problem is constant factors; every rational term
unification algorithm I know requires far more (and more complex) trailing
of side-effects to terms than the usual Prolog unification. No free lunch...

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, Murray Hill, NJ 07974
pereira@research.att.com