en>Dewritech: clean up, typo(s) fixed: verifcation → verification using AWB

2014-12-18T14:24:19Z

clean up, typo(s) fixed: verifcation → verification using AWB

← Older revision		Revision as of 16:24, 18 December 2014
Line 1:		Line 1:
	~~In [[computer science]], the '''occurs check'''~~ is a part of [[algorithm]]s for syntactic [[unification (computer science)\|unification]]. It causes unification of a [[First-order logic#Terms\|variable]] ''V'' and a structure ''S'' to fail if ''S'' contains ''V''.		She is known by the title of Myrtle Shryock. I utilized to be unemployed but now I am a librarian and the wage has been really satisfying. California is our birth location. Body building is what my family and I appreciate.<br><br>my blog post [http://AV8TheWeb.com/diettogo30380 http://AV8TheWeb.com/diettogo30380]

	~~==Application in theorem proving==~~

	~~In [[theorem proving]], unification without the occurs check can lead to [[unsound inference]]. For example,~~ the ~~[[Prolog]] goal~~
	~~<math>X = f(X)</math>~~
	~~will succeed, binding ''X'' to a cyclic structure which has no counterpart in the [[Herbrand universe]].~~
	~~As another example,~~
	~~<ref>{{cite book\| author=David A. Duffy\|~~ title~~=Principles~~ of ~~Automated Theorem Proving\| year=1991\| publisher=Wiley}}; here: p~~.~~143</ref>~~
	~~without occurs-check,~~ a ~~[[Resolution (logic)\|resolution proof]] can be found for the non-theorem~~
	~~<ref>Informally,~~ and ~~taking <math>p(x,y)</math> to mean e.g. "''x loves y''",~~ the ~~formula reads "''If everybody loves somebody, then a single person must exist that is loved by everyone.''"</ref>~~
	~~<math>(\forall x \exists y. p(x,y)) \rightarrow (\exists y \forall x. p(x,y))</math>: the negation of that formula~~ has the [[conjunctive normal form]] <math>p(X,f(X)) \land \lnot p(g(Y),Y)</math>, with <math>f</math> and <math>g</math> denoting the [[Skolem function]] for the first and second existential quantifier, respectively; the literals <math>p(X,f(X))</math> and <math>p(g(Y),Y)</math> are unifiable without occurs check, producing the refuting empty clause.

	~~[[File:Example for syntactic unification without occurs check leading to infinite tree svg~~.~~svg\|thumb\|upright=0.5\|Cycle by omitted occurs check]]~~
	~~==Prolog implementation==~~

	~~By default, 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 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 particular, the frequent case of variable-term unifications, runtime shrinks to <math>O(1)</math>.~~
	<ref>{{cite techreport\| author=F. Pereira, D. Warren, D. Bowen, L. Byrd, 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\| accessdate=21 June 2013}}</ref>

	~~A naive omission of the occurs check leads to the creation of cyclic structures~~
	and ~~may cause unification to loop forever~~.
	~~Modern implementations, based on Colmerauer's Prolog II,~~
	<~~ref~~>~~{{cite book\| author=A. Colmerauer\| title=Prolog and Infinite Trees\| year=1982\| publisher=Academic Press\| editor=K.L. Clark and S.-A. Tarnlund}}~~<~~/ref~~>
	~~<ref>{{cite journal\| author=M.H. van Emden, J.W. Lloyd\| title=A Logical Reconstruction of Prolog II\| journal=J. Logic Programming\| year=1984\| volume=2\| number=\| pages=143–149}}</ref>~~
	~~<ref>{{cite journal\| author=Joxan Jaffar, Peter J. Stuckey\| title=Semantics of Infinite Tree Logic Programming\| journal=laeoretical Computer Science\| year=1986\| volume=46\| pages=141–158}}</ref>~~
	~~<ref>{{cite journal\| author=B. Courcelle\| title=Fundamental Properties of Infinite Trees\| journal=Theoret. Comput. Sci.\| year=1983\| month=\| volume=25\| number=\| pages=95–169 \|url=~~http://~~www.diku.dk/hjemmesider/ansatte/henglein/papers/courcelle1983.pdf}}</ref>~~
	~~use [[rational tree unification]] to avoid looping.~~
	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.~~

	~~ISO Prolog implementations have the built-in predicate unify_with_occurs_check~~/2
	~~for sound unification but are free to use unsound or even looping algorithms~~
	~~when unification is invoked otherwise.~~
	~~Implementations offering sound unification~~
	~~for all unifications (optionally, via a runtime flag) are [[ECLiPSe]], [[XSB]] and [[SWI-Prolog]].~~

	~~==References==~~
	* {{cite journal\| author=W.P. Weijland\| title=Semantics for Logic Programs without Occur Check\| journal=Theoretical Computer Science\| year=1990\| month=\| volume=71\| number=\| pages=155–174\| url=http://~~oai~~.~~cwi.nl~~/~~oai/asset/2366/2366A.pdf}}~~
	~~{{reflist}}~~
	~~{{FOLDOC}}~~

	~~[[Category:Automated theorem proving]]~~
	~~[[Category:Logic programming]]~~
	~~[[Category:Programming constructs]]~~
	~~[[Category:Unification (computer science)]~~]

en>Nageh: categories

2012-04-13T15:18:30Z

categories

New page

In [[computer science]], the '''occurs check''' is a part of [[algorithm]]s for syntactic [[unification (computer science)|unification]]. It causes unification of a [[First-order logic#Terms|variable]] ''V'' and a structure ''S'' to fail if ''S'' contains ''V''.

==Application in theorem proving==

In [[theorem proving]], unification without the occurs check can lead to [[unsound inference]]. For example, the [[Prolog]] goal
<math>X = f(X)</math>
will succeed, binding ''X'' to a cyclic structure which has no counterpart in the [[Herbrand universe]].
As another example,
<ref>{{cite book| author=David A. Duffy| title=Principles of Automated Theorem Proving| year=1991| publisher=Wiley}}; here: p.143</ref>
without occurs-check, a [[Resolution (logic)|resolution proof]] can be found for the non-theorem
<ref>Informally, and taking <math>p(x,y)</math> to mean e.g. "''x loves y''", the formula reads "''If everybody loves somebody, then a single person must exist that is loved by everyone.''"</ref>
<math>(\forall x \exists y. p(x,y)) \rightarrow (\exists y \forall x. p(x,y))</math>: the negation of that formula has the [[conjunctive normal form]] <math>p(X,f(X)) \land \lnot p(g(Y),Y)</math>, with <math>f</math> and <math>g</math> denoting the [[Skolem function]] for the first and second existential quantifier, respectively; the literals <math>p(X,f(X))</math> and <math>p(g(Y),Y)</math> are unifiable without occurs check, producing the refuting empty clause.

[[File:Example for syntactic unification without occurs check leading to infinite tree svg.svg|thumb|upright=0.5|Cycle by omitted occurs check]]
==Prolog implementation==

By default, 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 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 particular, the frequent case of variable-term unifications, runtime shrinks to <math>O(1)</math>.
<ref>{{cite techreport| author=F. Pereira, D. Warren, D. Bowen, L. Byrd, 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| accessdate=21 June 2013}}</ref>

A naive omission of the occurs check leads to the creation of cyclic structures
and may cause unification to loop forever.
Modern implementations, based on Colmerauer's Prolog II,
<ref>{{cite book| author=A. Colmerauer| title=Prolog and Infinite Trees| year=1982| publisher=Academic Press| editor=K.L. Clark and S.-A. Tarnlund}}</ref>
<ref>{{cite journal| author=M.H. van Emden, J.W. Lloyd| title=A Logical Reconstruction of Prolog II| journal=J. Logic Programming| year=1984| volume=2| number=| pages=143–149}}</ref>
<ref>{{cite journal| author=Joxan Jaffar, Peter J. Stuckey| title=Semantics of Infinite Tree Logic Programming| journal=laeoretical Computer Science| year=1986| volume=46| pages=141–158}}</ref>
<ref>{{cite journal| author=B. Courcelle| title=Fundamental Properties of Infinite Trees| journal=Theoret. Comput. Sci.| year=1983| month=| volume=25| number=| pages=95–169 |url=http://www.diku.dk/hjemmesider/ansatte/henglein/papers/courcelle1983.pdf}}</ref>
use [[rational tree unification]] to avoid looping.
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.

ISO Prolog implementations have the built-in predicate unify_with_occurs_check/2
for sound unification but are free to use unsound or even looping algorithms
when unification is invoked otherwise.
Implementations offering sound unification
for all unifications (optionally, via a runtime flag) are [[ECLiPSe]], [[XSB]] and [[SWI-Prolog]].

==References==
* {{cite journal| author=W.P. Weijland| title=Semantics for Logic Programs without Occur Check| journal=Theoretical Computer Science| year=1990| month=| volume=71| number=| pages=155–174| url=http://oai.cwi.nl/oai/asset/2366/2366A.pdf}}
{{reflist}}
{{FOLDOC}}

[[Category:Automated theorem proving]]
[[Category:Logic programming]]
[[Category:Programming constructs]]
[[Category:Unification (computer science)]]

KCDSA - Revision history

en>Dewritech: clean up, typo(s) fixed: verifcation → verification using AWB

en>Nageh: categories