Home > Archive > Prolog > August 2005 > beginner's question: Difference between CWA and NAF
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
beginner's question: Difference between CWA and NAF
|
|
| DaMenge 2005-08-15, 9:01 am |
| Hi all,
I'm learning a bit theory about ProLog and DataLog, but I have a
problem understanding the difference between the "closed world
assumption" and "negation as failure".
Could anyone please tell me?
(Why aren't they equivalent, exspecially: why ist NAF => CWA not true?)
much thx
| |
| Torkel Franzen 2005-08-15, 9:01 am |
| "DaMenge" <c-programming@centermail.net> writes:
> Could anyone please tell me?
> (Why aren't they equivalent, exspecially: why ist NAF => CWA not true?)
"Negation as failure" doesn't even have the form of a statement.
What do you mean by "NAF => CWA"?
| |
| DaMenge 2005-08-15, 9:01 am |
| with "NAF => CWA" ,I mean :
"if one can suppose, that NAF leads to a correct interpretation of
negation then one can conclude the assumptions made by CWA"
Another way to say it : If you tell someone, who never heard anything
about CWA and NAF, that he can get the value of "not q(X)" in
p(X) :- s(X,Y), not q(X)
by checking all positive substitutes given by that s-literal in q to be
stored (or been proven in Prolog)
ie: let a positive substitution given by s , say X=a
if q(a) is proven(/stored), then "not q(a)" is wrong and if it's not,
then "not q(a)" is true.
With this rule of evaluation one should conclude the assumptions of the
CWA.
I guess i am wrong, but I don't see why at the moment.
Perhaps someone could give me an exact definition (for both: CWA and
NAF) first ?
thx for your help !
| |
| Mauro Di Nuzzo 2005-08-15, 5:02 pm |
| CWA (Reiter, 1978), also called "negation as infinite failure", is a
mechanism that allow us to draw negative conclusions based on the lack of
positive information.
NAF (Clark, 1978), also called "negation as finite failure", is a weaker
notion of CWA in which "false" means FINITELY failed.
A very very stupid example is the following.
f(a).
f(b).
f(X) :- f(X).
"not f(c)" follows from CWA, but cannot be concluded by NAF (the SLD-tree is
infinite).
Please consider to search on the net... g**gle
Regards,
M
"DaMenge" <c-programming@centermail.net> ha scritto nel messaggio
news:1124109030.630953.13870@f14g2000cwb.googlegroups.com...
> with "NAF => CWA" ,I mean :
> "if one can suppose, that NAF leads to a correct interpretation of
> negation then one can conclude the assumptions made by CWA"
>
> Another way to say it : If you tell someone, who never heard anything
> about CWA and NAF, that he can get the value of "not q(X)" in
> p(X) :- s(X,Y), not q(X)
> by checking all positive substitutes given by that s-literal in q to be
> stored (or been proven in Prolog)
> ie: let a positive substitution given by s , say X=a
> if q(a) is proven(/stored), then "not q(a)" is wrong and if it's not,
> then "not q(a)" is true.
>
> With this rule of evaluation one should conclude the assumptions of the
> CWA.
>
> I guess i am wrong, but I don't see why at the moment.
>
> Perhaps someone could give me an exact definition (for both: CWA and
> NAF) first ?
>
> thx for your help !
>
| |
| Torkel Franzen 2005-08-15, 5:02 pm |
| "DaMenge" <c-programming@centermail.net> writes:
> Perhaps someone could give me an exact definition (for both: CWA and
> NAF) first ?
There are different suggested justifications of negation as failure,
and we do indeed need precise formulations in order to be able to say
what implies what. I'm unfamiliar with the literature of the last
fifteen years or so, and don't know what survey to recommend.
| |
| DaMenge 2005-08-16, 4:01 am |
| Hi, thanks for your answer !
Mauro Di Nuzzo schrieb:
> CWA (Reiter, 1978), also called "negation as infinite failure", is a
> mechanism that allow us to draw negative conclusions based on the lack of
> positive information.
> NAF (Clark, 1978), also called "negation as finite failure", is a weaker
> notion of CWA in which "false" means FINITELY failed.
So you mean NAF is a Top-Down-progress ?
on every substitution given, it'll ask the SLD-tree down?
Then how can it decide wether it do fail finitely or not (ain't that
undecidable?)
>
> A very very stupid example is the following.
>
> f(a).
> f(b).
> f(X) :- f(X).
>
> "not f(c)" follows from CWA, but cannot be concluded by NAF (the SLD-tree is
> infinite).
ok, then we need a "safe" rule like:
p(X) :- s(X), not f(X).
(and another fact like s(c). )
but this would be a program with stratifikation, therefore all provable
facts of f can be found by a bottom-up progress like fixpoint
iteration.
(this should be equivalent to an infinite top-down progress by CWA, or
am I wrong?)
And after that the p(x) line is computable.
Of course - like you said : CWA is used to compute all provable facts.
But how can NAF work when only using a top-down SLD-tree?
I thought NAF was created to simply compute the given negation, but
isn't it undecideable ?
>
> Please consider to search on the net... g**gle
Believe me , I did...
But thank you again for your answer - now I see some difference between
NAF and CWA ..
| |
| Mauro Di Nuzzo 2005-08-16, 5:05 pm |
| Hi.
I think you have to distinguish between theory (logic and programming
languages) and practice (Prolog, in this case).
CWA deals mostly with theory, NFA with practice. Many correct theoretical
issues have to be modified (or even re-thought) to be implemented in Prolog.
This is done mostly to avoid Prolog's infinite loops.
Consider, for example, a simple program based on the transitive rule:
p(a,b).
p(b,c).
p(X,Y) :- p(X,Z), p(Z,Y).
In this case the goal
?- p(a,c).
succeeds (Z being b).
Now consider the following goal:
?- p(u,v).
According to CWA this is obviously false, but its falsity cannot be assessed
with NFA, because of an infinite loop.
Prolog engine tries to prove the following:
1) p(u,_1), p(_1,v).
2) p(u, _2), p(_2, _1), p(_1,v).
3) and so on...
So, it simply cannot never "decide".
Doesnt this appear to be strange, but quite obvious?
Cheers,
M
"DaMenge" <c-programming@centermail.net> ha scritto nel messaggio
news:1124181289.469681.224710@z14g2000cwz.googlegroups.com...
> Hi, thanks for your answer !
>
> Mauro Di Nuzzo schrieb:
of[color=darkred]
>
> So you mean NAF is a Top-Down-progress ?
> on every substitution given, it'll ask the SLD-tree down?
> Then how can it decide wether it do fail finitely or not (ain't that
> undecidable?)
>
SLD-tree is[color=darkred]
>
> ok, then we need a "safe" rule like:
> p(X) :- s(X), not f(X).
> (and another fact like s(c). )
>
> but this would be a program with stratifikation, therefore all provable
> facts of f can be found by a bottom-up progress like fixpoint
> iteration.
> (this should be equivalent to an infinite top-down progress by CWA, or
> am I wrong?)
> And after that the p(x) line is computable.
>
> Of course - like you said : CWA is used to compute all provable facts.
> But how can NAF work when only using a top-down SLD-tree?
> I thought NAF was created to simply compute the given negation, but
> isn't it undecideable ?
>
>
> Believe me , I did...
>
> But thank you again for your answer - now I see some difference between
> NAF and CWA ..
>
| |
| Mauro Di Nuzzo 2005-08-16, 5:05 pm |
| Sorry, I wrote NFA twice instead of NAF :-!
Bye
"Mauro Di Nuzzo" <picorna@inwind.it> ha scritto nel messaggio
news:m9qMe.19427$HM1.549234@twister1.libero.it...
> Hi.
> I think you have to distinguish between theory (logic and programming
> languages) and practice (Prolog, in this case).
> CWA deals mostly with theory, NFA with practice. Many correct theoretical
> issues have to be modified (or even re-thought) to be implemented in
Prolog.
> This is done mostly to avoid Prolog's infinite loops.
> Consider, for example, a simple program based on the transitive rule:
>
> p(a,b).
> p(b,c).
> p(X,Y) :- p(X,Z), p(Z,Y).
>
> In this case the goal
>
> ?- p(a,c).
>
> succeeds (Z being b).
> Now consider the following goal:
>
> ?- p(u,v).
>
> According to CWA this is obviously false, but its falsity cannot be
assessed
> with NFA, because of an infinite loop.
> Prolog engine tries to prove the following:
> 1) p(u,_1), p(_1,v).
> 2) p(u, _2), p(_2, _1), p(_1,v).
> 3) and so on...
> So, it simply cannot never "decide".
> Doesnt this appear to be strange, but quite obvious?
>
> Cheers,
> M
>
>
>
> "DaMenge" <c-programming@centermail.net> ha scritto nel messaggio
> news:1124181289.469681.224710@z14g2000cwz.googlegroups.com...
> of
weaker[color=darkred]
> SLD-tree is
>
>
|
|
|
|
|