[1] : The Free On-line Dictionary of Computing (27 SEP 03)

occurs check
     
         a feature of some implementations of
        unification which causes unification of a logic variable v
        and a structure s to fail if s contains v.
     
        binding a variable to a structure containing that variable
        results in a cyclic structure which may subsequently cause
        unification to loop forever.  some implementations use extra
        pointer comparisons to avoid this.
     
        most implementations of prolog do not perform the occurs
        check for reasons of efficiency.  without occurs check the
        complexity of unification is
     
        	ominsizeterm1, sizeterm2
     
        with occurs check it's
     
        	omaxsizeterm1, sizeterm2
     
        in theorem proving unification without the occurs check can
        lead to unsound inference.  for example, in prolog it is
        quite valid to write
     
        	x = fx.
     
        which will succeed, binding x to a cyclic structure.  clearly
        however, if f is taken to stand for a function rather than a
        constructor, then the above equality is only valid if f is
        the identity function.
     
        weijland calls unification without occur check, "complete
        unification".  the reference below describes a complete
        unification algorithm in terms of colmerauer's consistency
        algorithm.
     
        "semantics for logic programs without occur check",
        w.p. weijland, theoretical computer science 71 1990 pp
        155-174.
     
        1996-01-11
     
     
see also:
unification logic variable prolog complexity theorem proving constructor 
identity function 

Check >> C Words
Check, definition of term: Check
check_pag1.html

Check Mark >> C Words
Check Mark, definition of term: Check Mark
check+mark_pag1.html

Check Off >> C Words
Check Off, definition of term: Check Off
check+off_pag1.html

Check List >> C Words
Check List, definition of term: Check List
check+list_pag1.html

Check Out >> C Words
Check Out, definition of term: Check Out
check+out_pag1.html

Check In >> C Words
Check In, definition of term: Check In
check+in_pag1.html

Check For >> C Words
Check For, definition of term: Check For
check+for_pag1.html

Certified Check >> C Words
Certified Check, definition of term: Certified Check
certified+check_pag1.html

Cashiers Check >> C Words
Cashiers Check, definition of term: Cashiers Check
cashiers+check_pag1.html