Editing Occurs check (section)

==Rational tree unification==

Prolog implementations usually omit the occurs check for reasons of efficiency, which can lead to circular data structures and looping. 
By not performing the occurs check, the worst case complexity of unifying a term
<math>t_1</math> with term <math>t_2</math>
is reduced in many cases from
<math>O(\text{size}(t_1)+\text{size}(t_2))</math>
to
<math>O(\text{min}(\text{size}(t_1),\text{size}(t_2)))</math>;
in the frequent case of variable-term unification, runtime shrinks to 
<math>O(1)</math>.
{{refn|group=nb|Some Prolog manuals state that the complexity of unification without occurs check is 
<math>O(\text{min}(\text{size}(t_1),\text{size}(t_2)))</math> (in all cases).<ref>{{cite tech report|author1=F. Pereira |author2=D. Warren |author3=D. Bowen |author4=L. Byrd |author5=L. Pereira | title=C-Prolog's User's Manual Version 1.2| year=1983| institution=SRI International|URL=http://www.cs.duke.edu/csl/docs/cprolog.html| access-date=21 June 2013}}</ref>
This is incorrect, as it would imply comparing arbitrary ground terms in constant time (by unifying <math>eq(t_1,t_2)</math> with <math>eq(X,X)</math>).}}

Modern implementations, based on Colmerauer's Prolog II,
<ref>{{cite book| author=A. Colmerauer| author-link=Alain Colmerauer| title=Prolog and Infinite Trees| year=1982| publisher=Academic Press|editor1=K.L. Clark |editor2=S.-A. Tarnlund }}</ref>
<ref>{{cite journal|author1=M.H. van Emden |author2=J.W. Lloyd | title=A Logical Reconstruction of Prolog II| journal=Journal of Logic Programming| year=1984| volume=2| pages=143–149}}</ref>
<ref>{{cite journal|author1=Joxan Jaffar |author2=Peter J. Stuckey | title=Semantics of Infinite Tree Logic Programming| journal=Theoretical Computer Science| year=1986| volume=46| pages=141–158| doi=10.1016/0304-3975(86)90027-7| doi-access=free}}</ref>
<ref>{{cite journal| author=B. Courcelle| author-link=Bruno Courcelle| title=Fundamental Properties of Infinite Trees| journal=Theoretical Computer Science| year=1983| volume=25| issue=2| pages=95–169| doi=10.1016/0304-3975(83)90059-2| doi-access=free}}</ref>
use rational tree unification to avoid looping. However it is difficult to keep the complexity time linear in the presence of cyclic terms. Examples where Colmerauers algorithm becomes quadratic <ref>{{cite conference|author1=Albertro Martelli | author2=Gianfranco Rossi | title=Efficient Unification with Infinite Terms in Logic Programming| conference=The International Conference oj Fifth Generation Computer Systems| year=1984| url=https://www.ueda.info.waseda.ac.jp/AITEC_ICOT_ARCHIVES/ICOT/Museum/FGCS/FGCS84en-proc/84eFLP2-2.pdf}}</ref> can be readily constructed, but refinement proposals exist.

See image for an example run of the unification algorithm given in [[Unification (computer science)#A unification algorithm]], trying to solve the goal <math>cons(x,y) \stackrel{?}{=} cons(1,cons(x,cons(2,y)))</math>, however without the ''occurs check rule'' (named "check" there); applying rule "eliminate" instead leads to a cyclic graph (i.e. an infinite term) in the last step.