Production Systems with Negation as Failure.
We study action rule-based systems with two forms of negation, namely classical negation and negation as failure to find a course of actions. We show by several examples that adding negation as failure to such systems increases their expressiveness in the sense that real life problems can be represented in a natural and simple way. Then, we address the problem of providing a formal declarative semantics to these extended systems by adopting an argumentation-based approach which has been shown to be a simple unifying framework for understanding the declarative semantics of various nonmonotonic formalisms. In this way, we naturally define the grounded (well-founded), stable, and preferred semantics for production systems with negation as failure. Next, we characterize the class of stratified production systems, which enjoy the properties that the above mentioned semantics coincide and that negation as failure to find a course of actions can be computed by a simple bottom-up operator. Stratified production systems can be implemented on top of conventional production systems in two ways. The first way corresponds to the understanding of stratification as a form of priority assignment between rules. We show that this implementation, though sound, is not complete in the general case. Hence, we propose a second implementation by means of an algorithm which transforms a finite stratified production system into a classical one. This is a sound and complete implementation, though computationally hard, as shown in the paper.
This is a sound and complete implementation, though computationally
hard as shown in the paper.
Keywords: rule-based systems, knowledge-based systems, rule-based process-
ing, expert systems, knowledge representation
Note: This paper is a revised and extended version of [9].
1 Introduction and Motivations
In this section we rst give examples to motivate the extension of the production
systems paradigm [17] by the introduction of negation as failure (to nd a course
of actions). We then discuss its role as a specication mechanism for reactive
systems.
1.1 On the need for negation as failure in production systems
Example 1.1
Imagine the situation of a person doing his household work. Clothes have to
be washed and the person has two options, either hand washing or machine
washing. If there is machine powder in house, then machine washing can take
place. This is represented by the production rule
If no machine powder is in house, then it can be acquired by either buying it
in the shop (provided the shops are open) or by borrowing it from the neighbor
(if he is in). The rules for acquiring powder can be represented by the following
two classical production rules
Neighbor-In then borrow.
Of course, hand washing is undesirable and will be taken up if there is no way
to acquire machine powder . The naive representation of this rule using classical
negation
is clearly not correct, since the meaning of such a rule is that if there is no
machine powder in house at the current state, then the clothes should be hand
washed, while the intuitive meaning of \there is no way to acquire machine pow-
der" is that there is no course of actions starting from the current state leading
to acquiring machine powder. Hence in a state where there is no machine powder
in house and the neighbor is in, the above naive representation would allow
hand washing though there is a way to acquire machine powder by borrowing
it from the neighbor. Hence it fails to capture the intuitive understanding of
the problem.
Here we need to use a dierent kind of negation, called negation as failure
(to nd a course of actions) and denoted by the operator not . The previous
naive representation is now replaced by
not Powder then hand-wash.
Clearly, there are other ways of representing this situation which do not use
negation as failure at all, as we will see in the next Section. We will argue,
however, that the representation using negation as failure provides a better
specication for the problem at hand. 2
It is not di-cult to nd other real life situations governed by rules with negation
as failure.
Example 1.2
Consider the rules for reviewing the work of faculties at the end of each academic
year in a university. The rst rule species the conditions for oering tenure to
assistant professors. It states that assistant professors with good publications
and with a working experience of at least ve years should be oered tenure.
This rule could be formalized by:
if Assistant-Prof(X), Good-Pub(X), Work-at-least-5(X) then oer-tenure(X).
The second rule states that if an assistant professor has no prospect of getting
a tenure then re him. Though the intuitive meaning of this rule is clear, it
is not possible to represent it as a classical production rule since the premises
of a classical production rule represent conditions which must be satised in
the current state of the world while the premises of the second rule represent a
projection into the future. It says that if there is no possibility for an assistant
professor to get a tenure in the future then sack him now. In other words, the
rule says that if an assistant will fail in all possible course of actions in the future
to get a tenure then re him. To represent this rule, we use again negation as
failure to nd a course of actions. The second rule can then be represented as
follows:
if Assistant-Prof(X), not Getting-Tenure(X) then re(X) 2
In real life, we often nd ourselves in situations where we have to deal with risky
or undesirable actions. For example, a doctor may have to take the decision of
cutting the foot of his patient due to some severe frostbite. This is a very risky,
undesirable decision and the common-sense rule specifying the conditions for
taking this action is that the doctor is allowed to cut if there is no other way to
save the foot of the patient. This can be represented, using negation as failure,
as follows:
if not Save then cut.
Finally, we can expect that in real life, intelligent systems could be employed
to satisfy multiple goals. These goals can have dierent priorities, and negation
as failure (to nd a course of actions) can be used to represent these priorities
as in the following example.
Example 1.3
Consider a robot re ghter that should be sent into a re to save lives and
properties. The priority here is certainly saving lives rst. Imagine now that
the robot is standing before a valuable artifact. Should it take it and get out
of the re? The answer should be yes only if the robot is certain that there is
nothing it can do to save any life. The rule can be represented as follows
if Artifact(X), In-Danger(X), not Human-Found then save(X)
Note that the not Human-Found here means that no human being could be
found in the current and all other possible states of the world reachable by
ring a sequence of actions the robot is enabled to perform. 2
1.2 Negation as failure as a specication mechanism for reactive
systems
Let us consider again the example 1.1. Checking whether the conditions of the
rule
not Powder then hand-wash
are satised in the current state involves checking whether there is any way to
acquire machine powder from the current state, a process which could be time
consuming and expensive. In a concrete application, as in our example where
there are only two ways to get powder: buying it in the shop or borrowing it
from the neighbor, negation as failure can be \compiled" into classical negation
to produce a more e-cient rule:
Neighbor-In then hand-wash.
However, the environment in which a production system with the above rule is
applied can change. For example, you may get a new neighbor who may not
have any interest for good relations to other peoples, and so you will not be able
to borrow anything from him. Hence the rule for borrowing must be dropped.
Consequently the above production rule must be revised to
It is clear that the rule r 4 with negation as failure is still correct and serves as
a specication for checking the correctness of the new rule.
The point we want to make here is that in many cases, though negation as
failure is not employed directly, it could be used as a specication mechanism for
a classical production system. This situation can be encountered quite often in
many real life situations. Imagine the work of a physician in an emergency case
dealing with a patient who is severely injured in a road accident. In such cases,
where time is crucial, what a doctor would do is to follow certain treatments
he has been taught to apply in such situations. He more or less simply react
depending on the physical conditions of the patient. The treatment may even
suggest a fateful decision to operate the patient to cut some of his organs.
Now it is clear that such treatment changes according to the progress of the
medical science. One treatment which was correct yesterday may be wrong
today. So what decides the correctness of such treatments? We can think of
such treatments in a simplied way as a set of production rules telling the
doctors what to do in a concrete state of a patient. The correctness of such
rules are determined by such common-sense principles like: Operate and cut an
organ only if there is no other way to save the patient. And such a principle
can be expressed using negation as failure.
As we already pointed out, negation as failure can be seen as a mechanism to
specify priorities between dierent goals. For example, in the robot reghter
example 1.3, negation as failure is used to give the goal of saving humans a
higher priority than the goal of saving artifacts.
Explicit priorities between rules is often used in production systems and active
database systems [2, 16, 11] to in
uence the way rules are executed. In such
systems, whenever dierent rules can be triggered in a state, the rules which
have higher priority are triggered rst. Clearly, the notion of priority that
negation as failure induces, is dierent from the one used in classical production
and active database systems, as the former has to do with goals whether the
latter has to do with rules which are employed to implement goals. Moreover,
it is often di-cult to understand declaratively why a rule should have higher
priority than another rule. We believe that in many cases negation as failure
can be used as a high-level tool to specify the (implicit) priority between goals
which could then be implemented by dening explicit priorities between rules.
1.3 Aim of this work
We have seen in the examples that using negation as failure in production
systems allows one to naturally and correctly represent many real life problems.
The main aim of this paper, which is an extended and revised version of [9],
is to provide a declarative semantics to production systems where two kinds of
negation are used, classical negation and negation as failure (to nd a course
of actions). In this respect, we show that the argumentation based approach
[8], which has been successfully adopted to understand logic programming with
negation as failure as well as many other non-monotonic formalisms, can also
be adopted to provide a natural and simple declarative semantics to production
systems with two kind of negations. The basic idea is that negation as failure
literals, such as \not Powder" in example 1.1, represent assumptions underlying
potential computations of a production system. The intuitive meaning of such
an assumption is that the computation goes on by assuming that there is no
course of actions (i.e. computation) from the current state of the world leading
to a state which defeats the assumption itself. Referring back to example 1.1,
assuming not Powder corresponds to assuming that from the current state there
is no course of actions leading to a state where machine powder is in house.
A computation which is supported by a sequence of assumptions is plausible
(acceptable) if its underlying assumptions cannot be defeated by actually nd
a course of actions which defeats them.
These informal, intuitive notions can be formalized by viewing a production
system as an argumentation system along the lines of [8]. This provides us with
many natural semantics, such as the grounded (well-founded), the preferred
and the stable semantics [8]. These semantics are arguably the most popular
and widely accepted semantics for non-monotonic and common-sense reasoning
in the literature [15, 4, 19, 27].
Moreover, we address the problem of actually computing negation as failure.
In this respect, we introduce the class of stratied production systems, where
negation as failure can be computed using a simple bottom-up operator. As for
the case of general stratied argumentation systems, stratied production systems
enjoy the property that all the previously mentioned semantics (grounded,
preferred and stable) coincide.
We show that classical production systems with explicit priorities between rules
can be used to obtain a straightforward sound implementation of stratied production
systems with negation as failure. We will also show that a complete
implementation requires a more sophisticated method of compiling away negation
as failure even for the class if stratied production systems. This method
yields a classical production systems, but its complexity, in the worst case, is
not polynomial in the number of atoms occurring in the production system.
The rest of the paper is structured as follows. In Section 2 we introduce the
basic notations and terminologies we use for classical production rule systems.
In Section 3 we extend production systems to general production systems where
negation as failure can be used in the condition part of the rules, and we provide
them with an argumentation based semantics (argumentation systems are
brie
y reviewed in section 3.1). In Section 4 we address the problem of computing
with negation as failure and introduce the class of stratied production
systems, the semantics of which can be characterized by a simple bottom-up
operator. In Section 5 we discuss two ways of implementing stratied production
systems, along the lines mentioned above. Finally, in Section 6 we address
some open issues and future work.
Preliminaries: Classical production rule systems
We introduce here the notations and basic terminologies we are going to use in
the following. The production systems language we use is similar to classical
ones (see, e.g. [12]). We assume a rst order language L representing the ontology
used to describe the domain of interest. A state of the world is interpreted
as a snapshot of this world, hence is represented as a Herbrand interpretation
of L, i.e. as a set of ground atoms of L. The set of states is denoted by Stat .
Further we assume that a set of primitive actions A is given. The semantics
(eect) of actions is described by the function
eect
A production rule is a rule of the form
are ground literals of L and a is an action in A. The conditions
(resp. action) of a rule r will be referred to by cond (r) (resp. action(r)). A
production system P is a set of production rules.
A production rule if l then a is said to be applicable in a state S i
the conditions l are true in S, i.e. S
Denition 2.1 (Computations)
A computation C of a production system P is a sequence
0, such that S i 's are states, r i 's are production rules in P and for each
applicable in S i 1 , and S will be
referred to as initial(C) and S n as nal (C). 2
Note that, if then the computation is an empty computation.
Denition 2.2 (Complete Computations)
A computation C
is called a complete computation if there is no production rule in P which is
applicable in S n . 2
The behavior of a production system P can be dened as the set of pairs of
states is the initial (resp. nal) state of some
complete computation of P . This is formalized in the next denition.
Denition 2.3 (Input-Output semantics)
For a production system P , the input-output semantics of P is dened by
nal (C)) j C is a complete computation of Pg: 2
Even though we have considered only ground production rules, our approach can
be easily adopted for production systems in which rules may contain variables.
Given such a collection of rules, we consider all their possible ground instances,
obtained by replacing the variables occurring in them by any ground term. This
approach is usually adopted in the study of the semantics of logic programming
[15, 27, 7].
It is worth noting that the above semantics re
ects the inherent nondeterministic
nature of production systems. It is indeed natural to expect that from an
initial state S there may exist many dierent computations leading to possibly
dierent nal states. This means that, for a given S, there might be many different
pairs in the IO semantics. This nondeterminism arises naturally
in the representation of real life problems through production rules. Referring
back to example 1.1 if both the shops are open and the neighbor is in there
are two possible ways of acquiring machine powder, which are both plausible,
i.e. buying it from the shop or borrowing it from the neighbor. Clearly the
corresponding computations of the production system are both plausible and
there is no intuitive reason to prefer one to the other.
The need for nondeterministic rule based languages has been pointed out by
many authors (see, e.g. [1]). Indeed, nondeterministic rule based languages have
been mainly studied with respect to their expressive power and computational
complexity as opposed to purely deterministic languages. In this paper, we
argue that nondeterminism is needed to naturally represent real life problems.
Some work in the literature (see, e.g. [13, 24]) has also been devoted to dene
(operational) semantics for classical production systems, in such a way that
nondeterminism is avoided by adopting an ad hoc computational mechanism
which (either implicitly or explicitly) assigns a sort of priority to the production
rules which can be red in the same state. But the lack of an intuitive
motivation makes a full understanding of their technical results di-cult.
3 Production rules with NAF
We introduce a new form of negation into the language L, denoted by not. A
general literal is now either a (classical) literal l or a naf-literal not l, where l
is a classical literal. For each classical literal l, the intuition of not l is that it
is not possible to nd a course of actions to achieve l.
Denition 3.1 (General production rules)
A general production rule has the form
where each l i is a ground general literal. 2
Given a general production rule
the set of classical literals in r will be referred to as cl-cond (r), and the set of
naf-literals will be referred to as hyp(r).
A general production system (GPS) P is a set of general production rules.
A general production rule is possibly applicable in a state S if S
Denition 3.2 (Possible Computations)
Given a GPS P , a possible computation in P is a sequence
are states, r i 's are general production rules in P , for each i  1, r i
is possibly applicable in S i 1 and S
We denote by C(P ) the set of all possible computations of a GPS P . 2
Given a possible computation as above, the sequence hhyp(r 1
referred to as the sequence of hypotheses underlying the computation. The
basic idea in understanding the meaning of naf-conditions not l's in general
production rules is to view them as hypotheses which can be assumed if there
is no possible course of actions to achieve l. So, intuitively we can say that a rule
is applicable in a state S if it is possibly applicable and each of its hypotheses
could be assumed. A computation is then an acceptable computation if each of
its rules is applicable. The whole problem here is to understand formally what
does it mean that there is no possible course of actions starting from a state S
to achieve some result l.
Let us consider again the example 1.1.
1 Notice that a rule satisfying the condition that S j= cl-cond(r) in a state S is not necessarily
applicable in S since it is not clear whether its naf-conditions are satised in S.
Example 3.3
Let us rst recall the production rules:
not Machine-Powder then hand-wash
Neighbor-In then borrow-powder
The eects of the actions are specied below:
eect(hand-wash,
eect(buy-powder,
eect(borrow-powder,
Assume that in the initial state we have no powder, shops are closed and the
neighbor is in. This state is represented by the interpretation S
From this state there are three possible nonempty computations starting from
namely
r 4
fNeighbor-In, Machine-Powder, Clothes-Cleang.
r 4
First, notice that both C 2 and C 3 are not based on any assumption. Our
common-sense dictate that C 2 and C 3 represent acceptable course of actions
from the initial state which lead to the common-sense result that clothes are
machine washed. Hence they both must be accepted as possible courses of ac-
tions. On the other hand C 1 is based on the assumption \not Machine-Powder",
meaning that C 1 assumes that there is no possible way to acquire the machine
powder. However, C 3 represents just one such possible way. Hence, C 3 represents
an attack against the assumption \not Machine-Powder". So C 3 can also
be viewed as an attack against the acceptability of C 1 as a legitimate compu-
tation. On the other hand, both C 2 and C 3 are not based on any assumption,
hence there is no way they can be attacked. 2
This example points out that the semantics of GPS's is a form of argumentation
reasoning, where arguments are represented by possible computations. In the
following, we rst recall the general notion of argumentation systems from [8]
and then we show that the natural semantics of GPS can be dened using the
theory of argumentation.
3.1 Argumentation systems
Argumentation has been recognized lately as an important and natural approach
to nonmonotonic reasoning [5, 14, 18, 21, 22, 23, 26, 28]. It has been
shown [8] that many major nonmonotonic logics [20, 19, 25] represent in fact
dierent forms of a simple system of argumentation reasoning. Based on the
results in [8], a simple logic-based argumentation system has been developed
in [4] which captures well known nonmonotonic logics like autoepistemic logics,
Reiter's default logics and logic programming as special cases. In [14], argumentation
has been employed to give a proof procedure for conditional logics.
Argumentation has also been applied to give an elegant semantics for reasoning
with specicity in [10].
We review here the basic notions and denitions of argumentation systems
(the reader can refer to [8] for more details and for a discussion of the role of
argumentation systems in many elds of Articial Intelligence).
An argumentation system is a pair hAR; attacksi where AR is the set of all
possible arguments and attacks  ARAR, representing the attack relationship
between arguments. If the pair (A; B) 2 attacks , then we say that A attacks B
or B is attacked by A. Moreover, A attacks a set of arguments H if A attacks
an argument B 2 H.
set H of arguments is con
ict-free if no argument in H attacks H.
An argument A is defended by a set of arguments H if H attacks any attack
against A. We also say that H defends A if A is defended by H.
The basic notion which underlies all the semantics for argumentation systems
that we are going to review in the rest of this section, is the following, intuitive
notion of acceptability of a set of arguments. A set H of arguments is acceptable
if it is con
ict-free and it can defend each argument in it.
Let H be a set of arguments and let Def (H) be the set of all arguments which
are defended by H. It is not di-cult to see that H is acceptable i H
and H is con
ict-free. Further it is easy to see that
is monotonic. Hence the equation has a least solution which is
also acceptable (following from the fact that Def (;) is acceptable and if H is
acceptable then also H [
The various semantics for argumentation systems are basically solutions of
the above equation In particular, the grounded (well-founded)
semantics of an argumentation system is the least solution of the equation
Another semantics for argumentation systems, called the preferred semantics,
is dened by the maximal acceptable sets of arguments. It is not di-cult
to see that these sets are the maximal con
ict-free solutions of the equation
In general, preferred sets contain the grounded semantics, but
do not coincide with it. In the next section, we will give an example for this.
Finally, a popular semantics of non-monotonic reasoning and argumentation
systems is the stable semantics, dened as follows. A con
ict-free set of arguments
H is said to be stable if it attacks each argument not belonging to it. It is
not di-cult to see that each stable set of arguments is acceptable. Furthermore,
it is also easy to see that each stable set is preferred, hence it is a maximal,
con
ict-free solution of the equation but not vice versa.
In [8] it has been shown that logic programming with negation as failure can
be seen as a form of argumentation systems. In this view, the various semantics
of argumentation systems presented above capture in a unifying framework
various well-known semantics for logic programming with negation as failure.
For instance, the grounded semantics corresponds to the well-founded semantics
in logic programming [27] and the stable semantics corresponds to stable
semantics of logic programming [15].
In the following we show that general production systems with two kinds of
negation are also a form of argumentation systems. A philosophical explanation
of this result can be seen in the fact that the computations of production systems
represent also a form of common-sense reasoning.
3.2 Computations as arguments
The semantics of a GPS P is dened by viewing it as an argumentation frame-work
is the set of all possible computations of
P and the relation attacks is dened as follows.
Denition 3.4 (Attacks)
Let C be a possible computation
An attack against C is a possible computation C 0 such that initial(C 0
for some i, and there exists an underlying assumption not l in hyp(r i+1 ) such
that l holds in nal(C 0 ). 2
Remark 3.5 Empty computations cannot be attacked. Hence, empty computations
are contained in any semantics. 2
Notice that, in the above denition, the initial state of the attack C 0 , which
defeats the assumption not l underlying C, has to be the actual state S i in which
such an assumption was made. In other words, whether an assumption not l
can be defeated or not, depends on the state in which this assumption is made
and on whether or not this state can lead by a computation to a state in which
l holds. Referring back to example 3.3, it is easy to see that C 3 attacks C 1 , by
defeating the assumption \not Machine-Powder" on which C 1 is based. This is
because such an assumption is made in the state S 0 and C 3 shows an alternative
course of actions leading S 0 to a state where Machine-Powder actually holds.
Consider now an initial state S 0
among others, the fact that
there is no machine powder in house, shops are closed and the neighbor is not
in. It is clear that there is only one possible computation (apart from the empty
one) leading S 0
0 to the nal state fClothes-Cleang. This state represents the
fact that clothes have been hand washed. This computation is also based on
the assumption \not Machine-Powder" which is made in the state S 0
0 and hence
cannot be defeated (the powder cannot be bought since shops are closed neither
it can be borrowed since the neighbor is not in).
The view of a GPS as an argumentation system, allows us to provide it with
three dierent semantics: grounded (well-founded), preferred and stable se-
mantics. Recall that, given a set H of arguments (i.e. possible computations),
(H) is the set of all arguments which are defended by H (see Section 3.1).
Denition 3.6 Let P be a GPS and K be a set of possible computations.
Then:
K is grounded if K is the least solution of the equation
K is preferred if K is a maximal con
ict-free solution of the equation
K is stable if K is con
ict-free and it attacks every possible computation
not in K.Let us elaborate in detail the example 3.3 to compute its grounded semantics.
Example 3.7
We compute the grounded semantics by using the We use the
following abbreviations: MP for Machine-Powder, NI for Neighbor-In, CC for
Clothes-Clean, SO for Shop-Open, hw for the action hand-wash, mw for the
action machine-wash, bp for the action Buy-Powder and bop for the action
borrow-powder. Hence the rules of example 3.3 become:
not MP then hw
As mentioned in the previous section, the grounded semantics is the least solution
of the equation be the empty set of arguments
(computations). contains all the computations which
can never be attacked (H 0 cannot defend any computation). These are clearly
all the empty computations and all the non-empty computations which are not
based on any assumptions. Let S so be any state such that S so
S so . Then the following computations
S so
S so
belong to H 1 , since both hyp(r 3 ) and hyp(r 2 ) are empty. Similarly, let S ni be any
state such that S ni . Then the following computations
r 4
belong to H 1 . Let us move now to H
us consider now the possible computations with some underlying assumptions.
All such computations must use rule r 1 , which is the only rule containing a
naf-literal in its premises. Let S 1 be any state such that S 1 Consider
then a computation C of the form
which is based on the assumption not MP . Now, if S 1 there is
a computation of the form (a) above, which attacks this computation (since it
leads to a nal state where MP holds) and belongs to H 1 . Since H 1 is con
ict-
defend the computation C. Similarly, if S 1
cannot defend C. So, we conclude that the only computations in H 2 n H 1 are
the computations of the form (e) such that S 1
It is easy to see that H 2 is indeed a solution, hence the least solution, of the
equation this case. Moreover it is not di-cult to see that, in
this example, the grounded, preferred and stable semantics coincide, and hence
H 2 is also stable and preferred. This is also a consequence of the fact that this
production system is stratied in the sense of section 4, and we will show that
for stratied production systems all dierent semantics coincide. 2
It is easy to see that the following propositions hold.
Proposition 3.8
If a computation C attacks a computation C 0 and C 0 is a prex of C 00 , then C
also attacks C 00 . 2
Proposition 3.9
Let H be a set of computations which is either the grounded, or a preferred, or
a stable set. For any C 2 H, any prex of C also belongs to H. 2
We give now some examples of general production systems, where the grounded,
preferred and stable semantics do not coincide.
Example 3.10
Let P 0 be the following GPS:
where the eect of assert(p) on a state S is adding p to S. Let S It is
easy to see that the nonempty possible computations starting from S 0 are:
fbg with underlying assumptions hfnot agi
underlying assumptions hfnot ag; fnot bgi
fag with underlying assumptions hfnot bgi
underlying assumptions hfnot bg; fnot agi
The empty computation starting from fbg attacks C 0
1 and the empty computation
starting from fag attacks C 0
2 . On the other hand, an empty computation
cannot be attacked. Hence, C 0
2 are not contained in any acceptable
set of computations. Furthermore, it is also clear that C 2 attacks C 1 , since
C 1 is based on the assumption not a, meaning that there is no way to achieve
a starting from S 0 . For similar reasons, C 1 also attacks C 2 . Hence, the only
computation starting from S 0 which is contained in the grounded semantics is
the empty computation.
But there are two stable sets of computations, one containing C 2 and the other
containing C 1 . This is because C 1 (resp. C 2 ) can defend itself against all
attacks. In this example preferred and stable semantics coincide.
Notice that rules similar to r 1 and r 2 may be needed to represent real world
situations. Imagine the situation of a team leader who needs to hire a person for
an important position and he has two applications for it, say Mary and Ann.
The leader asks his advisors to express their opinion. The rst advisor likes
Ann, hence he says: \if there is no way you can hire Ann, then hire Mary".
This can be expressed by the rule
Mary hired, not Ann hired then Hire(Mary)
Notice that using negation as failure we capture here the intuition that there is
no possible course of actions to hire Ann. Imagine now that the second advisor
has exactly the opposite view, i.e. his opinion can be expressed as:
Mary hired then Hire(Ann)
The team leader reasoning is represented by two computations which corresponds
to computations C 1 and C 2 above. 2
The next example shows that preferred sets may not be stable.
Example 3.11
Let P 1 be the following general production system.
The intuition of this rule is that if a is not true in the current state and there
is no way to achieve a, then add it to the state. This is clearly a paradox, since
if there is no way to achieve a then the rule itself allows to achieve it. The only
nonempty possible computation starting from S
fag.
It is clear that C attacks itself. Hence, in this example the grounded and
the preferred semantics coincide, and contain only the empty computations.
Clearly, there is no stable set of computations. 2
We can now dene the set of complete acceptable computations, with respect
to a selected semantics.
Denition 3.12 (Complete Computations)
Let P be a GPS and Sem be a selected semantics of P , i.e. Sem is either
the grounded, or a preferred, or a stable, set of possible computations. A
computation C 2 Sem is called a Sem-complete computation if there exists no
other computation C 0 2 Sem such that C is a prex of C 0 . 2
If all the semantics of a GPS coincide, we simply talk about complete computations
instead of Sem-complete computations. Referring back to the example
3.3, the only complete computation starting from S 0 is C 2 .
The input-output semantics of classical production systems can be extended
to general production systems with respect to a selected (grounded, preferred,
stable) semantics.
Denition 3.13 (Input-Output semantics for GPS)
Let P be a GPS.
The grounded input-output semantics of P is dened by
nal (C)) j C is a grounded complete computationg
Let Sem be a set of arguments which is preferred or stable. Then
IO Sem (P nal (C)) j C is a Sem-complete computation
of P g4 Stratied Production Systems
In this section we consider only special kinds of GPS, where the actions are
of two types, assert(p) and retract(p), where p is an atom. The eect of
assert(p) (resp. retract(p)) on a state S is adding (resp. removing) p to S
(resp. from S). Moreover, the rules have the following structure:
where l i 's are classical literals. Rules of the rst kind are called assert rules,
and rules of the second kind are called retract rules. If it is not important to
distinguish between assert and retract rules, we will simply write a rule as
Further, we dene stratied GPS's in such a way that negation as failure can
be computed bottom-up.
In the following, given a classical literal l, we refer to the atom of l as l if it is
a positive atom, and as p if l is :p.
Denition 4.1 (Stratied Production Systems)
A GPS P is stratied if there exists a partition of its rules such
that the following conditions are satised. Let
be a rule in P j . Then
(i) for each l i , each rule containing the atom of l i in the head
must belong to S
Pm
(ii) for each l i , h, each rule containing the atom of l i in the
head must belong to S
Pm .It is worth noting that the intuition underlying the above denition of stratied
GPS's is similar to the one underlying the denition of stratication in logic
programming [3].
For stratied GPS's, the grounded, preferred and stable semantics coincide (see
theorem 4.3). Moreover, this semantics can be computed in a bottom-up way,
by a simple operator S, that we are going to dene next.
Let C be a possible computation
Then for any h; k such that 0  h < k  n, the sequence
is called a subcomputation of C. Further, we denote by rules(C) the sequence
Denition 4.2 Let be a stratied GPS. Let S be the operator
dened as follows.
{ for each subcomputation C 0 of C if C
{ for each subcomputation of C of the form S
for each not l 2 hyp(r j ), there is no computation
lgRoughly speaking, the operator S formalizes the intuition that the acceptability
of a possible computation using rules in P depends only on
computations in P Thus, the semantics of a stratied GPS P can
be computed bottom-up by iterating the operator S on the strata of P .
Theorem 4.3
Let P be a stratied GPS. Then:
is the unique preferred set of computations
is the unique stable set of computationsProof. : See appendix.
Implementing Stratied PS
In this section we address the issue of implementing stratied PS by translating
stratied PS into classical PS. From now on, we restrict ourselves to production
systems where the collection of (the ground instances) of rules is nite.
Let us rst introduce the notion of implementation of a production system. Let
be two production systems. We say that P 0 is a sound implementation
of P if the following two conditions hold:
(i) for each computation C 0 of P 0 there exists a computation C of P such
that nal (C).
(ii) for each complete computation C 0 of P 0 there exists a complete computation
C of P such that initial(C 0
If P 0 is a sound implementation of P , we say it is also complete if the reverse
of conditions (i) and (ii) above hold, namely:
for each computation C of P there exists a computation C 0 of P 0 such
that
for each complete computation C of P there exists a complete computation
C 0 of P 0 such that
In the next section we introduce the class of prioritized production systems PPS
where rules can have dierent priorities, and dene accordingly a suitable notion
of computation. We show that viewing stratication as a priority assignment
to rules (the lower the stratum, the higher the priority), yields a sound implementation
of a stratied GPS through PPS. However, we will see by means of a
simple example that this implementations is not complete in the general case.
This means that the priorities induced by stratication are not powerful enough
to completely capture the implicit priorities induced by the negation as failure
mechanism. In order to obtain a sound and complete implementation, we need
a more sophisticated method which compiles away negation as failure from a
stratied GPS and yields a classical production system with no priorities at
all. We show that the classical PS obtained by this transformation is indeed a
sound and complete implementation of the original stratied PS. However, the
transformation, in the worst case, is not polynomial in the number of atoms of
the production system.
5.1 Implementing negation as failure with priorities
Let us introduce the class of PPS, namely classical production systems where
rules can be assigned dierent priorities. This type of systems have been extensively
studied in the literature [11].
Denition 5.1 A prioritized production system (PPS) is a pair hP; i where
P is a classical PS and  is a partial order relation between rules 2 . 2
2 a partial order is a irre
exive, transitive and asymmetric relation
In the sequel, if r  r 0 , we will say that r has higher priority than r 0 . Notice
that a classical PS is a PPS with  being the empty relation.
The priority relation between rules aects the applicability of rules.
Denition 5.2 Let hP; i be a PPS. A production rule if l then a is
applicable in a state S i S there is no rule r 0  r such that
r 0 is applicable in S. 2
The notion of computations in PPS is the same as the one given in Denition 2.1,
provided that applicability of rules is understood as in the previous denition.
Example 5.3 Let us formulate the washing machine example 3.3 as a PPS.
Let us rst recall the production rules:
Neighbor-In then borrow-powder
Notice that negation as failure in the rst rule has been replaced by classical
negation. To correctly represent the fact that hand washing has lower priority
than machine washing we can add the following priority relation between rules.
In this way, rule r 1 cannot be applied in states where there is no machine powder
but either the shops are open or the neighbor is in, thus achieving the desired
behavior. 2
now P be a stratied GPS. The idea is to view stratication as an implicit
assignment of priorities between rules: making this assignment explicit, allows
us to get rid of negation as failure and translate it directly into classical negation.
We need rst to introduce some useful notations.
Let l be a naf literal. Then we denote by l  the classical literal
:a, if l = not a
a, if l = not :a
Moreover, given a general production rule r, we denote by r  the rule obtained
from it by replacing each naf-literal l by l  .
Denition 5.4 Let be a stratied GPS. Its prioritized
is the PPS obtained by replacing each rule r of P by r  and by
dening  as follows:
The following theorem shows that, given a stratied GPS P , hP  ; i is a sound
implementation of it.
Theorem 5.5 Let P be a stratied GPS and hP  ; i its prioritized form. Then
is a sound implementation of P , i.e.
(i) for each computation C in hP  ; i there exists a computation C 0 in P
such that
(ii) for each complete computation C in hP  ; i there exists a complete computation
in P such that
nal (C
The following example shows that the implementation we have just given is not
complete in the general case.
Example 5.6 Consider the following
and its stratication g.
Consider the following complete computation
The prioritized form of P is given by the following PPS hP  ; i:
r
r
r
r
where  is dened by r
1 , for each 4. It is not di-cult to see that
there is no complete computation in hP  ; i starting from the empty state and
ending in the state fa; c; dg. This is due to the fact that r
3 and r
4 are both rule
with highest priority and then they are red before r
1 . Since the eect of r
4 is
adding fdg to the state, this will prevent r
1 from being applicable.
The point here is that the naf literal not b in r 1 induces a priority between
rules which is dierent from the naive one obtained by the given stratication.
Indeed, not b intuitively means that there is no way to achieve b and, given
a state where all classical conditions of r 1 are satised, this can be ensured
by enforcing c to be true, i.e. by making r 2 , the only rule for asserting b not
applicable. This can be obtained in two ways: either by enforcing the priority
r
1 or by transforming r 1 into the following classical rule
We thus need a deeper understanding of stratication, generalizing the intuition
sketched in the above example which allowed us to compile away negation as
failure in rule r 0
1 . In the next section we propose such a transformation, which,
given a stratied GPS P , yields a classical PS P 0 which is a sound and complete
implementation of P . However, in order to get a complete implementation we
have to pay a high price in terms of the complexity of the transformation, as
shown in Section 5.3.
5.2 Compiling away negation as failure
Let us rst introduce the notion of incomplete state and computations with
respect to incomplete states.
Denition 5.7 An incomplete state is a consistent set of ground literals of L.
A production rule if l then a is said to be applicable in an incomplete
state I i the conditions l are true in I, i.e. I
Often it is not necessary to have complete information about the state of the
world to carry out some computations. Indeed, if a computation relies only on
classical production rules, the following notion of computation, which we refer
to as partial computation, is su-cient.
Denition 5.8 (Partial Computation)
Let I be incomplete states, and r i 's be production rules in a
classical production system P . Then a sequence
I 0
is a partial computation C of P if for each i  1, r i is applicable in I i 1 , and
I i =<
I
I retract(p)Notice that a computation is also a partial computation. Moreover, any partial
computation C starting from an incomplete state I can be viewed as a collection
of all computations C 0 starting from a state S such that S j= I and
Denition 5.9 Let P be a classical PS, I be an incomplete state and l be a
ground literal. Then we say that l is achievable from I in P if there is a partial
computation C starting from I such that l 2 final(C). 2
Let us rst consider the problem of compiling away negation as failure for a
stratied PS with only two strata
Let r be a rule in P 1 of the following form
l 0
I n be the collection of all incomplete states such that, for each
are satised:
cl-cond (r) [ I i is consistent,
l 0 is achievable from I i in P 0
For each cl-cond (r). There are two cases here:
some J i is empty. This means that there exists a (classical) computation
in P 0 starting from cl-cond (r) and leading to a state in which l 0 holds.
Hence, the rule r can never be applied in any computation in S(P ) and
so it can be simply dropped;
no J i is empty.
Let R l 0 ;r be the empty set if one of the J i is empty. Otherwise, R l 0 ;r is the
following
R is minimalg
Notice that each non-empty J i is viewed as a conjunction of literals. Also, by
minimality, we mean that there exists no proper subset of R which implies :J i
for each
Each set R 2 R l 0 ;r is a set of conditions that, if satised by a state, make l 0 not
achievable from this state, and the set R l 0 ;r covers all such conditions. This is
formalized in the following lemma.
Lemma 5.10
Let S be a state such that S cl-cond (r). Then, S
if and only if there exists no computation C in C(P 0 ) such that
and final(C)
Proof. From the denition of R l 0 ;r it is clear that:
if and only if
for all I such that l 0 is achievable from I and I is consistent with cl-cond(r),
cl-cond (r)).
It is clear now that if the above condition is satised, then there is no computation
C in C(P 0 ) such that
Suppose now that there is no computation C in C(P 0 ) such that
and final(C) Assume now that there exists an incomplete state I such
that l 0 is achievable from I, I is consistent with cl-cond (r) and S 6j= :(I n
cl-cond (r)). From the assumption that S j= cl-cond(r), it follows that S
and hence there exists a computation C in C(P 0 ) such that
For each R 2 R l 0 ;r , we dene a new production rule r R as follows:
cl-cond (r R
hyp(r R
action(r R
We can now dene:
Example 5.11
The machine wash example 3.7 is translated into the following stratied PS.
g. Then, the set of all
incomplete states from which MP is achievable is:
Hence,
Hence, PMP ;r 1
consists only of the following rule:
production system clearly still stratied, and it is equivalent
to shown by the following results.
Lemma 5.12
only if there exists r ;r such that
Proof. Let us consider the following assertion:
(*) there is no computation C 2 S(P 0 ) such that
(*) holds
if and only if
for each consistent set I of literals such that l 0 is achievable
from I in P 0 , S
if and only if (from Lemma 5.10)
there exists R 2 R l 0 ;r such that S
By denition of the operator S:
if and only if
there is no computation C 2 S(P 0 ) such that
if and only if
(*) and 8l there is no computation C 2 S(P 0 )
such that
if and only if
there exists R 2 R l 0 ;r such that S
there is no computation
such that
if and only if
S r R
Theorem 5.13
r h
only if S 0
r
Proof. Obvious, by taking r 0
as in the above
The procedure of compiling away negation as failure from a two strata production
system then the following:
Step 1. Select r 2 P 1 and not l 2 hyp(r). If no such r exists then stop.
Step 2. if
then
else
Step 3. Goto Step 1.
The generalization of the above procedure for the general case of stratied
production systems with more than two strata is obvious.
We rst compile away naf from P 1 and obtain a stratied production system
with By continuing this process, we eventually obtain a classical
production system.
Coming back to Example 5.11, the result of applying the above transformation
is the classical PS consisting of the rules in the original P 0
together with the new rule
It should be obvious that the new production system is equivalent to the original
one.
In the above procedure, we assume that P l;r is given. We dene now a method
to compute it.
Denition 5.14 A set fI of incomplete states is called a base for l
with respect to P 0 if the following conditions hold:
l is achievable from each I i in P
for any incomplete state I such that l is achievable from I in P 0 , I  I i ,
for some each r 2 P 1 and l 2 hyp(r), it is easy to see that the following lemma holds.
Lemma 5.15
I n be a base for l with respect to P 0 , and J
for each Suppose that no J i is empty. Then
R is
Constructing P l;r consists of computing a base for l with respect to P 0 and
computing R l;r . The set R l;r can be computed from a base by applying standard
methods in propositional logic for computing disjunctive normal forms. In
the following we give an algorithm for computing a base for l. We do so by
constructing a tree satisfying the following properties:
Each node N of the tree is labeled with an incomplete state label(N ).
The root of the tree is labeled with the set flg.
Each link is labeled by a rule r
For any node M , a node N is a child of M with a link labeled by a rule
has no ancestor with the same label, label(N) is consistent,
and
{ if action(r 0
label(M)
{ if
f:pg.
It is clear from the above construction that if a node N has some ancestor with
the same label then N is a leaf node. Hence, since P 0 is nite, the tree is also
nite. Further, it should be clear from the construction of the tree that for
each there is exactly one tree satisfying the above conditions. Let
us refer to this tree as T P 0 ;l .
As an example, consider the production system of Example 5.11. Then T
is the following tree.
fMPg
f: MP, SOg f: MP, NIg
@
@
@
@ @
Theorem 5.16
is a node in T P 0 ;l g is a base for l with respect to P 0 . 2
Proof. See appendix.
5.3 Complexity of the transformation
In this section we show that compiling away NAF is, in general, not polynomial
in the number of atoms of the production system. The method we have given
to compile away a naf literal not l occurring in a rule r basically consists of
computing a base for l and then computing the set R l;r . The set R l;r can be
computed from a base by applying standard methods in propositional logic for
computing disjunctive normal forms. We show next that computing the set
R l;r is not polynomial by taking into account a restricted class of stratied
production systems.
First of all we will consider in the sequel classical production systems where
each rule has the following structure:
where b; a are all positive atoms. In the sequel a rule of this form is
referred to as a rule for b. Given two atoms a; b we say that a is a successor of
b, denoted by a < b if a occurs in the body of a rule for b. A production system
is acyclic if the relation < is well founded, i.e. each decreasing sequence of the
is nite.
Give an acyclic production system, we dene the rank of an atom a, denoted
by kak, as follows:
ag
Let now be a stratied production system where:
contains exactly one rule
r: :p; not l ! assert(p)
P 0 is a classical production system satisfying the following conditions:
(c2) each rule in P 0 has the following structure:
(c3) each atom either appears in the head of exactly two rules or it appears
in the head of no rule
a positive atom either occurs in the body of exactly one rule or it
does not occur in the body of any rule
for each atom a, either
for each atom a there exists a decreasing sequence
where l is the atom occurring in the naf literal of rule r .
Notice that condition (c5) implies that for any atoms a; b; c, if both b < a and
c < a then also that each atom has either no successors or
exactly four successors due to conditions (c2) and (c3) above.
We want to show that the number of rules obtained by compiling away the
naf literal from rule r is not polynomial in the number of atoms of P 0 . This
amounts at proving that the cardinality of the set R l;r is not polynomial in
the number of atoms of P 0 . Recall that the set R l;r can be computed from a
base for l by applying standard methods in propositional logic for computing
disjunctive normal forms.
Let a be an atom and be a partial state satisfying the following conditions:
(i) a is not achievable from any state satisfying
(ii) is minimal, i.e. no proper subset of it satises (i)
Let also R a be the set of partial states satisfying conditions (i) and (ii) above.
Then obviously R l;r l . In the sequel we show that the cardinality of R l is
not polynomial in the number of atoms of P 0 .
First of all, let us generalize the above denition of R l to a conjunction of
atoms. Given a conjunction a is the set of all partial states
satisfying the following conditions:
is not achievable from any state satisfying
(iv) is minimal, i.e. no proper subset of it satises (iii)
Consider now a conjunction of distinct atoms a such that ka 1
let be a partial state in R a1 ;:::;a n . By the syntactic restrictions on
is clear that 2 R a i for some a i . Moreover it is clear that R a i and R a j ,
with i 6= j, are disjoint sets.
For be the cardinality of R a i . By the previous observations,
it is clear that the cardinality of R
Consider now an atom b such that kbk > 0. Then P 0 contains exactly two rules
for b,
Consider a partial state 2 R b . By the syntactic restrictions on P 0 and the
minimality of , it is clear that can be split into two disjoint sets 0 and 00
such that 0 2 R a 1 ;a 2
and 00 2 R a 3 ;a 4
Recall that, if both a < b and c < b, then now P a i ,
4, be the set of rules of P 0 which are rules for a i or rules for
any atom c such that c < ::::: < a i . By the structure of P 0 and the fact that
it is clear that P a i and P a j , i 6= j are
equal up to the renaming of atoms. Hence it is also clear that the sets R a i , R a j ,
are equal up to the renaming of atoms. Let then m be the cardinality of
R a i , 4. By the previous arguments, it is obvious that the cardinality
of both R a 1 ;a 2
and R a 3 ;a 4
are 2  m. Hence, the cardinality of R
Let now We have just seen that the cardinality of R b can be given
inductively as
Furthermore it is obvious that since any atom a such that
does not occur in the head of any rule and hence f:ag is the only set in R a .
It is easy to show by induction that the relation f(k) we have just dened has
the unique solution
Let us now go back to the rule of P 1
r: :p; not l ! assert(p).
k. It is not di-cult to see that, due to the syntactic restrictions on
the number n of atoms occurring in P 0 are exactly
1from which we can easily calculate
i.e.
i.e.
Hence we can dene the cardinality of R l as a function g(n) as follows
Let now
2 . Then
4 . It is easy to see that, for any constants
c; d and su-ciently big x, 4 x > d  x 2c . Hence, for any constant c and su-ciently
We can conclude that g(n) is not polynomial in n, the number of atoms of P 0 .
Hence, the worst case complexity of translating away naf is not polynomial in
the number of atoms.
6 Discussion and Conclusions
Production systems with negation as failure to nd a course of actions are
a natural extension of classical production systems, which increases their expressiveness
in the sense that they allow a natural and simple representation
(specication) of many real life problems. This extension can be given a simple
semantics based on an argumentation theoretic framework.
Negation as failure to nd a course of actions is tightly related to negation as
failure to prove in logic programming. Indeed, any normal logic program P can
be viewed as a GPS G P by transforming each rule
a a
into a production rule
if :a; a not a not a k then assert(a).
It is not di-cult to show that the semantics of P and G P coincide, in the sense
that each (grounded, preferred, stable) set of computations of G P corresponds
to a (grounded, preferred, stable) model of P . On the other side, in [8] it has
been shown that argumentation can be represented in logic programming with
negation as failure. Therefore we can say that the mechanisms of negation as
failure to nd a course of actions in production systems and negation as failure
to prove in logic programming are dierent sides of the same coin.
There are still several issues which deserve a deeper study and understanding.
First, we have seen that our semantics re
ects the inherent nondeterminism of
production systems. In fact, in our semantics dierent complete computations
starting from the same initial state can yield dierent nal states, even for
stratied GPS's. This contrasts with many eorts in the literature aiming at
nding a method to select one of the complete computations as the expected
semantics [13, 24]. Even though we believe that in many cases these eorts
contrast with the inherent nondeterministic nature of the problems represented
by the production rules, there are situations in which selecting only one out of
(possibly) many complete computations may not harm at all. In these cases,
it is worth studying computational strategies which basically provide us with
a deterministic operational semantics for production systems. Still, the declarative
semantics serves as a basis for reasoning about the correctness of these
methods.
Secondly, we intend to study computational mechanisms and proof procedures
for general production systems with negation as failure. We have seen that for
stratied production systems there is a way to compute negation as failure in
a bottom-up fashion. This can be seen as a dynamic or run-time method to
compute negation as failure. It is worth addressing the point of whether the
class of stratied PS can be extended to more general classes, for which similar
bottom-up methods exist. On the other hand, in some cases negation as failure
can be compiled down to classical negation, as we have seen in Section 1.2.
This can be seen as a compile-time or static method to compute negation as
failure. Finding general techniques to achieve this is another interesting issue.
As we have already mentioned, in this case negation as failure still serves as a
specication for classical (i.e. without naf) production systems.
Finally, we are investigating the application of our approach in the active
databases area. Active databases [6] are an important research topic in the
database community, due to the fact that they nd many applications in real
world problems. Many commercial databases systems have been extended to
allow the user to express active rules. Still, active databases are faced with
many open issues, such as the lack of a well understood declarative semantics
(see, e.g. [11, 29]). Such a semantics would provide a common basis for understanding
the operational semantics dened by the implementation of active
rules in database systems, as well as for comparing dierent implementations.
The typical active rule in active databases is an event-condition-action rule of
the form on Event : if Condition then Action . We are currently extending
our argumentation based approach to these active rules, and we are addressing
also in this case the use of negation as failure in the Condition part of the rules.



--R


Static analysis techniques for predicting the behavior of active database rules.
Towards a theory of declarative knowledge.
An abstract
Preferred answer sets for extended logic programs.
Active Database Systems: Triggers and Rules For Advanced Database Processing.
Negation as hypotheses: An abductive foundation for logic programming.
The acceptability of arguments and its fundamental role in logic programming
Production systems need negation as failure.
reasoning with speci
Active database systems.
OPS5 user's manual.
logic for action rule-based systems

The stable model semantics for logic pro- gramming
An overview of production rules in database systems.
Rule based systems.
Computing argumentation in logic programming.

Semantical considerations on nonmonotonic logics.
Defeasible reasoning.
A system for defeasible argumentation
Logical systems for defeasible argumen- tation
A semantics for a class of strati
A logic for default reasoning.
A mathematical treatment of defeasible reasoning and its implementation.
Unfounded sets and well-founded semantics for general logic programs
The feasibility of defeat in defeasible reasoning.
Active database rules with transaction-conscious stable-model semantics
--TR
rule-based processing;knowledge-based systems;rule-based systems;expert systems;knowledge representation