W3C home > Mailing lists > Public > public-rule-workshop-discuss@w3.org > August 2005

Re: NAF and NEG [was: LP Semantics (non-monotonicity) in Usage Scenarios?]

From: Carlos Viegas Damásio <cd@di.fct.unl.pt>
Date: Mon, 29 Aug 2005 13:49:26 +0100
To: <public-rule-workshop-discuss@w3.org>
Message-ID: <000301c5ac98$173ce380$db8ec151@zaratrusta>
Dear all,

 

>> By the way, we are not advocating for NAF at the exclusion of 

>> classical negation. There are extensions of LP, which support 

>> classical negation as well (flora-2 doesn't support that yet). 

>

>That's not quite true, Michael: the second negation (e.g. in 

>extended logic programs as defined by Gelfond and Lifschitz) is 

>only called "classical", but it is not clasical negation because

>it does not obey the law of the excluded middle (LEM). And this 

>should not come as a surprise: the LEM creates a certain kind of 

>indefiniteness (e.g. it implies the principle of reasoning by 

>cases) that cannot be handled by a computational system without

>severe restrictions (such as DL).

>

>Therefore the second negation in these formalisms does not 

>correspond to classical 2-valued (i.e. Boolean) negation, but 

>rather to 3/4-valued Kleene negation.

 

I claim that the existence of these two forms of negation (“as failure” and
“strong”) can help solving the quarrel between “monotonics” and
“nonmonotonics”

I agree fully with the point of view that Michael Kifer has been actively
supporting in this and other forums; so I am a “nonmonotonic”.

My proposal attempts to reach a compromise between both sides, by letting
knowledge-base programmers (producers) to use the forms of reasoning they
like and

the users (consumers) to prevent the use forms of reasoning they dislike. A
more complete discussion can be found in the draft publicly available at
http://centria.di.fct.unl.pt/~cd/publicacoes/openclosed.pdf.

The mechanisms are the following:

 

- PRODUCERs

 

The knowledge is organized in knowledge-base (rulesets, modules, etc.) and
predicates are classified according to the following categories:

 

1) OPEN: a predicate declared open is visible outside the knowledge base,
and intends to capture global predicates

which are being defined in the Semantic Web. In particular, it can be
declared elsewhere and only strong negation can be applied to them.

 

2) VISIBLE: these predicates are visible outside the knowledge bases where
have been declared, but cannot be declared by any other

knowledge base in the Semantic Web.   As before, only strong negation can be
applied to these predicates.

 

3) LOCAL: these are predicates are to be used only inside the knowledge
base, but are restricted in that only strong negation can be used.

 

4) POSCLOSED and NEGCLOSED: these are predicates for use only in the current
module but rules are completed. If POSCLOSED is used to declare 

predicate $P$ then the rule 

 

NEG P :- SNAF P.

 

is implicitly asserted, and the dual one for NEGCLOSED, completing the
knowledge. 

The scope of SNAF is the current knowledge-base.

Again, anywhere else in the knowledge base, only strong negation can be
used. The closure rule may be inhibited by the consumer of the knowledge.

 

5) INTERNAL: predicate is internal to the knowledge base but now any form of
negation/reasoning can be used inside the knowledge base, and its use

can be forbidden by the consumer of the knowledge.

 

 

The labels for each mode may be changed to better reflect their intent.
There is also some degree of freedom in the above, that I will not discuss
now (e.g. closed predicates might be visible). 

 

- CONSUMERs

 

The user or application controlling a local context should be able to use
any of the following modes:

 

1) ALLOW-ALL: In this mode, any form of reasoning is allowed, monotonic or
not. 

The only error that might occur is that a predicate declared visible in some
module is declared elsewhere. In

this case, the agent may pick one of the knowledge bases to use or abort.
Inconsistencies and contradictions are detected, and the user

appropriately warned. Consequences obtained by default reasoning might also
be identified. This also applies to the subsequent modes.

 

2) ALLOW-CLOSED: In this mode, closed predicates might be used, but no
predicate can be declared internal. If there is an

internal predicate, the knowledge base cannot be used, and processing should
abort.

 

3) FORCE-OPEN: In this mode, closure rules are inhibited and cannot be used
in the inference engine by its deductive mechanisms.

Obviously, internal predicates are forbidden.

 

4) REJECT-CLOSED: The final mode rejects both closed and internal predicates
in knowledge bases.

 

I suggest to use FORCE-OPEN as default mode, since it does not extract
consequences by nonmotonic reasoning, and knowledge

bases might be combined together monotonically (if the mode used is always
FORCE-OPEN). 

Furthermore, all conclusions obtained from this mode are also obtained in
mode ALLOW-CLOSED.

However, some consequences obtained in any of the modes other than
FORCE-OPEN might not be inferred in ALLOW-CLOSED. 

 

So, any producer/consumer may blindly use knowledge bases in the Semantic
Web under FORCE-OPEN mode. 

Mode ALLOW-CLOSED can be used to extract more consequences, but which can be
retracted later on

when new knowledge is made available.

 

 

EXAMPLE:

 

RULEBASE xpto1

 

OPEN country/1.

VISIBLE memberEU/1.

 

        memberEU(?C) :-  country(?C),          listedMemberEU(?C).

NEG memberEU(?C)  :- country(?C), NEG listedMemberEU(?C).

 

NEG memberEU(usa).

NEG memberEU(canada).

 

 

POSCLOSED listedMemberEU/1.

 

listedMember(austria).

listedMember(Belgium).

…

listedMember(UnitedKingdom).

 

 

RULEBASE xpto2

 

OPEN country/1.

 

country(austria).

…

country(turkey).

country(china).

country(usa).

 

 

 

Suppose now that we have a mechanism of putting these two rulebases together
(the other issue in discussion…)

In mode FORCE-OPEN, the following conclusions are obtained:

 

[xpto1,xpto2] ?- memberEU(austria).

Yes

 

[xpto1,xpto2] ?- memberEU(usa).

No

 

[xpto1,xpto2] ?- memberEU(turkey).

No

 

[xpto1,xpto2] ?- NEG memberEU(austria).

No

 

[xpto1,xpto2] ?- NEG memberEU(usa).

Yes

 

[xpto1,xpto2] ?- NEG memberEU(turkey).

No

 

Now, in ALLOW-CLOSED mode we get the extra “nonmonotonic” conclusion NEG
member(turkey): 

 

[xpto1,xpto2] ?- memberEU(austria).

Yes

 

[xpto1,xpto2] ?- memberEU(usa).

No

 

[xpto1,xpto2] ?- memberEU(turkey).

No

 

[xpto1,xpto2] ?- NEG memberEU(austria).

No

 

[xpto1,xpto2] ?- NEG memberEU(usa).

Yes

 

[xpto1,xpto2] ?- NEG memberEU(turkey).

Yes

 

Afterwards, if turkey becomes a member state of the European Union, the NEG
member(turkey) result will not be entailed (that’s life, knowledge changes…)

 

Notice that you cannot perform NAF queries directly. The example also helps
illustrating the differences between NAF and NEG, I believe.

Any of the adopted semantics for LP with two forms of negation (Answer Set
Semantics or Well-founded Semantics with Explicit Negation, paraconsistent
or not)

coincides in the above. It is also a property that for these semantics, the
conclusions extracted in the FORCE-OPEN are contained in the ones obtained
in ALLOW-CLOSED.

 

Sorry for the long message, but I think this might help the discussion.

 

Best regards,

 

Carlos Viegas Damásio

 

----------------------------------------------------------------------------
-------------------------------

Carlos Viegas Damásio (Prof. Auxiliar) | Tel: +351-21-294 8536 (ext.10758)

Departamento de Informática            | Fax: +351-21-294 8541

Fac. de Ciências e Tecnologia da       |

Universidade Nova de Lisboa            | 

Qta. da Torre - 2829-516 Caparica      | e-mail: cd@di.fct.unl.pt

PORTUGAL                               | http://centria.di.fct.unl.pt/~cd

 

 

 

 
Received on Monday, 29 August 2005 12:49:43 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:16:23 GMT