\documentstyle[jair,twoside,11pt,theapa,makeidx,amsmath,amssymb,epsfig]{article}
\input epsf %% at top of file

\jairheading{24}{2005}{465-518}{09/04}{10/05}
\ShortHeadings{Reasoning about Action: An Argumentation-Theoretic Approach}
{Vo \& Foo}
\firstpageno{465}

\newtheorem{Def}{Definition}[section]
\newtheorem{Exa}{Example}
\newtheorem{Lem}{Lemma}
\newtheorem{Cor}{Corollary}
\newtheorem{The}{Theorem}
\newtheorem{Obs}{Observation}
\newtheorem{Ass}{Assumption}
% \input psfig.sty

\newenvironment{aThe}{\noindent{\bf Theorem}\em}{}
\newenvironment{aExa}{\noindent{\bf Example}\em}{}
\newenvironment{aLem}{\noindent{\bf Lemma}\em}{}
\newenvironment{aObs}{\noindent{\bf Observation}\em}{}
\newenvironment{aCor}{\noindent{\bf Corollary}\em}{}
\newenvironment{aPro}{\noindent{\bf Proposition}\em}{}
\newenvironment{aFct}{\noindent{\bf Fact}\em}{}

%% \usepackage{makeidx}  % allows for indexgeneration
%% \usepackage{amsmath, amssymb}  % allows for indexgeneration
%% \usepackage{picinpar}
%% \usepackage{wrapfig}
%% \usepackage{epsfig}
%% \usepackage{pstricks,pst-node,pst-tree}

\makeindex

\begin{document}

\title{Reasoning about Action: \\ An Argumentation-Theoretic Approach}

\author{\name Quoc Bao Vo \email vqbao@cs.rmit.edu.au \\
        \addr School of Computer Science and Information Technology \\
              RMIT University \\
              GPO Box 2476V, Melbourne, VIC 3001,  Australia \\
       \AND
       \name Norman Y. Foo \email norman@cse.unsw.edu.au \\
       \addr Knowledge Systems Group \\
             Artificial Intelligence Laboratory \\
             School of Computer Science and Engineering\\
             University of New South Wales, Sydney, NSW 2052, Australia}

% For research notes, remove the comment character in the line below.
% \researchnote

\maketitle


\begin{abstract}
We present a uniform non-monotonic solution to the problems of reasoning
about action on the basis of an argumentation-theoretic approach. Our theory is
provably correct relative to a sensible minimisation
policy introduced on top of a temporal propositional logic. Sophisticated
problem domains can be formalised in our framework. 
As much attention of researchers in the field has been paid to the
traditional and basic problems in reasoning about actions
such as the frame, the qualification and the ramification problems, approaches 
to these problems within our formalisation lie at heart of the expositions
presented in this paper.
\end{abstract}


\section{Motivation and Introduction}

The need for a good reasoning about action formalism is apparent for research 
in artificial intelligence (AI). 
Alongside the logicist point of view to artificial intelligence, more recently, 
there emerges the cognitivist and situated action-based approaches(see 
\citeR{Kus96} and the references therein). 
The latter approaches
provide some immediate and practical answers to certain issues of AI. The current 
problem domains for (Soccer) Robot Cup seem to be an area where these approaches 
promise to gain fruitful results. On the other hand, the logicist approach aims
at long term solutions for the general problems of AI.
From a logicist approach, formalising dynamic domains for reasoning about 
action can be
realised within a logical knowledge representation. The general idea is that
intelligent agents should be able to represent all kinds of knowledge in
a uniform way such that some general problem solver can fully employ and 
find a solution based on their knowledge. As it turns out, there are 
difficulties with such a general approach to AI. Consider the task of 
formalising dynamic domains in some logical language. To formalise the 
dynamics of an action (or event) in a language with $n$ fluents\footnote{%
\emph{fluent} is a technical term referring to functions or predicates whose
values can be varied relative to time.}, one will need to axiomatise
not only about the fluents that are effected by the action but also about 
those that are not. Essentially, it requires that $n$ axioms be asserted.
Such a formalisation can hardly be considered a good representation. Hence,
there is the need to solve this problem in logic-based reasoning about action
formalisms.
%% This is the well known frame problem as introduced by McCarthy and 
%% Hayes \cite{MH69}. Moreover, there is still a problem in axiomatising the
This is the well known \emph{frame problem} as introduced by \citeA{MH69}. Moreover, there
is still a problem in axiomatising the 
effects of an action, called the \emph{effect axioms}. A logical axiomatisation requires 
that the conditions under which the effects will take place after executing
the action be precisely specified. However, there are potentially infinitely 
many such conditions, some of which the reasoner may never have thought about.
No realistic formalisation would ever be able to exhaustively enumerate all of 
those conditions. Nonetheless, to start a car, most people only worry about 
whether they have the key to that car. They never bother checking whether there 
is something blocking the tailpipe or checking all electric circuits to make sure 
that they are all well connected.
Such a story has long been well-known within the community of
commonsense reasoning, in particular reasoning about action. This is known as 
%the qualification problem and was introduced by McCarthy (cf. \cite{McC77}).
the \emph{qualification problem} and was introduced by \citeA{McC77}.

While there have been a number of solutions to the frame problem
\cite<e.g.,>{Sha97,Rei91,Cas99},
the qualification problem has largely been ignored with the notable exception of
\citeS{thielscher01qualification} solution within the Fluent Calculus and \citeS{DK98}
circumscription-based solution using fluent dependency constraints. Some people argue that
the frame problem is already 
very challenging and it would be a good approach to thoroughly solve the 
frame problem before complicating a formalism with the qualification
problem. We argue that there is a danger of approaching these problems from
that point of view for (at least) two reasons: 
\begin{enumerate}
\item \emph{It may be very hard to
come up with a uniform solution for all problems:} while many existing
solutions for the frame problem are monotonic \cite<e.g.,>{Rei91,Cas99}, 
the qualification problem inherently requires a non-monotonic
solution. This is the case with the original qualification problem as 
stated by \citeA{McC77} for the dynamics of actions/events need to be
finitely axiomatisable and when an unexpected qualification for an action
arises, the agent must necessarily retract his initial expectation that the 
effects caused by the action would take place, making the underlying 
reasoning machinery non-monotonic (see section~\ref{sec:1.3} for
a discussion on the qualification problem).
\item \emph{Many solutions to the frame problem can only succeed
under some precise assumptions.} For instance,

\begin{itemize}
\item  Actions always succeed. This is the {\em action omniscience}
assumption. More precisely, this assumption dictates that the qualification
problem is skipped. This is the case with all monotonic solutions to the
frame problem.\footnote{The argument that any solution to the frame problem
which works with nondeterministic action is not subject to this assumption
does not stand. The quick fix of allowing such an approach to a fortiori 
express actions that may fail by representing failure as a possible effect
is an invalid one. It is because we can no longer infer that, in the absence 
of evidences that suggest otherwise, actions would normally succeed. It's
also worth noting that \citeS{lin96embracing} extension of \citeS{Rei91}
solution to the frame problem in the Situation Calculus to deal with 
nondeterministic action is based on circumscription.}

\item  Fluents change if and only if the reasoner knows that there exists an
action that possibly changes its value. This can be termed as {\em domain
omniscience} assumption. It assumes that the reasoner has complete
(ontological) knowledge of the domain about which he is reasoning.
\end{itemize}
\end{enumerate}

The above two reasons are of course closely related as the former arises due to the 
underlying assumptions in the latter which no longer holds once the qualification 
problem is taken into consideration. 

In the remainder of this section, we review several works on this topic before
introducing the reader to our approach. 

\subsection{The Frame Problem}

In the late 1960s, the frame problem had been recognised as a major obstacle to
formalising dynamic domains (see the discussions and exposition by 
\citeR{MH69,Gre69}).
Several alternative responses to the frame problem have been proposed along way.
To respond to the explosive number of axioms required for theorem proving-based
planners as proposed by \citeA{Gre69}, \citeA{FN71} 
% planners as proposed by Green \cite{Gre69}, Fikes and Nilsson \cite{FN71} 
introduce procedures
that operate on special data structures used to represent dynamic domains. However, 
for complex and sophisticated problem domains, e.g. those with domain constraints, 
concurrent actions, observations at different time points, etc.
STRIPS quite often fails to express
the domain knowledge. In fact, the expressivity of STRIPS is quite limited as has 
been pointed out by \citeA{Lif87}. Another response attributing the
% been pointed out by Lifschitz \cite{Lif87}. Another response attributing the
frame problem as an artefact of the situation calculus has proved to be 
ungrounded. There are attempts to distinguish a logical or epistemological aspect
of the frame problem from the computational aspect \cite<e.g.,>{McD87,Kow92}.
While the computational inefficiency associated with a representation of dynamic
domains in the situation calculus can be attributed to the explosive number of 
global situations required by the situation calculus as argued by  
\citeA{KS86}, the logical aspect of the frame problem is inherent 
% Kowalski and Sergot \cite{KS86}, the logical aspect of the frame problem is inherent 
to any logic-based representation of dynamic domains. It is thus essential that a 
logical approach to AI and knowledge representation have a decent solution to the
frame problem.

% Later, with the introduction of the qualification problem by McCarthy \cite{McC77}, it is
Later, with the introduction of the qualification problem by \citeA{McC77}, it is
reckoned that formalising dynamic domains not only is about solving the frame 
problem but would require systematic studies to fundamental issues of knowledge
representation. In the early 1980s, the frame and the qualification problem were 
considered to be instances of commonsense reasoning problems. In particular, many 
believed that a non-monotonic reasoning framework would solve the frame problem. 
It was argued that the `principle of inertia'\footnote{The {\em principle of inertia}
or the {\em common sense law of inertia} basically states that 
\emph{``By default a fluent 
is assumed to persist over time unless there is evidence to believe otherwise.''} 
The reader is referred to
% Shanahan's book \cite{Sha97} for more details on this principle and the issues around it.} 
\citeS{Sha97} book for more details on this principle and the issues around it.} 
which is considered to be the key to
the frame problem can be formalised in terms of default rules or default axioms in
default reasoning.
Moreover, it was also argued that to solve the qualification problem, the following 
common sense law should be rendered: \emph{``an action, by default, would qualify to 
succeed and bring about the intended effects unless there is known reason for it not 
to,''} in formalisations of dynamic domains. 

With the introduction of several non-monotonic reasoning formalisms, e.g. truth 
%% maintenance systems (TMSs) by Doyle \cite{Doy79}, default logics by Reiter 
%% \cite{Rei80}, 
%% circumscriptive approaches by McCarthy \cite{McC80}, modal non-monotonic logic by 
%% McDermott and Doyle \cite{MD80}, autoepistemic logic by Moore \cite{Moo85}, etc. 
maintenance systems (TMSs) by \citeA{Doy79}, default logics by \citeA{Rei80}, 
circumscriptive approaches by \citeA{McC80}, modal non-monotonic logic by 
\citeA{MD80}, autoepistemic logic by \citeA{Moo85}, etc., 
it was believed 
that these problems were solved. The solutions to these problems were illustrated as
examples for the proposed non-monotonic reasoning frameworks. For instance, 
\citeA{McC86} showed how circumscription is used to solve the frame problem
relative 
% McCarthy \cite{McC86} showed how circumscription is used to solve the frame problem relative 
to the {\em blocks world} domain. Unfortunately, 
\citeA{HM87} show that these formalisations do not 
% Hanks and McDermott \cite{HM87} show that these formalisations do not 
work correctly in a simple dynamic domain known as the Yale Shooting Problem (YSP). We
will now review successful attempts to solve the frame problem:

\begin{enumerate}

\item \citeA{Bak89} successfully modifies the original (and incorrect)
% Baker \cite{Bak89} successfully modifies the original (and incorrect)
circumscription policy proposed by \citeA{McC86} to deal with the Yale Shooting Problem.
In the traditional circumscriptive policy, the predicate $Abnormal$ is minimised with
the predicate $Holds$ allowed to vary. Baker suggests that, instead of allowing $Holds$
to vary, the function $Result$ should be the one to be varied. 
While this does not solve the frame problem in its full generality, this initiates
the line of research which brings many fruitful results to reasoning about action
community. For a more detailed discussion about these solutions and the follow up 
% works, the reader is referred to \citeS{Sha97} book. Furthermore, Foo {\em et al.}
% works, the reader is referred to Shanahan's book \cite{Sha97}. Furthermore, Foo {\em et al.}
works, the reader is referred to \citeS{Sha97} book. Furthermore, 
\citeA{FZVP01} present an exposition on the issue from an automata  and system theory point
of view. 
In order for \citeS{Bak89} solution to work correctly, additional axioms need to be introduced,
e.g. domain closure axioms, axioms about the existence of situations, etc.
This emphasises that: (i) the circumscriptive approach to reasoning about action only
works under careful designation and considerations of the domain; and more importantly,
(ii) circumscription is domain dependent. That is, a domain dependent circumscriptive
policy is required to correctly render the common sense of a particular problem domain.

\item A number of researchers argue that in many cases, a monotonic solution
% to the frame problem will be sufficient. Pednault \cite{Ped89} assumes that 
to the frame problem will be sufficient. \citeA{Ped89} assumes that 
the effect of actions on fluents are specified by {\em effect axioms} of the following 
forms:

\begin{eqnarray}
\varepsilon^+_F(\vec{x}, \vec{y},s) \supset F(\vec{x}, do(A(\vec{y}),s )),
\label{eq:ae1}\\
\varepsilon^-_F(\vec{x}, \vec{y},s) \supset \neg F(\vec{x}, do(A(\vec{y}),s )),
\label{eq:ae2}
\end{eqnarray}

Here, $A(\vec{y})$ and $F(\vec{x}, s)$ are the parameterised action and fluent, 
respectively; $\varepsilon^+_F(\vec{x}, \vec{y},s)$ and 
$\varepsilon^-_F(\vec{x}, \vec{y},s)$ are first order formulas whose free 
variables are among $\vec{x}, \vec{y},s$. \citeA{Ped89} makes the following
% variables are among $\vec{x}, \vec{y},s$. Pednault \cite{Ped89} makes the following
\textbf{Causal Completeness Assumption}:
\begin{quote}
\emph{
The axioms (\ref{eq:ae1}) and (\ref{eq:ae2}) specify all the causal laws relating the 
action $A$ and the fluent $F$.
}
\end{quote}

Note that the Causal Completeness Assumption is a stronger form of the domain omniscience 
assumption presented above. Under this assumption, the following frame axioms can be 
introduced:

\begin{eqnarray*}
F(\vec{x}, s) \wedge
\neg \varepsilon^-_F(\vec{x}, \vec{y},s)
\supset F(\vec{x}, do(A(\vec{y}),s )).
\end{eqnarray*}
and
\begin{eqnarray*}
\neg F(\vec{x}, s) \wedge
\neg \varepsilon^+_F(\vec{x}, \vec{y},s)
\supset \neg F(\vec{x}, do(A(\vec{y}),s )).
\end{eqnarray*}

\citeA{Sch90}, elaborating on a proposal of 
\citeA{Haa87}, employs the so-called \textbf{Explanation Closure Axioms}  of the
%% Schubert \cite{Sch90}, elaborating on a proposal of 
%% Haas \cite{Haa87}, employs the so-called \textbf{Explanation Closure Axioms}  of the
following forms:

\begin{eqnarray}
F(\vec{x}, s) \wedge
\neg F(\vec{x}, do(A, s))
\supset 
\alpha_F(\vec{x}, A, s),
\label{eq:ae3}\\
\neg F(\vec{x}, s) \wedge
F(\vec{x}, do(A, s))
\supset 
\beta_F(\vec{x}, A, s),\label{eq:ae4}
\end{eqnarray}

Or, equivalently, we can rewrite the above two axioms as follows:

\begin{eqnarray*}
F(\vec{x}, s) \wedge
\neg \alpha_F(\vec{x}, A, s)
\supset F(\vec{x}, do(A, s )).%\\
\end{eqnarray*}
and
\begin{eqnarray*}
\neg F(\vec{x}, s) \wedge
\neg \beta_F(\vec{x}, A, s)
\supset \neg F(\vec{x}, do(A, s )).%\\
\end{eqnarray*}

Schubert's proposal is correct under the following assumption, called the \textbf{Explanation Closure Assumption}:
\begin{quote}
\emph{
$\alpha_F$ completely characterises all those actions $A$ that can cause the fluent $F$'s
truth value to change from {\bf true} to {\bf false}; similarly for $\beta_F$.
}
\end{quote}

\citeA{Rei91} then combines the merits of the above two proposals by
systematically generating the frame axioms as proposed by \citeA{Ped89} with
the quantifiers over the set of actions as proposed by \citeA{Haa87} and
\citeA{Sch90}. 

Other researchers who also propose monotonic solution to the frame problem
include \citeA{Cas99}, and \citeA{FZ01}.

%% Reiter \cite{Rei91} then combines the merits of the above two proposals by
%% systematically generating the frame axioms as proposed by Pednault \cite{Ped89} with
%% the quantifiers over the set of actions as proposed by Hass \cite{Haa87} and
%% Schubert \cite{Sch90}. 

%% Other researchers who also propose monotonic solution to the frame problem
%% include: Castilho {\em et al.} \cite{Cas99}, and Foo and Zhang \cite{FZ01}.

\item Attempts to solve the frame problem using default logic \cite{Rei80}
also encounter some problematic issues. 
\citeA{HM87} show that a 
% Hanks and McDermott \cite{HM87} show that a 
natural formulation of the Yale Shooting Problem in 
default logic suffers the same problem as that with circumscriptive approaches,
{\em viz.} the existence of anomalous extensions. 
\citeA{Mor88}
% Morris \cite{Mor88}
proposes a slight modification on Hanks and McDermott's original formulation
to the Yale Shooting Problem in an attempt to avoid the anomalous extensions.
As pointed out by \citeA{Tur97}, Morris' formulation is complete,
% As pointed out by Turner \cite{Tur97}, Morris' formulation is complete,
and thus eliminates the anomalous extensions in the Yale Shooting Problem, but
unsound. More importantly, from Morris' formulation it is not clear how dynamic 
domains should be formulated in general. \citeA{Tur97} himself then 
% domains should be formulated in general. Turner \cite{Tur97} himself then 
proposes a way to formalise dynamic domains using default logic (and also logic 
programming). His solution is based on the following observation: In the Yale 
Shooting domain and similar dynamic domains, the anomalous extensions arise 
because undesired effects of an action can be derived by reasoning ``backward in 
time.'' For instance, in the Yale Shooting domain, by making the counterintuitive 
supposition that the victim of the shooting is somehow still alive after the 
shooting, an anomalous extension come up in the following way. First, it allows
the default saying that the victim persists to be alive regarding the shooting 
action to be applicable. As a consequence, the gun must not be loaded before the 
shooting action. Therefore, it blocks the application of the default saying that
the gun persists to be loaded regarding the waiting action. In other words, the 
loaded gun would get unloaded (magically) during the waiting action which is an
undesirable conclusion. To block these lines of ``backward'' reasoning, Turner 
appeals to the non-contrapositivity of inference rules and replaces the 
implications by inference rules. To guarantee that this formulation work correctly,
additional techniques are required such as a fact $\varphi$ will be formulated as
an inference rule:
\[
\frac{\neg \varphi}{\mathbf{false}}
\]
and enforcing the completeness of the initial situation by adding the following 
rules:
\[
\frac{:Holds(f,S_0)}{Holds(f,S_0)}
\qquad
\frac{:\neg Holds(f,S_0)}{\neg Holds(f,S_0)}
\]
for every fluent $f$.

However, \citeS{Tur97} formulation is still fairly {\em ad hoc} as 
% However, Turner's \cite{Tur97} formulation is still fairly {\em ad hoc} as 
different techniques
are added to fix the known issues. For example, the inference rules are used in place 
of implications to block the application of the undesirable ``backward'' reasoning,
the rules completing the initial situations are added to overcome the unsoundness 
issue in Morris' \citeyear{Mor88} formulation, etc. This also shows the problematic
% issue in Morris' \cite{Mor88} formulation, etc. This also shows the problematic
side of default logic as a uniform formalisation to various problems of common
sense reasoning. This becomes a serious issue if one proceeds with the question of 
how the qualification problem, a typical problem of default reasoning, is solved
in \citeS{Tur97} formalisation of dynamic domains. This is the case, for 
% in Turner's \cite{Tur97} formalisation of dynamic domains. This is the case, for 
example, when instead of asserting that the victim dies whenever it is shot by a loaded
gun the reasoner can only maintain that as a default proposition as there may be many 
hidden possible conditions under which the victim may not die. Thus the reasoner is able 
to deal with `surprising' situations in which the victim is observed to be still 
alive after the shooting action (of a loaded gun). Another, symmetric, case is with 
`surprises' regarding the persistence of fluents. For instance, after a waiting action,
which is not supposed to unload a gun, the gun, which was loaded before the wait action,
is observed to be unloaded. Such a scenario was first introduced by  \citeA{Kau86} in a
scenario called the Stolen Car Problem. In both cases, reasoning ``backward
% called the Car Stolen Problem \cite{Kau86}. In both cases, reasoning ``backward
in time'' is necessary. It is not clear how these will be rendered in Turner's formulation
which explicitly intends to block ``backward'' reasoning. These scenarios will be analysed 
in the solution we present later in this paper.
\end{enumerate}

\subsection{The Qualification Problem}\label{sec:1.3}

While there have been several
solutions to the qualification problem, none of these addressed the original
qualification problem introduced by \citeA{McC77} and later formalised by
% qualification problem introduced by McCarthy \cite{McC77} and later formalised by
\citeA{GS88}.
% Ginsberg and Smith \cite{GS88}.

\begin{enumerate}
\item \citeA{LR94} propose a formalisation for action theories
% \item In \cite{LR94}, Lin and Reiter offer a formalisation for action theories
in the situation calculus (SC). Their formalism is an extension of 
\citeS{Rei91} solution to the frame problem (sometimes) by incorporating
% Reiter's \cite{Rei91} solution to the frame problem (sometimes) by incorporating
state constraints. They discover that there are at least two different kinds
of state constraints which they call ramification and qualification
constraints. They then go further to claim a solution to the qualification
(and the ramification) problem. The basic idea behind their solution to the
qualification problem is that certain state constraints imply implicit
preconditions of some actions. Thus an action may not be qualified even
though it appears (from the explicit action description) to be. While this
is of course a special case of the qualification problem, the classical
qualification problem as introduced by \citeA{McC77} has a much
% qualification problem as introduced by McCarthy \cite{McC77} has a much
broader extent. In this setting, the qualification problem is more a
pragmatic issue than a technical issue. Similar to the frame problem, it is
impractical, and sometimes impossible, to axiomatise all the possible
preconditions of an action. For example, in addition to the requirement that
the gun be loaded, to guarantee that performing the action shoot would kill
the victim, many preconditions must also be included such as: the gun is not
malfunctioning, the shooter does not miss the victim, the victim does not wear a
bullet-proof jacket, etc. among which some
may be very improbable such as: ``no alien interferes with the bullet.'' The 
reasoner
simply does not want to consider these conditions by assuming that they are
not the case unless there are explicit evidences stating otherwise. In other
words, the qualification problem in its original form requires that the
reasoner be able to tolerate the mistaken conclusions possibly jumped to by
previous inferences and to correct them appropriately. Henceforth, we will
always refer to the {\em qualification problem} in this original form.
It is this similarity to the frame problem that led John McCarthy to conjecture that:
\begin{quote}
The {\em frame problem} may be a sub-case of what we call the {\em %
qualification problem}, and a good solution of the qualification problem may
solve the frame problem also.

\hfill (\citeR{McC77}, p. 1040, \emph{italics are original}.)
\end{quote}

Roughly 10 years after his introduction of the qualification problem, \citeA{McC86} presented
his solution to the problem using his non-monotonic formalism of circumscription. However,
this solution suffers an almost identical flaw as its counterpart 
% \cite{McC86}. However, this solution suffers an almost identical flaw as its counterpart
regarding the frame problem: simple minimisation of abnormalities sanctions anomalous
models \cite<e.g.,>{thielscher01qualification}.

\item \citeA{MT95} propose a solution to the problem
described by \citeA{LR94}, viz. the problem of deriving the implicit
%% \item In \cite{MT95}, McCain and Turner propose a solution to the problem
%% described by Lin and Reiter in \cite{LR94}, viz. the problem of deriving the implicit
preconditions from state constraints. McCain and Turner's solution is posed
in a model-based representation of action theories.

\item Similar to \citeS{MT95} result, \citeA{Bar95}
%\item Similar to McCain and Turner's \cite{MT95} result, in \cite{Bar95} Baral
offers a solution to the problem defined by Lin and Reiter using a
state-based representation. Baral extends the language of disjunctive logic
programs for state specification and as an action description language.

\item \citeA{DK98} make a careful investigation to
% \item In \cite{DK98}, Doherty and Kvarnstr\"om make a careful investigation to
the qualification problem. They are aware of the shortcomings present in the
definition of the ``qualification problem'' introduced by \citeA{LR94}. 
% definition of the ``qualification problem'' introduced by Lin and Reiter \cite{LR94}. 
They proceed one step further to distinguish between the {\em %
weak} and {\em strong} forms of the qualification problem. To deal
comprehensively with the qualification problem in its full extent, Doherty
and Kvarnstr{\"o}m apply circumscription on a predicate which plays a similar
% role to the predicate $Poss$ used by Lin and Reiter \cite{LR94}.
role to the predicate $Poss$ used by \citeA{LR94}.

Even though \citeS{DK98} solution is closest in spirit to the
% Even though Doherty and Kvarnstr\"om's \cite{DK98} solution is closest in spirit to the
original form of the qualification problem, there is still a serious problem
with their approach. The intended designation on predicate $Poss$ and its
variants is action-oriented. 
That is, it would qualify on the {\em executability}
condition for the action under consideration, not towards the effects that
action is supposed to cause. In other words, only circumscribing $Poss$ does
not guarantee to capture the full extent of the qualification problem. For
example, a single action of shooting a gun may cause several effects:
killing the victim, making a loud noise, emptying the cartridge, etc. The
conditions for such an action to be executable is: having the gun, the gun
is not broken, the gun is loadable, etc. Once the action is executable, it is
not necessary that all effects will take place. It may be the case that
there is a loud noise and the cartridge is emptied but the victim is still
alive since the victim was wearing a bullet-proof jacket. Assuming
that the reasoner is somehow aware about this possibility, should he include
the requirement that the victim not wear a bullet-proof jacket
% the interference of the alien as a qualification for the action shoot?
as a qualification for the action shoot?
Perhaps he should not for he would still expect to hear a loud noise and the 
cartridge to be emptied after the shoot action.

These are not the end of all the troubles though. The presence of both
qualification and ramification constraints causes several complications.
Firstly, they are not syntactically distinguishable. Secondly, as has been
mentioned by \citeA{DK98}, qualification constraints may cause
% mentioned by Doherty and Kvarnstr\"om \cite{DK98}, qualification constraints may cause
indirect effects to arise and vice versa, i.e. ramification constraints may
reveal implicit action preconditions. \\[1ex]
\textsc{Remark:} The terms \emph{ramification constraints} and 
\emph{qualification constraints} were first introduced by \citeA{LR94}
when a careful examination to state constraints was taken. As discussed by
\citeA{DK98}, these two kinds of constraints might interact in several ways. 
Consider the example introduced by \citeA{DK98}: the only
preconditions of the action \emph{board} a plane are
\emph{having-ticket} and \emph{at-gate}. However, to a 
passenger who places a gun into his pocket at home before travelling
to the airport and proceeding to the gate, a new qualification
for the action \emph{board} materialises. Because one ramification
of putting an object in your pocket is that it will stay with you 
as you travel from location to location (i.e. result of a \emph{ramification
constraint}), a reasoner could easily conjecture that our passenger
fails to board the plane. On the other hand, the fact that a passenger 
who possesses a gun when trying to board the plane must fail to board the
plane is a result of a \emph{qualification constraint}. Now, not only the 
fact that a passenger possesses a gun disqualifies the action of boarding
a plane but it also brings about an indirect effect when the action of boarding
a plane is executed: the passenger being put under arrest. Note that for this
indirect effect to take place, both requirements must be present: the action of 
boarding a plane being executed, and the above qualification constraint is
present. In other words, a qualification constraint might also bring about 
indirect effects.

We believe that all these problems are
too sophisticated for any circumscription policy to successfully address in
most situations. Furthermore, such a policy would be extremely hard to
understand and error-prone. Recall the failure of non-monotonic reasoning
formalisms regarding the frame problem (in its simplest form viz. without
the ramification and the qualification problems). Researchers had failed to
point out this bug for several years before Hanks and McDermott discovered it
in their award winning paper \citeyear{HM87}.

\item More recently, \citeA{thielscher01qualification} gives an exposition on
% \item More recently, Thielscher \cite{thielscher01qualification} gives an exposition on
  the qualification problem. Thielscher discusses the problem sustained by \citeS{McC86}
%  the qualification problem. Thielscher discusses the problem sustained by McCarthy's
  simplistic circumscription policy, \emph{viz.} the anomalous models. He then introduces
  a default logic based formalisation for the qualification problem in the Fluent Calculus
  and shows that his formalisation does not suffer the problem of anomalous models. Note
  that in Thielscher's formalisation, circumscription is still required to generate the
  initial theories of the default theories (in addition to the set of default
  rules). Nevertheless, Thielscher's solution still suffers the following drawbacks: (i)
  Thielscher's use of the predicate $Poss$ is in the same way as has been formulated by
  \citeA{DK98}. Thus, qualifications are taken over the executability conditions for the
  actions rather than over different effects of the
  actions; and (ii) while Thielscher shows that the problem of
  anomalous models sustained by \citeS{McC86} circumscription policy is overcome in his
%  anomalous models sustained by McCarthy's circumscription policy is overcome in his
  formalisation, it's not entirely clear whether Thielscher's formalisation which
  is based on both circumscription and default logic will not suffer from other 
  anomalies.
\end{enumerate}


\subsection{The Ramification Problem}\label{sec:ramp}

In the context of reasoning about action, the ramification problem is mainly
related to indirect effects. Finding a solution to this problem may not be
easy as indirect effects indicate exceptions to frame assumptions and
require special treatment. While there have been several formalisms
dealing with the ramification problem, e.g., see \cite{Lin95,MT95,Thi97}, 
there are still several issues that need a more careful consideration. 
We consider three examples to motivate our discussion.

\begin{Exa}\label{exa:4.2} 
{\rm
Consider \citeS{Thi97} circuit:
% Consider Thielscher's (\cite{Thi97}) circuit:

\begin{figure}[hbt]
\centerline{\psfig{figure=pictures/circuit4.eps,height=5cm}}
\caption {Thielscher's circuit 
\label {fig:cir1}}
\end{figure}

This example is interesting because it gives a counterexample for the
minimalistic approaches e.g. in the work of \citeA{MT95}. In this domain, the intended 
relationship between $relay$ and $sw_2$ is that when $relay$ is on, it
would make $sw_2$ jump off. Thus, when $sw_1$ and $sw_3$ are both closed, $sw_2$
can not be also closed as that is prevented by $relay$. However, there is
certainly a duration (no matter how short it is) before $sw_2$ is forced to
jump off by $relay$. In the state given in Figure~\ref{fig:cir1},
after performing the action of closing switch $sw_1$, two next states are
equally possible: one in which $detect$ is on, in another it is 
off.\footnote{The reason for nondeterminism in this case is due to 
insufficiency of domain information: depending on the sensitivity of $relay$,
$light$ and $detect$, when $light$ could get lit quickly and $detect$ is very
sensitive to detect any glimpse of light and $relay$ is not sensitive enough
to make the switch $sw_2$ jump off quickly enough then $detect$ will be on;
otherwise it will stay off.} Only
the latter is sanctioned in a minimalistic account. Through this example,
Thielscher pointed out the need for keeping track of the chains of
applications of indirect effects.

\citeA{Thi97} proposes a way to remedy this problem by keeping track of the
applications of the domain constraints which are re-expressed in terms of
causal relationships. Thus, given the above example, his formalism is able
to arrive at a next state in which the $detect$ is on. Following such chains
of causal relationships, the dynamic system undergoes several intermediate
states before arriving at the next state.\hfill$\Box$
}
\end{Exa}

In this paper, we proceed one step further from \citeS{Thi97} position by
% In this paper, we proceed one step further from Thielscher's position by
formally representing the intermediate states as possible states of the
world.\footnote{%
Note that this point of view also corresponds to the traditional definition
of states as snapshots of the world.} We believe that an intelligent agent
should be able to reason about these intermediate states even though they
may not satisfy all domain constraints. This capability is especially
important if the reasoner needs to explain certain observations about the
world in a systematic way. We note that given an observation, there may be
several chains of causal relationships that bring about that observation.%
\footnote{%
For example, given $detect$ is not on in the next state, it can be that
either the $light$ has never been bright or the $light$ may have been bright
but the $detect$ is not sufficiently sensitive to detect its momentary
brightness.} Unless intermediate states are explicitly represented and
reasoned about, there is no way for an agent to have a full insight to the
system in hand and certain information would be missing.

\begin{Exa}\label{exa:4.3} 
{\rm
Consider \citeS{Lin95} spring-loaded suitcase with two latches.
% Consider Lin's \cite{Lin95} spring-loaded suitcase with two latches.
Let's assume that the latches can be toggled if the suitcase is closed. The
following state constraint is supposed to apply in this domain: $%
up(Latch_1)\wedge up(Latch_2)\supset open(Suitcase)$.

The question is: {\em how does a robot close the above suitcase back after
opening it?} 
\citeA{MT97} also consider this problem and their
% McCain and Turner \cite{MT97} also consider this problem and their
answer is:

\begin{quote}
In general, when both latches are up, it is impossible to perform {\em only}
the action of closing the suitcase; one must also concurrently toggle at
least one of the latches.

\hfill (\citeR{MT97}, p. 464, {\em italic is original}.)
\end{quote}

The problem now is how to represent the action of holding the suitcase
closed such that it would overcome the above indirect effect caused by the
loaded spring. This also suggests another kind of actions whose direct
effects are to keep the world unchanged. These actions have usually been
formalised by other researchers as fluents, e.g. $holding$. Our main objection to
this approach is that agents also need to reason about these actions since
they may also require certain preconditions such as the agent is strong
enough to hold the object. Moreover, under certain (abnormal) circumstances,
agents may also fail to perform such actions. That is, these actions are 
also subject to
the qualification problem discussed in the previous subsection.\hfill$\Box$
}
\end{Exa}

\begin{Exa}\label{exa:4.4}
{\rm
Consider the circuit
in Figure~\ref{fig:cir2}:\footnote{This example is an instance of the so-called
``vicious cycles'' scenarios, e.g., see \cite{shanahan99ramification}.}

\begin{figure}[hbt]
\centerline{\psfig{figure=pictures/circuit2.eps,height=5cm}}
\caption {A dynamic domain with a (potentially) infinite sequence of indirect effects
\label {fig:cir2}}
\end{figure}

It is quite obvious that after performing the
action $flip_1$ whose direct effect is having $sw_1$ closed, the following
circular sequence of indirect effects will take place: $\{relay_1,\neg
relay_2\}\rightarrow \neg sw_2\rightarrow \{\neg
relay_1,relay_2\}\rightarrow sw_2\rightarrow \{relay_1,\neg relay_2\}$. This
sequence of course would potentially carry on the above sequence of indirect
effects indefinitely unless $sw_1$ is flipped open or some device stopped
functioning correctly, e.g. when the battery is out of charge. In other words, this action
domain requires some 
action to be inserted in between a series of on going indirect effects which
can not be captured by the above representation. Note also that none of the
causation-based representations proposed by \citeA{Lin95}, 
\citeA{MT95} or \citeA{Thi97} is able to deal with the above action domain.\hfill$\Box$
%% causation-based representations proposed by Lin \cite{Lin95}, McCain and Turner
%% \cite{MT95} or Thielscher \cite{Thi97} is able to deal with the above action domain.
}
\end{Exa}

\subsection{Towards a Solution}
To address the problems discussed in the previous sections, we argue that in order to find
a uniform 
solution to these  problems one should avoid cryptic formalisms whose consequences can not
be seen clearly from the formalisation of the problem domains. As a consequence, we
propose a uniform non-monotonic solution 
to the main problems of reasoning about action. Essentially, when performing
commonsense reasoning, the reasoner relies on a number of plausible
assumptions, e.g., assuming that an instance of birds flies, or assuming
that shooting a turkey with a loaded gun causes it to die, etc. In
traditional default reasoning formalisms such as circumscriptive approaches
or default logic, these assumptions are made implicit. For example, these
are the instances of predicates which are minimised away by
circumscription or the implicitly asserted justifications in default rules
when they are still consistent with the extension under consideration in
default logic. The proposed representation formalism aims at making these
assumptions explicit so that an automated reasoner is conscious (at least)
about what assumptions it relies on when performing reasoning. Then the
reasoner can always manipulate these assumptions independently of each
other. It is also the basic idea of assumption-based frameworks which are at
%% heart of Bondarenko {\em et al}.'s \citeyear{BDK97} argumentation-theoretic approach.
heart of \citeS{BDK97} argumentation-theoretic approach.

We then proceed to consider the ramification problems and domain
theories with concurrent and non-deterministic events. Among the major
results, we show that our framework captures the essence of the
causation-based approaches regarding the ramification problem. Moreover, we
also show the expressiveness of our formalism through two examples in which
indirect effects also need qualifications and infinite sequence of indirect
effects. To the best of our knowledge, none of the existing formalisms are
able to cope with these scenarios.

Based on the basic idea of assumption-based frameworks, our approach comprises 
the following major aspects of representation:
\begin{enumerate}
\item We introduce different types of assumptions to render various
laws of common sense in dynamic domains. For instance, frame assumptions
are introduced to capture the \emph{common sense law of inertia} whilst
(two types of) qualification assumptions are introduced to overcome 
the qualification problem.
\item We introduce a special class of (system-generated) \emph{dummy actions}
to allow the explanation problem, i.e. when some actions or events occur
outside of the reasoner's knowledge, to be dealt with in a uniform manner.
\item Being based on \citeS{BDK97} argumentation-theoretic framework, our
approach makes use of the inference rules to represent domain knowledge.
\item Lying at heart of our approach is an argumentation-theoretic semantics, 
called \emph{plausibility semantics}, which is argued to best render common 
sense knowledge in dynamic domains. This semantics consists in a particular
policy of resolving conflicting assumptions when computing the argumentation
to be accepted.
\end{enumerate}

To summarise, in this paper we formalise an expressive
representation scheme in order to cope with sophisticated action domains. We
believe that such a formalisation sometimes requires certain advanced
knowledge to be encoded in a precise and well-engineered way. The
representation of action theories proposed in this paper can be considered
as the intermediate level between commonsense and scientific knowledge. The
expressiveness of the formalism is improved through several independent
steps by adding further assumptions into the domain descriptions. This also
shows one advantage of our solution: a simple representation can be achieved
by simply removing the involved assumptions. This is arguably a desirable
feature as the reasoner has the option of either increasing the
expressibility of the representation formalism or improving the simplicity
and, as a consequence, the efficiency of the reasoning system.

The rest of the paper is organised as follows: Section 2 summarises relevant 
features of the abstract argumentation framework proposed by \citeA{BDK97}, 
its semantics and concrete instances.
In Section 3 we present the syntax and
semantics of the basic temporal logic and the extension for reasoning about action. In
Section 4 we present our formalisation for reasoning about action based on the
argumentation-theoretic approach introduced by 
%% Bondarenko {\em et  al}. \citeyear{BDK97}. The technical framework as well as 
\citeA{BDK97}. Our approach to reasoning about action, in particular a uniform
solution to the frame and the qualification problems, as well as 
the main results of the paper
are presented in Section 5. In Section 6, we show how the proposed formalism is extended
to deal with more complex dynamic domains, including those with concurrent and
non-deterministic events, and indirect effects. Related work and future research 
directions are discussed in Section 7. We will defer most proofs of the results 
presented in the paper to the Appendix.

This paper is an extended version of two earlier conference papers \cite{VF01,VF02}. The
main differences are that in this version all proofs are included, lemmas that are used in
the proofs of the theorems are introduced to help the reader more easily comprehend these
results, and the presentation has been improved and extended with more examples of the
various constructions.


\section{Defeasible Reasoning by Argumentation}

Let a \emph{deductive system}\index{deductive system} $\langle {\cal L},{\cal R} \rangle$ be given, 
where $\cal L$ is some formal language with countably
many sentences and $\cal R$ is a set of inference rules. 
Given a theory $\Gamma \subseteq {\cal L}$ and a sentence $\alpha \in {\cal L}$, 
we write
$\Gamma \vdash _{\langle {\cal L},{\cal R}\rangle }\alpha $ if there is
a deduction from $\Gamma$ whose last element is $\alpha $. 
$Th_{\langle {\cal L}, {\cal R}\rangle }(\Gamma)$ denotes the set 
$\{\alpha \in {\cal L}\ |\ \Gamma \vdash _{\langle {\cal L},{\cal R}\rangle }\alpha \}$. 
Since the language ${\cal L}$ is
generally kept fixed whereas the set of inference rules ${\cal R}$ is likely
to vary depending on the description of the domain, when there is no
possible confusion we will abbreviate $\vdash _{\langle {\cal L},{\cal R}\rangle }$ 
and $Th_{\langle {\cal L},{\cal R}\rangle }$ as $\vdash _{{\cal R}}$ and 
$Th_{{\cal R}}$, respectively. Thus the classical inference relation 
$\vdash $ can also be written as $\vdash _{{\cal R}_C}$ where ${\cal R}_C$ is
the set of inference rules of classical propositional logic. Note also that
every set of inference rules considered in this paper will be a super set of 
${\cal R}_C$.

% Given $r=\frac{\alpha _1,\ldots ,\alpha _n}\alpha \in {\cal R}$, we will
% also denote $prem(r)=\{\alpha _1,\ldots ,\alpha _n\}$, the premises of $r$,
% and $cons(r)=\alpha $, the consequence of $r$.

Given a deductive system $\langle {\cal L},{\cal R}\rangle$, 
an \emph{assumption-based framework}\index{assumption-based framework} with respect to 
$\langle {\cal L},{\cal R}\rangle$ 
consists of a theory $\Gamma$ representing the current knowledge of the reasoner 
about the domain, an assumption base ${\cal AB}$ and a contrariness 
operator $^{-}$, i.e. given an assumption $\delta \in {\cal AB}$, 
$\overline{\delta}$ denotes the \emph{contrary} of $\delta$.\\[2ex]
\textsc{Remark:}
The notion of the contrary of an assumption is intended to generalise the
classical negation $\neg \delta$. Note that in general assumptions may be
constructed by special operators (e.g. \emph{negation-as-failure} in the case 
of logic programming, or the modal operator $L$ in the case of autoepistemic 
logic, \citeR{Moo85}), thus the contrariness operator must also
be sufficiently general. \\[-1ex]

The hardest part in reasoning with assumption-based
frameworks is computing the set of assumptions to augment the given theory 
$\Gamma$. In an argumentation-theoretic approach, this is realised by the attack
relation. To determine which assumptions to be accepted, assumptions are put
together to form arguments. The assumptions behind the best arguments are
considered to be acceptable. Several semantics for best arguments are
presented by \citeA{BDK97} based on the notions of attack: Given an 
assumption-based framework 
$\langle \Gamma, {\cal AB}, ^{-} \rangle$ and an assumption set 
$\Delta \subseteq {\cal AB}$:
\begin{itemize}
\item $\Delta$ \emph{attacks an assumption}\index{attacks an assumption} $\delta \in {\cal AB}$ iff 
$\overline{\delta} \in Th(\Gamma \cup \Delta)$.
\item $\Delta$ \emph{attacks an assumption set}\index{attacks an assumption set} $\Delta' \in {\cal AB}$ iff 
$\Delta$ attacks some assumption $\delta \in \Delta'$.
\item $\Delta$ is \emph{closed}\index{closed} iff $\Delta = {\cal AB} \cap Th(\Gamma \cup \Delta)$.
\item $\Delta$ is \emph{conflict-free}\index{conflict-free} iff 
there does not exist any $\delta \in {\cal AB}$ such that 
$\Gamma \cup \Delta \vdash_{\cal R} \delta, \overline{\delta}$.
\end{itemize}

Assumption-based frameworks in which assumption sets are always closed
are referred to as \emph{flat}\index{flat}. In a flat assumption-based framework,
the conflict-free property of a set of assumptions $\Delta$ is equivalent
to the property that $\Delta$ does not attack itself.
The major argumentation-theoretic semantics defined by \citeA{BDK97} for
assumption-based frameworks include:
\begin{itemize}
\item \emph{Stability semantics}\index{stability semantics}: an assumption
set $\Delta \subseteq {\cal AB}$ is \emph{stable} iff
\begin{enumerate}
\item $\Delta$ is closed,
\item $\Delta$ does not attack itself, and
\item $\Delta$ attacks each assumption $\delta \notin \Delta$.
\end{enumerate}
\citeA{BDK97} show that the above stability semantics corresponds to 
the standard semantics of extensions of Theorist \cite{poole88logical}, 
minimal models of (many cases of) circumscription \cite{McC80,McC86}, 
extensions of Default Logic \cite{Rei80}, stable expansions of 
Autoepistemic Logic \cite{Moo85}, and stable models of logic 
programming. In other words, from a complexity-theoretic perspective, any
approach based on the existing formalisms to default reasoning can be 
rendered in a corresponding
assumption-based argumentation framework with no loss in terms of 
computational complexity.
\item \emph{Admissibility and Preferability semantics}\index{admissibility and preferability semantics}: 
\citeA{BDK97} go further to extend these existing formalisms by 
generalising
the semantics of admissible and preferred arguments which were originally 
proposed for logic programming only. The new semantics are defined in 
terms of ``admissible'' and ``preferred'' sets of
assumptions/extensions. An assumption set $\Delta \subseteq {\cal AB}$ is 
\emph{admissible} iff
\begin{enumerate}
\item $\Delta$ is closed,
\item $\Delta$ does not attack itself, and
\item for all closed sets of assumptions $\Delta' \subseteq {\cal AB}$ if 
$\Delta'$ attacks $\Delta$ then $\Delta$ attacks $\Delta'$.
\end{enumerate}
Maximal (with respect to set inclusion) admissible assumption sets are 
called \emph{preferred}.
\end{itemize}

Throughout this paper assumptions are expressed in terms of usual propositions.
Thus, we will replace
the notion of contrariness $^{-}$ in \citeS{BDK97} system with
the classical negation $\neg $ and omit it from the specification of
assumption-based frameworks. That is, an assumption-based framework 
$\langle \Gamma, {\cal AB} \rangle$ consists of a theory $\Gamma \subseteq {\cal L}$,
and the assumption base ${\cal AB}$ which contains the assumptions to be used in the 
reasoning.



\section{Domain Descriptions\label{sc2}}

We introduce a propositional action description language based on a more
comprehensive representation formalism proposed by \citeA{San94}. In
particular, we extend \citeS{DB99} 
%% comprehensive representation formalism proposed by Sandewall \cite{San94}. In
%% particular, we extend Drakengren and Bj\"areland's \cite{DB99} 
language so that it is possible to describe narratives in our framework.

\subsection{Syntax}

Following \citeA{San94}, 
% Following Sandewall \cite{San94}, 
the underlying representation of time is a ({\em %
discrete}) {\em time structure}\index{discrete time structure}\index{%
time structure|see{discrete time structure}} 
$\mathbf{T}=\langle \mathbb{T},<,+,-\rangle$\index{$\mathbf{T}$}
consisting of

\begin{itemize}
\item  a {\em time domain}\index{time domain} 
$\mathbb{T}$\index{$\mathbb{T}$} whose members are 
called {\em time points}\index{time points} which are integers in this paper
(except in a later part of the paper where the distinction will be made 
explicit);

\item  $<,+,-$ are as usual for integers.
\end{itemize}

Given a time structure ${\mathbf T}=\langle \mathbb{T},<,+,-\rangle $, a 
\emph{signature}\index{signature}  
$\sigma$\index{$\sigma$} with respect to ${\mathbf T}$ is a tuple
$ =\langle {\cal T},{\cal F},{\cal A}\rangle $, 
where ${\cal T}$\index{${\cal T}$} is a set of countably infinitely many 
{\em time-point variables}, ${\cal F}$\index{${\cal F}$} is a set of 
{\em propositional fluent names}, and ${\cal A}$\index{${\cal A}$} is a set of 
{\em action names}. Since the time structure ${\mathbf T}$ is fixed in the rest of this
paper, ${\mathbf T}$ will be taken implicitly whenever a signature is introduced. We
assume that all sets in $\sigma $ are countable. We denote 
${\cal F}^{*}\index{${\cal F}^*$}= \{[\neg] f \ |\ f\in {\cal F}\}$.\footnote{The notation
  $[\neg]$ means that the formula following it may, or may not, be negated.}
A member of ${\cal F}^{*}$ is a 
{\em fluent literal}. Moreover, ${\cal A}={\cal A}_0\cup {\cal DA}$\index{${\cal A}$}, where
${\cal A}_0$\index{${\cal A}_0$} is the set of domain dependent action names, 
called \emph{basic actions},
e.g. $load$, $shoot$, etc. and 
%
${\cal DA}\index{${\cal DA}$}=\{da_l \ |\ l \in {\cal F}^{*}\}$ is the set 
of \emph{dummy actions}. As will be explained later in this paper, our
solution to the problems of reasoning about action is based on the basic guideline
of attributing changes to events. Given the reasoner's ignorance about certain
events that bring about changes in the world, the dummy actions are to be used 
to make up for these gaps in the reasoner's belief state. That is why we need to
associate the dummy actions with the fluent literals from ${\cal F}^{*}$.

For each fluent literal $l \in {\cal F}^{*}$, we introduce the
following two symbols: $AQ_l$\index{$AQ_l$}, and $FA_l$\index{$FA_l$}: 
\begin{itemize}
\item $AQ_l$ is associated with the assumed qualifications upon the 
preconditions of an action regarding the fluent literal $l$. Essentially, 
$AQ_l$ when used in the description of the dynamics of an action $\alpha$
allows the reasoner to describe only the main preconditions of $\alpha$
(with regards to the fluent literal $l$) while leaving other possible 
(but less probable) qualifications to be rendered by a single assumption 
$AQ_l$.
\item $FA_l$ is associated with the frame assumptions regarding $l$. 
$FA_l$, when coupled with a particular \emph{frame inference rule},
allows the reasoner to infer that the fluent literal $l$ continues
to hold in future time points unless there is a reason that defeats
$FA_l$.
\end{itemize}
Given a set of fluent literals $%
\Gamma \subseteq {\cal F}^{*}$, we denote 
$FA_\Gamma \stackrel{def}{=}\{FA_l \ |\ l \in \Gamma \}$ and 
$AQ_\Gamma \stackrel{def}{=}\{AQ_l \ |\ l \in \Gamma \}$.\\[-1ex]

%% \newpage
A \emph{time-point expression} is one of the following:

\begin{itemize}
\item  a member of $\mathbb{T}$,

\item  a time-point variable in ${\cal T}$,

\item  an expression formed from time-point expressions using $+$ and $-$.
For convenience, we will also write $\tau ^{+}$\index{$\tau ^{+}$} 
and $\tau ^{-}$ instead of $\tau +1$ and $\tau -1$, respectively.
\end{itemize}

We denote the set of time-point expressions by ${\cal TE}$\index{${\cal TE}$}.

\begin{Def}
{\rm 
Let a signature $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be given 
and $\tau ,\upsilon \in {\cal TE}$, $f\in {\cal F}$,
$\alpha \in {\cal A}$, $R\in \{=,<\},$ $\otimes \in \{\wedge ,\vee
,\rightarrow ,\leftrightarrow \}$. Define the {\em basic (domain
description) language} $\Lambda $\index{$\Lambda $}\ over $\sigma $\ by:

$\Lambda_0 ::= \mathbf{true}\ |\ \mathbf{false}\ |\ f\ |\ \tau
R\upsilon \ |\ \neg \Lambda_0 \ |\ \Lambda_0\otimes \Lambda_0\ |\ [\tau ]\Lambda_0 $,

$\Lambda ::= \Lambda_0\ |\ [\tau ,\upsilon ]\alpha\ |\ \neg \Lambda \ |\ \Lambda\otimes \Lambda$\\
and the {\em assumption base}\index{assumption base} ${\cal AB}$\index{${\cal AB}$}\ by:

${\cal AB}={\cal AB}_{AQ}\cup {\cal AB}_{FA}$, where 

${\cal AB}_{AQ}=\{[\tau ,\upsilon ]AQ_l \ |\ \tau ,\upsilon \in {\cal TE}$\index{${\cal AB}_{AQ}$} and 
$l \in {\cal F}^{*}\}$, and 

${\cal AB}_{FA}=\{[\tau ]FA_l\ |\ \tau \in {\cal TE}$\index{${\cal AB}_{FA}$} and $l \in {\cal F}^{*}\}$.
}
\end{Def}

The {\em domain description language}\index{domain description language} 
${\cal L}_D$\index{${\cal L}_D$}\ (over $\sigma $) 
is defined: ${\cal L}_D=\Lambda \cup {\cal AB}$.\footnote{It would be more precise
to denote the domain description language over $\sigma$ by ${\cal L}_\sigma$.
However, as the signature is usually clear from the context and in order to
avoid the mention of $\sigma$ every time we have to formalise something
with the domain description language, we choose to denote it by ${\cal L}_D$.} \\[-1ex]

$[\tau ,\upsilon ]\alpha$\ means the action $\alpha$ has a duration corresponding
to the interval $[\tau ,\upsilon ]$. $[\tau ,\upsilon ]AQ_l$\ means the
fluent literal $l$ is assumed to be qualified to hold by the end of
the interval $[\tau ,\upsilon ]$. $[\tau ]FA_l$\ means the fluent
literal $l$ is assumed by default to persist from the time point 
$\tau $ to the next, i.e. the {\em principle of inertia}. Notice the difference 
between $[\tau ]FA_{l_1}$ and $[\tau]l_2$ for some fluent literals 
$l_1, l_2 \in {\cal F}^*$. $[\tau]l_2$ indicates that the fluent literal $l_2$ holds at
$\tau$ while $[\tau ]FA_{l_1}$ indicates that the fact that the fluent literal $l_1$ 
persists during the interval $[\tau, \tau^+]$ is true.

For example, in the blocks world domain, to say that block $A$ is on block $B$ at
the time point 2, we write: $[2]on(A,B)$; or, to say that an action $pickup$ 
the block
$A$ occurs between time points $t_1 + 3$ and $t_2 - 1$ and that the relation $<$
holds between $t_1 + 5$ and $t_2$, we write $[t_1 + 3, t_2 - 1]pickup(A) \wedge
(t_1 + 5 < t_2)$.

A formula that does not contain any connectives 
(i.e. $\wedge ,\vee,\rightarrow ,\leftrightarrow ,\neg ,$ and $[.]$) is 
{\em atomic}\index{formula!atomic}. If $%
\gamma $ is atomic and {\rm $\tau $}$\in {\cal TE}$, then the formulas 
$\gamma $, $[\tau ]\gamma $, $\neg \gamma $, $\neg [\tau]\gamma $, 
and $[\tau ]\neg \gamma $ are {\em literals}.

Let $\gamma $ be a formula. A fluent $f\in {\cal F}$ occurs {\em free} in $%
\gamma $ iff it does not occur within the scope of a $[\tau ]$ expression in 
$\gamma $. $\tau \in {\cal TE}$ {\em binds} $f$ in $\gamma $ if a formula $%
[\tau ]\psi $ occurs as a subformula of $\gamma $, and $f$ is free in $\psi$. 
If no fluent occurs free in $\gamma $, $\gamma \,$ is 
{\em closed}\index{formula!closed}. If $%
\gamma $ does not contain any occurrence of $[\tau ]$ for any $\tau \in 
{\cal TE}$, then $\gamma $ is {\em propositional}\index{formula!propositional}.

\subsection{Semantics}

\begin{Def}
{\rm Let }$\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle ${\rm \ be a
signature. A {\em state} over }$\sigma ${\rm \ is a function from }${\cal F}$%
{\rm \ to the set }$\{\mathbf{true},\mathbf{false} \}${\rm \ of truth values. 
A {\em %
history} over }$\sigma ${\rm \ is a function }$h$\index{$h$}{\rm \ from }$\mathbb{T}${\rm %
\ to the set of states. A {\em valuation} is a function }$\phi $\index{$\phi $}{\rm \ from }%
${\cal TE}${\rm \ to }$\mathbb{T}${\rm . A {\em narrative assignment} is a
function }$\eta $\index{$\eta $}{\rm \ from }$\mathbb{T}\times {\cal A}\times \mathbb{T}${\rm \
to the set }$\{\mathbf{true},\mathbf{false}\}${\rm . In addition, we define }$\varepsilon
_q:\mathbb{T}\times AQ_{{\cal F}^{*}}\times \mathbb{T}\rightarrow \{\mathbf{true},
\mathbf{false}\}$\index{$\varepsilon_q$}
{\rm \ and $\varepsilon _f:\mathbb{T}\times FA_{{\cal F}^{*}}\rightarrow
\{\mathbf{true},\mathbf{false} \}$\index{$\varepsilon_f$}. An 
\emph{interpretation}\index{interpretation}
over }$\sigma ${\rm \ is a tuple }$%
\langle h,\phi ,\eta ,\varepsilon _q,\varepsilon _f\rangle ${\rm \ where }$h$%
{\rm \ is a history, }$\phi ${\rm \ is a valuation, }$\eta ${\rm \ is a
narrative assignment and }$\varepsilon _q,\varepsilon _f${\rm \ are defined
as above.}
\end{Def}

\begin{Exa}\label{exa:4.1}
{\rm
Consider \citeS{HM87} Yale Shooting Problem (YSP) : There are three possible actions: $load$ 
(the gun), $wait$, and $shoot$ (the victim with the gun). Normally, waiting does not 
cause any change in the world, but shooting leads to the victim's death, provided 
that, of course, the gun is loaded.
Assume that all three actions are performed, in the given order.

We define the signature $\sigma_{\textsc{ysp}}$ to be a tuple 
$\langle \{ t, t_1, t_2, \ldots, u, u_1, u_2, \ldots \}, \{ loaded, alive\}, \{ load,$ 
$wait,$ $shoot \} \rangle$.
Then the Yale Shooting problem can be formulated in the domain description language
${\cal L}_{\textsc{ysp}}$ as the following theory: $\Gamma_{\textsc{ysp},0} = \{ [0]alive,\ 
[0,1]load,\ [1,2]wait,\ [2,3]shoot\}$.

%% ${\cal L}_{\textsc{ysp}}$ as the following theory $T_{\textsc{ysp},0}$:

%% \begin{eqnarray*}
%% alive[0]\\
%% load[0,1]\\
%% wait[1,2]\\
%% shoot[2,3]
%% \end{eqnarray*}

The following two histories $h_1$ and $h_2$ are corresponding to the well-known
models in the literature of reasoning about action: $h_1$ to the intended model and
$h_2$ to the anomalous model most frameworks would produce.

\begin{figure}[hbt]
\centerline{$h_1 \qquad$\psfig{figure=pictures/hist1.eps,height=2.5cm}}
\bigskip
\bigskip
\centerline{$h_2 \qquad$\psfig{figure=pictures/hist2.eps,height=2.5cm}}
\caption {The two histories for the YSP action description.
\label {fig:raa.1}}
\end{figure}

Each oval in Figure~\ref{fig:raa.1} represents a state over $\sigma_{\textsc{ysp}}$.
A narrative assignment complying with the above action description would map
the three tuples $(0, load, 1), (1, wait, 2)$, and $(2,shoot, 3)$ to $\mathbf{true}$
and other tuples to $\mathbf{false}$ (relative to the assumption that \emph{`normally,
given any action and any time point, there is no instance of that action at that
time point unless specified otherwise'}).

}
\end{Exa}

\begin{Def}
{\rm Let }$\gamma ,\delta \in \Lambda ${\rm \ and }$I=\langle h,\phi ,\eta
,\varepsilon _q,\varepsilon _f\rangle ${\rm \ an interpretation. Assume }$%
\tau ,\upsilon \in {\cal TE}${\rm , }$f\in {\cal F}${\rm , $A\in {\cal A}$, $%
R\in \{=,<\}$, $l \in {\cal F}^{*}$, }$\otimes \in \{\wedge ,\vee
,\rightarrow ,\leftrightarrow \}${\rm , and }$\chi \in \{\mathbf{true},\mathbf{false} \}$%
{\rm . Define the truth value of }$\gamma ${\rm \ in }$I${\rm \ for a
time point }$t\in \mathbb{T}${\rm , denoted }$I(\gamma ,t)${\rm \ as follows:}\\[-1ex]

\begin{tabular}{l@{\hspace{9ex}}l}
$I(\chi ,t)=\chi $ & $I(f,t)=h(t)(f)$ \\
$I([\tau ,\upsilon ]A,t)=\eta (\phi (\tau ),A,\phi (\upsilon ))$ &
$I([\tau ,\upsilon ]AQ_l ,t)=\varepsilon _q(\phi (\tau ),AQ_l,\phi (\upsilon ))$ \\
$I([\tau ]FA_l ,t)=\varepsilon _f(\phi (\tau ),FA_l)$ &
$I(\tau R\upsilon ,t)=\phi (\tau )R\phi (\upsilon )$ \\
$I(\neg \gamma ,t)=\neg I(\gamma ,t)$ &
$I(\gamma \otimes \delta ,t)=I(\gamma ,t)\otimes I(\delta ,t)$ \\
$I([\tau ]\gamma ,t)=I(\gamma ,\phi (\tau ))$\\[2ex]
\end{tabular}
%% $I(\chi ,t)=\chi $

%% $I(f,t)=h(t)(f)$

%% $I([\tau ,\upsilon ]A,t)=\eta (\phi (\tau ),A,\phi (\upsilon ))$

%% $I([\tau ,\upsilon ]AQ_l ,t)=\varepsilon _q(\phi (\tau ),AQ_l,\phi (\upsilon ))$

%% $I([\tau ]FA_l ,t)=\varepsilon _f(\phi (\tau ),FA_l)$

%% $I(\tau R\upsilon ,t)=\phi (\tau )R\phi (\upsilon )$

%% $I(\neg \gamma ,t)=\neg I(\gamma ,t)$

%% $I(\gamma \otimes \delta ,t)=I(\gamma ,t)\otimes I(\delta ,t)$

%% $I([\tau ]\gamma ,t)=I(\gamma ,\phi (\tau ))$

{\rm Two formulas }$\gamma ${\rm \ and }$\delta ${\rm \ are equivalent iff }$%
I(\gamma ,t)=I(\delta ,t)${\rm \ for all }$I${\rm \ and }$t${\rm . An
interpretation }$I${\rm \ is a {\em model} of a set }$\Gamma \subseteq
\Lambda ${\rm \ of formulas, denoted }$I\models \Gamma ${\rm , iff }$%
I(\gamma ,t)=${\rm \ $\mathbf{true}$ for every }$t\in \mathbb{T}${\rm \ and }$\gamma
\in \Gamma ${\rm . A formula }$\gamma \in \Lambda ${\rm \ is {\em entailed}
by a set }$\Gamma \subseteq \Lambda ${\rm \ of formulas, denoted }$\Gamma
\models \gamma ${\rm , iff }$\gamma ${\rm \ is true in all models of }$%
\Gamma ${\rm .}
\end{Def}

%% \begin{Def}
%% {\rm Let $I=\langle h,\phi ,\eta ,\varepsilon _q,\varepsilon _f\rangle $\ be
%% an interpretation. The set $Occ^I=\{(t,A,u)\in \mathbb{T}\times {\cal A}\times 
%% \mathbb{T}$ $|$ }$\eta (${\rm $t,A,u)=\mathbf{true}\}$ is called {\em action
%% occurrence denotation} of }$I${\rm . The set $FA^I=\{(t,FA_l )\in 
%% \mathbb{T}\times FA_{{\cal F}^{*}}$ $|$ }$\varepsilon _f(${\rm $t,FA_l )=%
%% \mathbf{true}\}$ is called }$FA${\rm -{\em denotation} of }$I${\rm . The set $%
%% AQ^I=\{(t,AQ_l ,u)\in \mathbb{T}\times AQ_{{\cal F}^{*}}\times \mathbb{T}$ 
%% $|$ }$\varepsilon _q(${\rm $t,AQ_l ,u)=\mathbf{true}\}$ is called }$AQ${\rm -%
%% {\em denotation} of }$I${\rm .} %\hfill$\blacksquare $
%% \end{Def}

\begin{Def}
{\rm Let $I=\langle h,\phi ,\eta ,\varepsilon _q,\varepsilon _f\rangle $\ be
an interpretation. }
\begin{enumerate}
\item {\rm The set $Occ^I=\{(t,A,u)\in \mathbb{T}\times {\cal A}\times 
\mathbb{T}$ $|$ }$\eta (${\rm $t,A,u)=\mathbf{true}\}$\index{$Occ^I$} is called {\em action
occurrence denotation} of }$I$.
\item {\rm The set $FA^I=\{(t,FA_l )\in 
\mathbb{T}\times FA_{{\cal F}^{*}}$ $|$ }$\varepsilon _f(${\rm $t,FA_l )=%
\mathbf{true}\}$\index{$FA^I$} is called }$FA${\rm -{\em denotation} of }$I$.
\item {\rm The set $%
AQ^I=\{(t,AQ_l ,u)\in \mathbb{T}\times AQ_{{\cal F}^{*}}\times \mathbb{T}$ 
$|$ }$\varepsilon _q(${\rm $t,AQ_l ,u)=\mathbf{true}\}$\index{$AQ^I$} is 
called }$AQ${\rm -{\em denotation} of }$I${\rm .} %\hfill$\blacksquare $
\end{enumerate}
\end{Def}

\section{Representing Dynamic Domains in the Argumentation-Theoretic Approach}

We now proceed to showing an assumption-based framework for representing
dynamic domains. We subsequently introduce a uniform framework for solving
the frame and the qualification problems based on the argumentation-theoretic 
approach. General solutions for the frame and the qualification problems
can be obtained by computing plausible sets of assumptions which guarantee
that extensions computed from these sets of assumptions will be
consistent when the given theory is consistent. We now introduce some 
additional notations: Given an
inference rule $r \in {\cal R}$, we denote by $prem(r)$ and $cons(r)$ the premise and the
  consequence of rule $r$, respectively.

\begin{Def}
{\rm A deductive system $\langle {\cal L}_D,{\cal R}\rangle $ is \emph{well-defined} iff
  for each subset $S\subseteq {\cal R}$, if the set $\bigcup_{r\in S}prem(r)$ is
  consistent then the set $CONS(S)=\{cons(r)\ |\ r\in S\}$ is also consistent. 
}
\end{Def}

Henceforth, we will assume that deductive systems are well-defined. Being
formalised in terms of the argumentation-theoretic approach, the
representation requires an extended notion of consistency.

\begin{Def}
{\rm Let }$\langle {\cal L}_D,{\cal R}\rangle ${\rm \ be a deductive system,}
\begin{enumerate}
\item[{\rm (i)}] {\rm a set of sentences }$\Gamma \subseteq {\cal L}_D${\rm \ is }${\cal R}${\rm %
-{\em consistent}\index{${\cal R}$-consistent} iff }$\Gamma \not \vdash _{{\cal R}}\mathbf{false}$;
\item[{\rm (ii)}]{\rm an
assumption-based framework }$\langle \Gamma, {\cal AB} \rangle ${\rm \ with respect
to }$\langle {\cal L}_D,{\cal R}\rangle ${\rm \ is {\em consistent} iff }$\Gamma$%
{\rm \ is }${\cal R}${\rm -consistent.} %\hfill$\blacksquare $
\end{enumerate}
\end{Def}

\noindent
\textsc{Remark:} Observe that even when $\langle {\cal L}_D,{\cal R}\rangle $
is a well-defined deductive system, consistency is not equivalent to 
$\cal R$-consistency. For instance, let $\displaystyle {\cal R} = \{ \frac{b}{\neg a} \}$,
the (logically) consistent theory $\Gamma = \{ a, b \}$ is not $\cal R$-consistent.\\


\begin{aExa}{\bf\ \ref{exa:4.1}} 
{\rm ({\em continued})
Returning to the Yale Shooting problem, the following inference rules describe the
actions of this domain:

\begin{gather}
\frac{[\tau ,\upsilon ]load}
{ [\upsilon]loaded \wedge \neg [\tau]FA_{\neg loaded} }\label{eq:raa.1}
\end{gather}
\begin{gather}
\frac{[\tau ,\upsilon ]shoot, [\tau ]loaded}
{\neg [\upsilon]alive \wedge \neg [\tau ]FA_{alive}}\label{eq:raa.2}
\end{gather}
\begin{gather}
\frac{[\tau ]loaded,[\tau ]FA_{loaded}}{[\tau ^{+}]loaded}\label{eq:raa.f1}
\end{gather}
\begin{gather}
\frac{[\tau]alive,[\tau ]FA_{alive}}{[\tau ^{+}]alive} \label{eq:raa.f2}
\end{gather}
\begin{gather}
\frac{\neg [\tau]loaded,[\tau ]FA_{\neg loaded}}{\neg [\tau ^{+}]loaded}\label{eq:raa.f3}
\end{gather}
\begin{gather}
\frac{\neg [\tau]alive,[\tau ]FA_{\neg alive}}{\neg [\tau ^{+}]alive}\label{eq:raa.f4}
\end{gather}

Rules (\ref{eq:raa.1}) and (\ref{eq:raa.2}) represent the descriptions of the 
actions $load$ and $shoot$, respectively. Action $wait$ does not cause any
effect to the world, so there is no need to describe it. Other rules render the
common sense law of inertia: \emph{``at any time point, a fluent literal presumably 
persists to the next time point.''}\\[-1.5ex]
}
\end{aExa}

Most argumentation-theoretic semantics, e.g. stability, admissibility,
preferability, complete, well-founded semantics, etc. \cite{BDK97} are based
on the notion of attack. However, to reason about problem domains with
incomplete information, especially action domains, this notion alone may
not be sufficient as we may not always be able to construct explicit
arguments to defeat unsound assumptions. For example, consider the Yale
Shooting Problem: By observing that a turkey is shot with a loaded gun
at time point 1, the reasoner infers plausibly that the turkey is dead at
time point 2 using the assumption that the action shoot is qualified to
bring about the effect of killing the victim. However, at time point 2, the
reasoner could observe that the turkey is still alive. Existing solutions to
%% the frame problem, e.g. Reiter's \cite{Rei91}, Thielscher's \cite{Thi97},
%% Castilho {\em et al}.'s \cite{Cas99}, etc. fail to deal with such a surprise
the frame problem, e.g. \citeS{Rei91}, \citeS{Thi97},
\citeS{Cas99}, etc. fail to deal with such a surprise
since they allow a contradiction to be derived. Observe that the reasoner does not have
any explicit reason to defeat the above qualification assumption, i.e. she is not
aware of any cause that prevents the application of this qualification assumption. She only
knows that it is not acceptable in this case by common sense. To formalise
such phenomena, we introduce the notion of rejected assumptions.

\begin{Def}
{\rm 
Given an assumption-based framework $\langle \Gamma, {\cal AB} \rangle $, a set
of assumptions $\Delta \subseteq {\cal AB}$ \emph{rejects}\index{reject} an assumption $\delta \in
{\cal AB}$ iff

(a) $\Delta$ is conflict-free, and 

(b) $\Delta \cup \{\delta \}$ attacks itself. 
}
\end{Def}

For instance, in example~\ref{exa:4.1}, the set of assumptions $\Delta_1 = 
\{ [0]FA_{alive}, [1]FA_{alive}, [1]FA_{loaded} \}$ attacks the assumption
$[2]FA_{alive}$.\footnote{In fact, any set of assumptions containing the 
assumption $[1]FA_{loaded}$ would attack $[2]FA_{alive}$.} Moreover, relative
to the given action description, any set of assumptions attacks the assumption
$[0]FA_{\neg loaded}$. On the other hand, the set of assumptions $\Delta_2 = 
\{ [0]FA_{alive}, [1]FA_{alive}, [2]FA_{alive} \}$ rejects the assumption
$[1]FA_{loaded}$ but $\Delta_2$ does {\bf not} attack it.

\begin{Obs}
\label{ob1}Given an assumption-based framework $\langle \Gamma , {\cal AB} \rangle $
and a conflict-free set of assumptions $\Delta \subseteq {\cal AB}$, if $\Delta $ 
attacks an
assumption $\delta \notin \Delta $ then $\Delta $ rejects $\delta$.
\end{Obs}

Then, why do we not generalise the contrariness notion of an assumption so
that it would be general enough to account for all rejected assumptions? The
reason is because we want to isolate the set of assumptions that are
rejected but are not attacked as part of our solution to the frame problem.

\begin{Def}
{\rm Given an assumption-based framework $\langle \Gamma, {\cal AB} \rangle $, a set
of assumptions $\Delta \subseteq {\cal AB}$ 
\emph{leniently rejects}\index{reject!leniently} an assumption 
$\delta \in {\cal AB}$ iff }

{\rm (a) $\Delta $ rejects $\delta$, and }

{\rm (b) $\Delta $ does not attack $\delta$. }
\end{Def}

We denote $Lr(\Delta )\index{$Lr$}\stackrel{def}{=}\{\delta \in {\cal AB}\ |\ \delta$ is
leniently rejected by $\Delta \}$.\\[-1.5ex]

To show that our solution provides an intuitive account for problems of
reasoning about action, several scenarios should be considered. These include
the projection problem, the most basic form of the frame problem, whose
typical example is the infamous YSP. Another scenario concerns with the
explanation problem which are usually discussed with the Stolen Car Problem \cite{Kau86}
and the Stanford Murder Mystery \cite{Bak89}. We will first provide an informal
discussion of our approach through these examples.

In the present solution, the frame assumptions are the essence of the
principle of inertia,%
%By default we will assume
%that a fluent persists over time unless there is evidence to believe
%otherwise.  
and their role in the argumentation
approach is illustrated below by the Yale Shooting Problem. In
this formulation we intentionally ignore the qualification problem (it is
addressed in the next section) to highlight how the frame problem is solved.
We now reconsider the well-worn example YSP to motivate our approach to the frame 
problem.\\[-1.5ex]

\begin{aExa}{\bf\ \ref{exa:4.1}}
{\rm ({\em continued})
Given the theory $\Gamma_{\textsc{ysp}}$, the
argumentation-theoretic approach will yield the following preferred set of
assumptions \cite{BDK97}:

$\{[t]FA_l \ |\ t \in \mathbb{T}$ and $l \in
\{loaded,alive,\neg loaded,\neg alive\}\}\setminus \{[0]FA_{\neg
loaded},[2]FA_{alive}\}$,\\ which corresponds to the intended model of this
scenario in which the gun remains loaded at time point 2 and the victim is not
alive at time point 3. %\\[-1.5ex]

This extension is also the stable extension and well-founded semantics
\cite{BDK97} of the given theory under the argumentation-theoretic
approach. Note that in case one would like to be uncertain about whether the
gun is still loaded after the shooting action, one just simply needs to add
an axiom: $[\tau ,\upsilon ]shoot\rightarrow \neg [\tau ]FA_{loaded}$ to
dictate that the persistence of the fluent $loaded$ after the action
shooting is not guaranteed. In that case, we can still derive that $[\tau
]loaded$ for $\tau =1,2$, but we can no longer give a definite assertion
about $[\tau ]loaded$ for $\tau \geq 3$. \\[-1.5ex]
%\hfill$\square $
}
\end{aExa}

As the above formalisation of YSP resembles that using default logic, it may
be surprising that the problem of unintended models pointed out by \citeA{HM87} for
%% be surprising that the problem of unintended models pointed out by Hanks and McDermott for
circumscription, default logic, autoepistemic logic does not 
happen here. The principal reason is the interaction of the inference rules
and the notion of attack in the argumentation-theoretic framework, which
invalidates undesired assumptions. Notice that even if $\neg [2]loaded$ can
be (magically) derived, it cannot lead to $\neg [1]FA_{loaded}$. Therefore,
the set of assumptions corresponding to this case does not satisfy the
conditions of preferred set of assumptions, thus ruling out this unintended
model. This shows one of the important features of assumption-based
frameworks on its capability of making explicit the assumptions used by the
reasoner during the course of inference. Recall that defaults'
justifications are accepted as long as they are consistent with some
extension for credulous semantics or all extensions for skeptical semantics
(thus the name consistency-based approach.) In light of the inertia
principle, it's considered to be abnormal if a fluent does not persist from
a state to the next state. To minimise the abnormality, (normal) default
rules are introduced to express the fact that if it's consistent to believe
that there is no abnormality with respect to a fluent $f$ and an action $a$
in a situation $s$ then assert that. But then we would fail to distinguish
between the abnormalities brought about by reasonable causes and those
unintuitively generated to make them consistent with some possible
extension. The latter is of course corresponding to the anomalous models. By
using explicit assumptions, not only consistency is maintained (by
preventing the accepted assumptions from attacking themselves) but each
rejection of assumptions must also be justified by the known facts from the
given theory.%\\[1.5ex]

\subsection*{Discussion:}
\begin{enumerate}
\item \citeA{Tur97} showed that an alternative representation of the 
YSP in default logic  
can help solve the issue of anomalous models introduced by \citeS{HM87} 
representation. 
Turner formulates the Yale Shooting scenario as follows:
%% Recently, Turner \cite{Tur97} showed that an alternative representation of
%% the YSP in default logic 
%% can help to solve the issue of anomalous models introduced by Hank
%% and McDermott's \cite{HM87} representation. 
%% Turner formulates the Yale Shooting scenario as follows:

\begin{gather}
\frac{\neg Holds (Alive, S_0)}
{ \mathbf{False} }\label{eq:raa.T1}
\end{gather}
\begin{gather}
\frac{\mathbf{True}}
{ Holds(Loaded, Result(Load, s))}\label{eq:raa.T2}
\end{gather}
\begin{gather}
\frac{Holds(Loaded, s)}
{ \neg Holds(Alive, Result(Shoot, s)) }\label{eq:raa.T3} %\\
\end{gather}
\begin{gather}
\frac{:\ Holds(f,S_0)}
{Holds(f,S_0)} \label{eq:raa.T4} 
\end{gather}
\begin{gather}
\frac{:\ \neg Holds(f,S_0)}
{ \neg Holds(f,S_0)} \label{eq:raa.T5}
\end{gather}
\begin{gather}
\frac{Holds(f,s):\ Holds(f, Result(a, s))}
{ Holds(f, Result(a, s)) } \label{eq:raa.T6}
\end{gather}
\begin{gather}
\frac{ \neg Holds(f,s):\ \neg Holds(f, Result(a, s))}
{ \neg Holds(f, Result(a, s)) } \label{eq:raa.T7}
\end{gather}

Notice that Turner also uses the inference rules to block the ``backward'' reasoning
that generates the anomalous models of the Yale Shooting scenario. However, this 
also means that all kinds of useful backward reasoning will also be blocked. 
In other words, Turner's formulation fails to deal with ``surprising'' observations
about states at later time points. As a consequence, Turner's
formulation only works when the domain is restricted to qualification-free.
As soon as the action descriptions, e.g. the one for the shoot action in
YSP, need to rely on some default justifications, e.g. qualification
assumptions, Turner's formulation would also encounter the problem of
undesirable extensions. Our approach offers solutions to both of the above
issues. 
\item After \citeS{HM87} seminal paper in which early approaches to the frame 
problems were exposed, besides new attempts to solve the frame problem, 
\citeA{San94} should be accredited as the first who tried to approach
the problems of reasoning about action in a systematic way. As part of this
effort, he also examines the reason behind the failure of early approaches 
to the frame problem. As discussed by Sandewall, early approaches to reasoning
about action while attempting to formulate the inertia principle have made
the common mistake of making changes the abnormality regarding this 
principle but failing to distinguish between normal changes triggered
by actions and anomalous changes. This important insight turns out to be
a consequence of a much more general law for reasoning about dynamic 
domains discovered by researchers in the community in pursuit of solutions
to various problems of reasoning about actions: 
\emph{``action dynamics are causality-based.''}
It is this principle that underpins most solutions to the problems of
reasoning about action. The anomalous models that arise in early approaches
to the frame problem discovered by \citeA{HM87} or to the qualification
problem as discussed by \citeA{thielscher01qualification} are those
in which the \emph{causes} of abnormalities are not present. On the other
hand, regarding the ramification problem, given a domain constraint involving
a number of fluents, it's important to know which of these fluents are the 
causes influencing the other fluents, i.e. the \emph{causality direction}
between the involved fluents.

In light of the above analysis, \citeS{Tur97} approach appears to be rather
ad hoc. Note that Turner's solution to the problem of anomalous models
is to block ``backward reasoning'' by the use of inference rules without
any motivation on why backward reasoning is a bad thing. While his 
approach appears to share with solutions based on \emph{chronological
ignorance} (which will be discussed in more details in 
Section~\ref{sec:conc}) the notion of directedness: By minimizing
chronologically or blocking backward reasoning, one tends to minimize 
causes rather than effects. However, a more systematic approach
to various problems of reasoning about action is still very much 
desired.
\end{enumerate}

Nevertheless, while the preferability semantics copes successfully with the
YSP, it can not properly account for the explanation problem, e.g. the
Stanford Murder Mystery \cite{Bak89}, the Stolen Car Problem \cite{Kau86}. 
The subtlety lies in the
derivation of the contrary of the frame assumptions. The
contrary of a frame assumption is derived only when both the occurrence of
the event that brings about the change (absent in the Stolen Car Problem)
and the preconditions required to be satisfied for the change to actually
take place (absent in the Stanford Murder Mystery) are explicitly derivable.
This is where the notion of (leniently) rejected assumptions is called into
service.

\begin{Def}
{\rm 
Given an assumption-based framework $FA=$$\langle \Gamma, {\cal AB} \rangle $, 
a set of assumptions $\Delta \subseteq {\cal AB}$ is {\em presumable
wrt }\index{set of assumptions!presumable}
$FA$ iff 
}

{\rm (a) $\Delta =\{\delta \in {\cal AB}\ |\ \Gamma \cup \Delta \vdash _{{\cal R}}
\delta \}$\ (in the terms given in \citeR{BDK97}, $\Delta $\ is closed), 
}

{\rm (b) }$\Delta ${\rm \ does not attack itself, and }

{\rm (c) for each assumption }$\delta \not \in \Delta ${\rm , }$\delta ${\rm %
\ is rejected by }$\Delta ${\rm .} %\hfill$\blacksquare $
\end{Def}

\begin{Def}
{\rm Given an assumption-based framework $FA=$}$\langle \Gamma, {\cal AB} \rangle $%
{\rm , a set of assumptions }$\Delta \subseteq {\cal AB}${\rm \ is {\em plausible
wrt }\index{set of assumptions!plausible}$FA$ iff }

{\rm (a) }$\Delta ${\rm \ is presumable, and }

{\rm (b) there exists no }$\Delta ^{\prime }\subseteq {\cal AB}${\rm \ such that }$%
\Delta ^{\prime }${\rm \ is presumable and }$Lr(\Delta ^{\prime })${\rm \ }$%
\subset Lr(\Delta )${\rm .} % \hfill$\blacksquare $
\end{Def}

We now proceed to formalising action theories in our framework. 

\begin{Def}
{\rm 
Let $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be a
signature. Assume $\tau ,\upsilon \in {\cal TE}$, $\alpha \in {\cal A}$, 
$\Phi \subseteq \Lambda $, and $l \in {\cal F}^{*}$. A 
\emph{domain description} $D$\ (over $\sigma$) is a tuple 
$\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $, where:

\begin{enumerate}
\item  ${\cal L}_D$\ is the domain description language and ${\cal AB}$ is
\ an assumption base over $\sigma $;

\item  ${\cal R}={\cal R}_C\cup {\cal R}_F\cup {\cal R}_A\cup {\cal R}_Q$, where 

\begin{enumerate}
\item  ${\cal R}_C$\index{${\cal R}_C$}\ is the set of inference rules of (classical)
propositional logic;

\item ${\cal R}_F$\index{${\cal R}_F$}\ is the set of {\em frame-based inference rules}
of the form: $\displaystyle
\frac{[\tau ]l ,[\tau ]FA_l }{[\tau ^{+}]l }, $
i.e. those that represent the frame axioms in terms of inference rules; 

\item ${\cal R}_A$\index{${\cal R}_A$}\ is the set of {\em action descriptions} which
are inference rules of the form: $\displaystyle
\frac{\Phi ,[\tau ,\upsilon ]\alpha,[\tau ,\upsilon ]AQ_l }
{[\upsilon]l \wedge \neg [\tau ]FA_{\neg l }},$\ i.e. those that 
represent the conditions for the action $\alpha$  to bring about $l$; and

\item ${\cal R}_Q$\index{${\cal R}_Q$}\ is the set of {\em qualification-based
inference rules} of the form: $\displaystyle
\frac \Phi {\neg [\tau ,\upsilon ]AQ_l },$
i.e. those that represent the qualifications regarding the fluent
literal $l$.
\end{enumerate}

\item  The theory $\Gamma \subseteq \Lambda $. %\hfill$\blacksquare $
\end{enumerate}
}
\end{Def}

Given a set of assumptions $\Delta $, we denote $\Delta _{FA}=\Delta \cap 
{\cal AB}_{FA}$ and $\Delta _{AQ}=\Delta \cap {\cal AB}_{AQ}$.

\begin{Obs}
\label{ob2}Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $\ be a
domain description, for each set of assumptions $\Delta \subseteq {\cal AB}$, either
$\Delta $  is closed or $\Delta $ attacks itself.
\end{Obs}



\section{Reasoning about Action: The Frame and the Qualification Problems}

In general, we adopt the following guidelines in seeking a uniform solution to 
the problems of reasoning about action:

\begin{itemize}
\item  The derived pieces of information do not conflict with the given facts;

\item  Occurrences of events are minimised; and

\item  The inertia of fluents is maximised though the minimality of the
event occurrences will be of higher priority.
\end{itemize}

Aside from the trivial case of occurrences of actions causing the frame
assumptions to be rejected, two aspects of actions can be distinguished:

\begin{enumerate}
\item An action happens but the change it is supposed to cause does not take
place. We call this {\em expectation failure} and this is more or less the
qualification problem; and

\item No actions that are known to have happened and caused a change but the 
change did
take place. We call this {\em surprise} and this is usually known as the
explanation problem.
\end{enumerate}

The following assumption represents our underlying intuition behind
reasoning about action formalisms.

\begin{Ass}
Intuitive models contain minimal (with respect to set inclusion) sets of
surprises. %\hfill$\square $
\end{Ass}

Now we introduce some model-theoretic counterpart notions of the
assumption-based notions presented above.

\begin{Def}
{\rm 
Let $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be a 
signature
and $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $\ a domain
description over $\sigma $. An interpretation $I=\langle h,\phi ,\eta
,\varepsilon _q,\varepsilon _f\rangle $\ is a {\em model}\index{model} of $D$\ iff

\begin{enumerate}
\item  $I$\ is a model of $\Gamma $;

\item  for each $r\in {\cal R}$, if $I\models prem(r)$\ then $I\models cons(r)$. %\hfill$\blacksquare $
\end{enumerate}
}
\end{Def}

The following definition captures one of several aspects of the
(model-theoretic) solution of the frame problem. This aspect is known as the
action-oriented frame problem in \citeS{LS95} terms. The proposed
% action-oriented frame problem in Lin and Shoham's (\cite{LS95}) terms. The proposed
minimisation policy formalises the intuition that change does not happen by
itself but is caused by some kind of event. Thus, for each fluent, if its
value is changed between two timepoints $\tau $ and $\upsilon $, (at least)
an occurrence of some event must end at $\upsilon $ that brings about that
change.

\begin{Def}
{\rm 
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $\ be a
domain description and $I$\ a model of $D$. $I$\ is a 
{\em coherent model}\index{model!coherent} of $D$\ iff

\begin{enumerate}
\item  for each basic action $\alpha \in {\cal A}_0$ and $\tau
,\upsilon \in {\cal TE}$, if $I \models [\tau ,\upsilon ]\alpha$
then $\Gamma \models [\tau ,\upsilon]\alpha$ ; and

\item  for each $l \in {\cal F}^{*}$ and $t \in \mathbb{T}$, 
if $I\models [t]l \wedge \neg [t^{+}]l $
then either 
\begin{enumerate}
\item there are $\alpha\in {\cal A}_0$\ and $s \in \mathbb{T}$ such that
$\displaystyle
r=\frac{\Phi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\neg l }}
{\neg [\tau_2]l \wedge \neg [\tau_1]FA_l} \in {\cal R}
$ and \\
$I\models prem(r)[\tau_1/s, \tau_2/t^{+}]$,\footnote{The notation 
$\varphi[v_1/t_1,\ldots,v_n/t_n]$ is standard in logic and meant to be the 
instantiation of the formula $\varphi$ with the variables $v_1,\ldots,v_n$
being replaced by the terms $t_1,\ldots,t_n$, respectively.}  or 
\item $I\models [t ,t^{+}]da_{\neg l }$
% \hfill$\blacksquare $
\end{enumerate}

\end{enumerate}
}
\end{Def}

Thus, in a coherent model: (i) all satisfiable basic actions must follow from
the given theory, and (ii) all changes are attributable to events of one kind or another.

Given an interpretation $I$, we want to extract the sets of assumptions
satisfiable in $I$.

\begin{Def}\label{df16}
{\rm 
Let $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be
a signature and $I$\ an interpretation over $\sigma $. The set of frame
assumptions satisfiable in $I$, denoted $\Delta _{FA}^I$, is
defined as follows: \[\Delta _{FA}^I=\{[t]FA_l \ |\ (t ,FA_l)\in FA^I \}\] and 
the set of qualification assumptions satisfiable in $I$, denoted 
$\Delta _{AQ}^I$, is : \[\Delta _{AQ}^I=\{[t_1,t_2]AQ_l \ |\ (t_1,AQ_l ,t_2)\in AQ^I\}\]
We also write $\Delta_{QF}^I=\Delta _{AQ}^I\cup \Delta _{FA}^I$.
% \hfill$\blacksquare $
}
\end{Def}

Conversely, given a theory $\Gamma $ and a set of assumptions $\Delta $, a
reasoner can also construct his models about the domain of interest.

\begin{Def}
\label{df17}
{\rm 
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle$
be a domain description and $\Delta \subseteq {\cal AB}$. A
model $I=\langle h,\phi ,\eta ,\varepsilon _q,\varepsilon_f\rangle$ 
of $D$ is $\Delta $-{\em relativised}\index{$\Delta $-relativised} iff

\begin{enumerate}
\item  for each $\delta \in {\cal AB}$, $I\models \delta $\
iff $\delta \in \Delta $; and

\item  $Occ^I=OA_D\cup DAS(\Delta)$, where: 
\begin{enumerate}
\item  $OA_D=\{(\phi(\tau_1),\alpha,\phi(\tau_2))\in 
\mathbb{T}\times {\cal A}_0\times \mathbb{T}\ |\ \Gamma \models
[\tau_1,\tau_2]\alpha\}$, and 
\item $DAS(\Delta )=\{(t,da_{\neg l },t^{+})\in 
\mathbb{T}\times {\cal DA}\times \mathbb{T}\ |\ [t]FA_l
\notin \Delta $\ and there do not exist any action \\$\alpha \in {\cal A}_0$
and $s \in \mathbb{T}$
such that 
$\displaystyle
r=\frac{\Phi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\neg l }}
{\neg [\tau_2]l \wedge \neg [\tau_1]FA_l} \in {\cal R}
$  and 
$I\models prem(r)[\tau_1/s, \tau_2/t^{+}] \}$.  % \hfill$\blacksquare $
\end{enumerate}
\end{enumerate}
}
\end{Def}

$\Delta$-relativised models are one of the central notions of our framework.
Essentially, assumptions underpin our machinery to conjecture information based
on common sense knowledge. As such, we will try to accept as many assumption as
possible unless there is a good reason not to. Therefore, given a set of 
assumptions, we will attribute every missing frame assumption to a possible change
in the domain the agent is reasoning about which is caused by either a known
action/event or some unknown action, called dummy actions in this paper.

The following observation is immediate from condition (1.) in the above definition.

\begin{Obs}
Let a domain description $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle$
and a set of assumptions $\Delta \subseteq {\cal AB}$
be given. If the model $I$ of $D$ is $\Delta $-relativised then
$\Delta^I_{QF} = I(\Delta, t)$ for every $t \in \mathbb{T}$.
\end{Obs}

\subsection{The Frame Problem}

First we will address the frame problem in a simple setting {\em viz.} without
qualification assumptions, but we will lift the restrictions later.

\begin{Def}
{\rm 
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $\ be a
domain description. $D$\ is a \emph{simple domain description}\index{simple domain description}, or {\em %
S-domain}\index{S-domain|see{simple domain description}}, iff ${\cal R}_Q=\emptyset $\ and $AQ$\ does not occur
anywhere in ${\cal R}$\ or $\Gamma $.  % \hfill$\blacksquare $
}
\end{Def}

\begin{Def}
{\rm 
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $\ a
domain description. An interpretation $I=\langle h,\phi ,\eta ,\varepsilon
_q,\varepsilon _f\rangle $\ is a \emph{simple model}\index{model!simple}, or 
{\em S-model}\index{S-model|see{simple model}}, of $D$\ iff
\begin{enumerate}
\item  $I$\ is a model of $D$; and
\item $\varepsilon _q(t,AQ_l ,u)=\mathbf{true}$ for every $(t,AQ_l
,u)\in \mathbb{T}\times AQ_{{\cal F}^{*}}\times \mathbb{T}$.
% \hfill$\blacksquare $
\end{enumerate}
}
\end{Def}

This effectively isolates the frame problem from the qualification problem.
Note also that if $I$ is an S-model then $\Delta _{AQ}^I={\cal AB}_{AQ}$. A 
{\em coherent S-model}\index{S-model!coherent} is an S-model which is coherent.\\[-1.5ex]

\begin{aExa}{\bf \ \ref{exa:4.1}}
{\rm
({\em continued}.) The following is part of one of the coherent models
of $D_{\textsc{ysp}}$:

$\{[0,1]load,\neg [0]loaded,[1]loaded,[0]alive,[1]alive,$

$[1,2]wait,[1,2]da_{\neg loaded},\neg [2]loaded,[2]alive,$

$[2,3]shoot,\neg [3]loaded,[3]alive\}$,\\which corresponds to one of the
anomalous models of this scenario (the one pointed out by Hanks and
McDermott).\\[-1ex] % \hfill$\square $
}
\end{aExa}

But it is not desirable to admit the occurrence of an event when there is no
evidence for it. Thus we need to minimise the set of action occurrences in a
given action theory.

\begin{Def}
{\rm 
Let $D$\ be an S-domain. A coherent S-model $I$\ of $D$\ is a 
\emph{prioritised minimal model}\index{model!prioritised minimal} (or simply 
{\em PMM}\index{PMM|see{prioritised minimal model}}) of $D$\ iff there 
does not exist any coherent S-model 
$I^{\prime }$\ of $D$\ such that $Occ^{I^{\prime }}\subset Occ^I$.
% \hfill$\blacksquare $
}
\end{Def}

Note that the above model-theoretic minimisation policy is not based on the
frame assumptions. This solution to the frame problem is thus amenable to
well-known techniques such as circumscription\footnote{%
in combination with the introduction of occurrences of dummy actions.}, but
we believe an argumentation-theoretic approach is not only more direct but also
has wider applicability. In order to provide the connection between the above
(model-theoretic) minimisation policy and the (argumentation-theoretic) notion
of plausible sets of assumptions we need to maximise the set of assumptions
satisfiable in a PMM.

\begin{Def}
{\rm 
Let $D$\ be an S-domain. A PMM $I$\ of $D$\ is a 
\emph{canonical prioritised minimal model}\index{model!canonical prioritised minimal} 
(or simply {\em CPMM}\index{CPMM|see{canonical prioritised minimal model}}) 
of $D$\ iff there does not exist any PMM $I^{\prime }$\ of $D$
\ such that $FA^I\subset FA^{I^{\prime }}$.
% \hfill$\blacksquare $
}
\end{Def}

We now want to see how the account of plausible sets of assumptions connects
to this account of minimality.

\begin{Lem}
\label{le1}Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
S-domain. If $I$ is a CPMM of $D$ then for each assumption $\delta \in {\cal %
AB}$: $\delta \notin \Delta _{QF}^I$ iff $\delta $ is rejected by $\Delta
_{QF}^I$.
\end{Lem}
{\em Proof}. ($\Rightarrow $) Suppose by way of contradiction that $\delta $
is not rejected by $\Delta _{QF}^I$, then $\Delta _{QF}^I\cup \{\delta \}$
is ${\cal R}$-consistent, i.e. $\Gamma \cup $ $\Delta _{QF}^I\cup $ $%
\{\delta \}\not \vdash _{{\cal R}} {\mathbf{false}}$. Since $D$ is an S-domain, 
${\cal AB}_{AQ}\subseteq \Delta _{QF}^I$. 
Assume that $\delta =[\tau ]FA_l$
for some $\tau \in {\cal TE}$ and $l \in {\cal F}^{*}$, we can
construct an interpretation $I^{\prime }$ in such a way that $I^{\prime }$
interprets everything except $FA$ the same as $I$ and 
$FA^{I^{\prime}}=FA^I\cup \{(\phi (\tau ),FA_l)\}$.

Since $I$ is a PMM of $D$, from the above construction, $I^{\prime }$ is
also a PMM of $D$. But $FA^I\subset FA^{I^{\prime }}$. Contradiction.\\[1ex]
($\Leftarrow $) Obvious.\hfill$\Box$

\begin{Lem}
\label{le2}Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
S-domain and $I$ a CPMM of $D$. If there are $t \in \mathbb{T}$ and 
$l \in {\cal F}^*$ such that $[t]FA_l \in Lr(\Delta_{QF}^I)$ 
then $I\models [t,t^{+}]da_{\neg l}$.
\end{Lem}
{\em Proof}. Let $\delta$ denote the assumption $[t]FA_l$.
First we observe that $\delta \in Lr(\Delta _{QF}^I)$ implies 
$\delta \not \in \Delta _{QF}^I$ since $\delta $ is rejected by 
$\Delta_{QF}^I$ 
and $\Delta _{QF}^I$ does not attack itself. This in turn implies
that $I\models \{[t]l ,\neg [t^{+}]l\}$ as the denotation
of $FA$ in $I$ is required to be maximal since $I$ is a CPMM of $D$. From
the condition that $I$ is coherent, 
either (i) there are $\alpha\in {\cal A}_0$\ and $s \in \mathbb{T}$
such that
\[
r=\frac{\Phi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\neg l }}
{\neg [\tau_2]l \wedge \neg [\tau_1]FA_l} \in {\cal R}
\] 
and 
$I\models prem(r)[\tau_1/s, \tau_2/t^{+}]$, or 
(ii) $I\models [t ,t^{+}]da_{\neg l }$.
Condition (i) guarantees that $\delta $ is
attacked by $\Delta _{QF}^I$ and thus $\delta $ can not be a member 
of $Lr(\Delta _{QF}^I)$. Therefore, (ii) must be the case.\hfill$\Box$\\[-1ex]

The converse of Lemma~\ref{le2} does not hold.
There are cases in which $I\models [t ,t^{+}]da_{\neg l }$
and the assumption $[t]FA_l$ is attacked by $\Delta_{QF}^I$ as a basic action 
occurs that changes the fluent literal $l$.

\begin{The}
\label{th1}Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
S-domain. If $I$ is a CPMM of $D$ then $\Delta _{QF}^I$ is plausible.
\end{The}

We now prove that not only can we derive a plausible set of assumptions from
a given CPMM but we can also construct CPMMs from a plausible set of
assumptions of a given S-domain.

The set of $\Delta $-relativised models of an S-domain $D$ is denoted as 
$Mod_\Delta ^S(D)$.

\begin{Obs}
\label{ob3}Let $D$ be an S-domain and $\Delta $ a set of assumptions of $D$.
For each $I\in Mod_\Delta ^S(D)$, $\Delta =\Delta _{QF}^I$. % \hfill$\square $
\end{Obs}
{\em Proof}. From the construction of $\Delta $-relativised models:

For each $I \in Mod_\Delta ^S(D)$, $\delta =[\tau ]FA_l \in \Delta $
iff $I\models [\tau ]FA_l $ iff $\delta \in \Delta _{FA}^I$. (More precisely,
we have the assumption $[\phi(\tau)]FA_l$ is in $\Delta _{FA}^I$, where $\phi$ is 
the valuation defined in $I$. But relative to $I$, it is identical to $\delta$.)

Therefore, $\Delta =\Delta _{QF}^I$.\hfill$\Box$

\begin{The}
\label{th2}Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
S-domain and $\Delta \subseteq {\cal AB}$. $\Delta $ is plausible wrt $D$
iff $Mod_\Delta ^S(D)\neq \emptyset $ and for each $I\in Mod_\Delta ^S(D)$, 
$I$ is a CPMM of $D$.
\end{The}

\begin{The}
\label{th3}Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
S-domain. Furthermore, suppose that $CPMM(D)$ is the set of CPMMs of $D$ and 
$Plaus(D)$ is the set of plausible sets of assumptions of $D$, then $%
CPMM(D)=\bigcup_{\Delta \in Plaus(D)}Mod_\Delta ^S(D)$.
\end{The}

\subsubsection{Discussion:}
So, how does our account of the frame problem relate to the existing approaches
to the frame problem? While there has been a long line of development
behind monotonic approaches to the frame problem starting with \citeS{Haa87}
and \citeS{Sch90} early attempts and resulting in \citeS{Rei91} monotonic 
solution to the frame problem together with other solutions proposed by others
such as \citeA{Cas99} and \citeA{FZ01} or \citeS{thielscher97from} Fluent 
Calculus-based monotonic solution to the frame problem, with the notable exception 
of \citeS{thielscher01qualification} attempt to address the qualification problem,
few have tried to tackle the qualification within the framework they use
to address the frame problem.

On the other hand, in the action languages \cite{GL98} and related 
approaches such as those proposed by 
\citeA{MT95,MT97}, \citeA{giunchiglia97representing}, 
and \citeA{giunchiglia98action},
state transition systems are employed as the underlying computation
machinery which essentially provides the reasoner with all possible
complete states of the world. Furthermore, as domain decsriptions
can be uniquely translated to state transition systems, the reasoner 
could safely derive the successor state(s) based on the current 
together with the transition function.

\subsection{Solving the Qualification Problem (in the Presence of the Frame
Problem)}

The results reported in the previous section are established in a simple
setting. If we add the following observation to the theory in 
example~\ref{exa:4.1}: 
$[3]alive$, i.e. after the $shoot$ action, the victim is still alive, then
like most existing formalisms, the above account of plausibility would come
up with a contradiction. In fact, it would be more reasonable that such a
failure is explained as an occurrence of some qualification. In this
section, we remove certain restrictions on the qualifications of actions in
order to achieve a more general framework.

There are some subtleties in the way action theories are represented in our
proposed assumption-based framework. Note first that there is a potential
difficulty if frame assumptions and qualification assumptions are treated 
equally, which can be illustrated by a version of the YSP. Consider
the following action description:

$$
\{\frac{[\tau ]alive,[\tau ]FA_{alive}}{[\tau ^{+}]alive},\frac{[\tau
]loaded,[\tau ,\upsilon ]shoot,[\tau ,\upsilon ]AQ_{\neg alive}}{\neg
[\upsilon ]alive\wedge \neg [\tau ]FA_{alive}}\}\subseteq {\cal R}\mbox{,} 
$$

$\{[0]loaded,[0]alive,[0,1]shoot\}\subseteq \Gamma $.

From this, we have (at least) two stable sets of assumptions: one contains
the frame assumption $[0]FA_{alive}$ which rejects the qualification
assumption $[0,1]AQ_{\neg alive}$ and another contains $[0,1]AQ_{\neg alive}$
which attacks $[0]FA_{alive}$. Only the latter is intuitive in this case but
we do not have any explicit criterion to prefer one over another.
The following assumption asserts that in our solution to the frame problem
in the presence of the qualification problem, an action is presumed to
bring about its effects unless there is an explicit justification for its
disqualification.

\begin{Ass}
When there is a direct conflict between a frame assumption and a qualification
assumption (over a fluent literal), the qualification assumption takes precedence.
\end{Ass}

Given the presence of several kinds of assumptions, i.e. frame and
qualification, we will adopt the following convention: we will write $%
Lr_P(\Delta )$ instead of $(Lr(\Delta ))_P$ for $P\in \{FA,AQ\}$. Since we
no longer exclude qualification assumptions from our assumption-based domain
descriptions, we will simply refer to assumption-based domain descriptions
as {\em Q-domains}\index{Q-domain}.

\begin{Def}
{\rm
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be a Q-domain. A
presumable set of assumptions $\Delta \subseteq {\cal AB}$ is 
\emph{semi-Q-plausible}\index{semi-Q-plausible} wrt
$D$ iff $Lr_{FA}(\Delta )$ is minimal (with respect to
set inclusion).  % \hfill$\blacksquare $
}
\end{Def}

\begin{Def}
{\rm 
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $\ be a
Q-domain. A set of assumptions $\Delta \subseteq {\cal AB}$\ is 
\emph{Q-plausible}\index{Q-plausible} wrt $D$ iff 
\begin{enumerate}
\item   $\Delta $\ is semi-Q-plausible wrt $D$,
\item $\Delta _{AQ}$\ is maximal, i.e. there does not exist any 
$\Delta ^{\prime }\subseteq {\cal AB}$\ such that $\Delta ^{\prime }$\ is
semi-Q-plausible (wrt $D$) and $\Delta _{AQ}$\ $\subset \Delta
_{AQ}^{\prime }$, and
\item $\Delta _{FA}$\ is maximal relative to the above two
conditions, i.e. there does not exist any $\Delta ^{\prime }\subseteq {\cal AB}$
\ such that $\Delta ^{\prime }$\ satisfies the above two
conditions and $\Delta _{FA}$\ $\subset \Delta _{FA}^{\prime }$. % \hfill$\blacksquare $
\end{enumerate}
}
\end{Def}

We will now refer to models of a Q-domain as {\em Q-models}. A {\em coherent
Q-model}\index{Q-model!coherent} is a Q-model which is coherent. 
We minimise the set of action
occurrences in coherent Q-models of a given action theory.

\begin{Def}
{\rm 
Let $D$\ be a Q-domain. A coherent Q-model $I$\ of $D$\ is a 
\emph{prioritised minimal Q-model}\index{Q-model!prioritised minimal} (or simply 
{\em PMQM}\index{PMQM|see{prioritised minimal Q-model}}) of $D$\ iff there 
does not exist any coherent Q-model 
$I^{\prime }$\ of $D$\ such that $Occ^{I^{\prime }}\subset Occ^I$.
% \hfill$\blacksquare $
}
\end{Def}

\begin{Def}
{\rm 
Let $D$\ be an S-domain. A PMQM $I$\ of $D$\ is a 
\emph{canonical prioritised minimal Q-model}\index{Q-model!canonical prioritised minimal} 
(or simply 
{\em CPMQM}\index{CPMQM|see{canonical prioritised minimal Q-model}}) of $D$\ iff 
\begin{enumerate}
\item  there does not exist any PMQM $I^{\prime }$ of $D$ such that $%
AQ^I\subset AQ^{I^{\prime }}$, and 
\item there does not exist any PMM $I^{\prime }$\ of $D$
\ such that $FA^I\subset FA^{I^{\prime }}$. % \hfill$\blacksquare $
\end{enumerate}
}
\end{Def}

Now we can proceed to obtaining the main results for CPMQMs regarding Q-plausible sets of
assumptions which are similar to those for CPMMs regarding plausible sets of
assumptions. The following lemma, which is a
straightforward extension of Lemma \ref{le1} and Lemma \ref{le2} proved in
the previous section, is introduced to assist in the proof of Theorem~\ref{th4} .

\begin{Lem}
\label{le3}Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
Q-domain and $I$ a CPMM of $D$,
\begin{enumerate}
\item For each assumption $\delta \in {\cal AB}$: $\delta \notin \Delta
_{QF}^I $ iff $\delta $ is rejected by $\Delta _{QF}^I$.

\item If $\delta =[\tau ]FA_l \in Lr(\Delta _{QF}^I)$ then $I\models
[\tau ,\tau ^{+}]da_{\neg l}$.
\end{enumerate}
\end{Lem}

\begin{The}
\label{th4}Let $D$ be a Q-domain. If $I$ is a CPMQM of $D$ then $\Delta
_{QF}^I$ is Q-plausible wrt $D$.
\end{The}

Similar to the previous section, we now prove that not only can we derive a
plausible set of assumptions from a given CPMQM but we can also construct
CPMQMs from a plausible set of assumptions of a given domain description.
The set of $\Delta $-relativised models of a Q-domain $D$ is denoted as $%
Mod_\Delta ^Q(D)$.\\[1.5ex]
The following observation is obvious:
\begin{Obs}
\label{ob4} Let $D$ be a Q-domain and $\Delta $ a set of assumptions of $D$. 
For
each $I\in Mod_\Delta ^Q(D)$, $\Delta =\Delta _{QF}^I$. % \hfill$\square $
\end{Obs}

\begin{The}
\label{th5}Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be a
Q-domain and $\Delta \subseteq {\cal AB}$. $\Delta $ is Q-plausible wrt $D$
iff $Mod_\Delta ^Q(D)\neq \emptyset $ and for each $I\in Mod_\Delta ^Q(D)$, $%
I$ is a CPMQM of $D$.
\end{The}

\begin{The}
\label{th6} Let $D$ be a Q-domain. Furthermore, suppose that $CPMQM(D)$ is
the set of CPMQMs of $D$ and $Plaus^Q(D)$ is the set of Q-plausible sets of
assumptions of $D$, then $CPMQM(D)=\bigcup_{\Delta \in Plaus^Q(D)}Mod_\Delta
^Q(D)$. % \hfill$\square $
\end{The}
%% 
%% {\em Proof}. Similar to the proof of Theorem \ref{th3}.\hfill$\blacksquare $

Q-plausible sets of assumptions allow one to overcome scenarios in which
expectation failures (or, qualification surprises) arise, e.g. shooting a
turkey with a loaded gun and observing that the turkey is still
alive. When such surprises arise, the reasoner knows who's to blame:
qualification assumptions. She can then accordingly remove the ``guilty''
assumptions. Just as the anomalous models forming obstacle to early
approaches to the frame problem, similar anomalous models can also
arise in solutions to the qualification problem. This important issue
related to the qualification problem has been thoroughly discussed by
\citeA{thielscher01qualification} and a solution was presented within
the framework of the Fluent Calculus. To give the reader a flavour of
this problem within our framework, we invite the reader to consider the 
following classical example:


\begin{Exa}\label{exa:4.6}
{\rm 
Consider the problem of starting a car whose tail pipe could possibly be 
blocked by a potato, formalised in our formalism as follows.

\begin{enumerate}
\item The set of inference rules $\cal R$ is:\footnote{%
Of course we also have the frame-based inference rules for $HasKey$, 
$BlockedTP$, etc. but we omit them from this representation for
sake of readability.}

%% \begin{gather*}
$\displaystyle \frac{[\tau]BlockedTP}{\neg [\tau ,\upsilon]AQ_{GetStarted}},$

$\displaystyle \frac{[\tau ]HasPotato,[\tau ,\upsilon]InsertPotato,[\tau ,\upsilon ]AQ_{BlockedTP}}
{[\upsilon]BlockedTP\wedge \neg [\tau ]FA_{\neg BlockedTP}},$

$\displaystyle \frac{[\tau]HasKey, [\tau,\upsilon]TurnOnIgnition, [\tau ,\upsilon]AQ_{GetStarted}}
{[\upsilon]GetStarted \wedge \neg [\tau]FA_{\neg GetStarted}}.$
%% \end{gather*}

\item The theory $\Gamma$ is: $\{
[0]HasPotato,
[0]HasKey,$
$\neg [0]BlockedTP,$
$\neg [0]GetStarted,$\\
$[0,1]InsertPotato,$
$[1,2]TurnOnIgnition \}$.
\end{enumerate}

Of course, we have designed this example to try to avoid any possible
troubles with the frame problem. We have to consider two conflicting
qualification assumptions in this case which are $[0,1]AQ_{BlockedTP}$
and $[1,2]AQ_{GetStarted}$. Given the above action theory, any
Q-plausible set of assumptions would contain exactly one of them. Thus,
there will be at least two extensions, one in which the car can not get
started since the tailpipe is blocked and it's no longer consistent to
assume $[1,2]AQ_{GetStarted}$. The other extension disqualifies the
action of inserting the potato into the tailpipe and thus the action of
starting the car becomes successful. Only the former is intuitive in this
case and the account of Q-plausible sets of assumptions fails to deliver
this desired solution.
}
\end{Exa}

However, in exactly the same way the problem of anomalous models arising
in the solution to the frame problem is tackled, the above problem is
easily addressed within our framework. The key insight is of course also
underlined by the notion of causality: $[1]BlockTP$ was caused (by the 
action $[0,1]InsertPotato$) which in turn allows 
$\neg [1,2]AQ_{GetStarted}$ to be derived. On the other hand, there was
no cause that allows $\neg [0,1]AQ_{BlockTP}$ to be derived. How is the 
above insight realised in our framework? The answer turns out to be 
rather simple: Just as the distinction between leniently rejected 
frame assumptions and non-leniently rejected frame assumptions allows us
to distinguish between normal changes (i.e. action-triggered) and
anomalous changes, a distinction between leniently rejected 
qualification assumptions and non-leniently rejected qualification 
assumptions will allow us to distinguish between normal disqualifications
(i.e. those underlined by a cause) and anomalous disqualifications.
Thus, facing a collection of Q-plausible sets of assumptions, a
reasoner simply selects the set of assumptions that contains the
smallest (with respect to set inclusion) set of leniently rejected
qualification assumptions.

The ability to introduce different argumentation-theoretic semantics
for assumption-based frameworks is arguably the biggest advantage of
our approach. The following example illustrates this critical point:


\begin{Exa}\label{exa:4.5}
{\rm
We modify an example presented by \citeA{LS95}
which is in turn a modification of \citeS{Kau86} Stolen Car Problem.
% We modify an example presented by Lin and Shoham \cite{LS95}
% which is in turn a modification of Kautz's \cite{Kau86} Stolen Car Problem.
A spy possessed a microfilm of a top secret evidence which an organisation, $%
A$, tried to steal. For some reason, another organisation, $B$, wanted to
murder this spy. The microfilm was in the safe at the spy's home at time $0$. 
The spy was not at home at time $0$. $A$ tried to $steal$ the evidence
between the time points $0$ and $1$. The spy might $return$ home at any time
between $0$ and $1$. $B$ tried to $murder$ the spy at any time between $0$
and $1$. $return$ cancels the effects of $steal$, $murder$ cancels the
effects of $return$ and $steal$ cancels the effects of $murder$. Any of the
three actions $steal$, $return$, and $murder$ takes only one time step. The
domain is formalised as follows: $\Gamma = \{
\neg [0]EvStolen, 
[0]Alive,
\neg [0]AtHome \}$; and $\cal R$ contains\\[1.5ex]
$\displaystyle \{ \frac{[\tau ,\upsilon ]steal,[\tau ,\upsilon ]AQ_{EvStolen}}
{[\upsilon]EvStolen\wedge \neg [\tau ]FA_{\neg EvStolen}},$ 
$\displaystyle \frac{[\tau ,\upsilon ]return,[\tau ,\upsilon ]AQ_{AtHome}}
{[\upsilon]AtHome\wedge \neg [\tau ]FA_{\neg AtHome}}, $
$\displaystyle \frac{[\tau ,\upsilon ]murder,[\tau ,\upsilon ]AQ_{\neg Alive}}{\neg
[\upsilon ]Alive\wedge \neg [\tau ]FA_{Alive}}, $\\[1.5ex]
$\displaystyle \frac{[\tau ]AtHome\wedge \tau <\upsilon }
{\neg [\tau ,\upsilon]AQ_{EvStolen}}, $
$\displaystyle \frac{\neg [\tau ]Alive\wedge \tau <\upsilon }
{\neg [\tau ,\upsilon]AQ_{AtHome}}, $
$\displaystyle \frac{[\tau ]EvStolen\wedge \tau <\upsilon }
{\neg [\tau ,\upsilon ]AQ_{\neg Alive}} \}$.\\
%% \end{gather*}

Given the above formalisation of the problem, traditional accounts of
non-monotonic reasoning (i.e. Default Logic, circumscription, Autoepistemic 
Logic, etc.) can not provide one with a solution since these formalisms 
can not produce any extension under their standard semantics. However, the
argumentation-theoretic approach does gives several semantics for this
problem including preferability semantics. Note, however, that
all admissible sets of assumptions and
preferred sets of assumptions for this domain contain \textbf{none} of
the assumptions: $[0,1]AQ_{EvStolen}$, $[0,1]AQ_{AtHome}$, and 
$[0,1]AQ_{\neg Alive}$.
This essentially means that, under the admissibility and
the preferability semantics, the reasoner could only infer that none
of the above actions would succeed
On the other hand, our proposed plausible semantics
gives an alternative solution for this problem in which each consistent set
of assumptions can contain at most one of the following three assumptions: $%
[0,1]AQ_{EvStolen}$, $[0,1]AQ_{AtHome}$, and $[0,1]AQ_{\neg Alive}$.
Moreover, each plausible set of assumptions must contain exactly one of them. 
Among the other two assumptions which do not
belong to a plausible set of assumptions, one is attacked and the other is
leniently rejected.
}
\end{Exa}

We believe that the above examples have underlined the major advantages
of our approach in which a reasoner is aware of the (defeasible) assumptions
used in her reasoning as well as being able to explicitly reason about
these assumptions. The flexibility of allowing a reasoner to introduce 
different argumentation-theoretic semantics for assumption-based
framework by simply varying the notion of acceptability of sets of 
assumptions is certainly another advantage in favour of our approach.

\section{More Complex Dynamic Domains and Indirect Effects}

So far we haven't taken into consideration the issues of concurrent actions
and indirect effects. To ensure that the formalisation introduced is
expressive enough to deal with complex domains, we will show how these
issues are coped with by our approach. Firstly, we motivate our
formalisation with an informal discussion.

\subsection{Concurrent and Non-Deterministic Events}

Given our temporal representation, formulating concurrent events is not a
difficult issue in our framework. However, there are some subtleties which
need to be carefully considered. Firstly, the use of assumptions. As
presented earlier in this paper, qualification assumptions are fluent
oriented, i.e. we qualify over the effects of action rather than over the
action itself. Whilst this manifests the capability of formulating actions
with multiple effects, and thus each effect should be qualified
independently, it may fail to formalise concurrent events with the same
effects. For example, both actions $hit$ the vase with a hammer and $shoot$
it with a loaded gun bring about the effect that the vase is $broken$. In
other words, it is essential that qualification assumptions be dependent on
the actions that bring about the effect under consideration. Thus, given $n$
actions and $m$ fluents whose values can be changed by those actions, we
have to potentially introduce $2\times m\times n$ qualifications assumptions.\footnote{% 
In fact, as we will see later, there are potentially $2\times m\times (n+1)$
qualification assumptions in this case since there is one special event
corresponding to all (natural) events that bring about the indirect effects.}
Therefore, instead of subscripting the assumption symbols $AQ$ with
the fluent literals from ${\cal F}^{*}$, we extend the set of subscripts
of $AQ$, denoted as ${\cal AF}$, to contain both the action and the corresponding
fluent literals.\footnote{The reader is referred to section~\ref{sc2} for the
general formalisation.} For example, given the above
two actions $hit$ and $shoot$ and an additional action $repair$ whose effect
is change a broken vase to being non-broken, {\em viz.} $\neg broken$, we will 
need
to introduce the following qualification assumptions: $AQ_{Hit\mbox{-}Broken},
AQ_{Shoot\mbox{-}Broken}$ and $AQ_{Repair\mbox{-}\neg Broken}$. 
Therefore, syntactically we also extend the set 
${\cal AB}_{AQ}=\{[\tau,\upsilon ]AQ_\varphi \ |\ \tau ,\upsilon \in {\cal TE}$ 
and $\varphi \in {\cal AF}\}$ 
and semantically the function $\varepsilon _q:\mathbb{T}%
\times AQ_{{\cal AF}}\times \mathbb{T}\rightarrow \{\mathbf{true},\mathbf{false}\}$. In the
definition of an interpretation $I=\langle h,\phi ,\eta ,\varepsilon
_q,\varepsilon _f\rangle $, we also have 
$I([\tau,\upsilon]AQ_\varphi,t) = \varepsilon_q(\phi(\tau),AQ_\varphi,\phi(\upsilon))$, 
where $\tau,\upsilon \in {\cal TE}$ and $\varphi \in {\cal AF}$.

Though this does increase the complexity of the framework, it is the price
we have to pay for the expressiveness of the resulting system. To the best
of our knowledge, none of the existing formalisms possesses such an
expressiveness.

How about non-deterministic actions? The solution turns out to be quite
simple: we can treat action non-determinism as a special kind of action
qualification. For example, to formulate the Russian shooting scenario 
\cite{San94} in which a gun non-deterministically gets loaded or not after
spinning its revolver, the following action descriptions can be asserted:\\[1.5ex]
$\displaystyle
adr_1=\frac{[\tau ,\upsilon ]spin,[\tau ,\upsilon ]AQ_{Spin\mbox{-}Loaded}}
{[\upsilon]loaded\wedge \neg [\tau ]FA_{\neg loaded}} 
$ and
$\displaystyle
adr_2=\frac{[\tau ,\upsilon ]spin,[\tau ,\upsilon ]AQ_{Spin\mbox{-}\neg Loaded}}
{\neg [\upsilon]loaded\wedge \neg [\tau ]FA_{loaded}} $\\[1.5ex]
together with the following two qualification rules:\\[1.5ex]
$\displaystyle
qr_1=\frac{[\upsilon ]loaded}{\neg [\tau ,\upsilon ]AQ_{Spin\mbox{-}\neg Loaded}} 
$
and
$\displaystyle
qr_2=\frac{\neg [\upsilon ]loaded}{\neg [\tau ,\upsilon ]AQ_{Spin\mbox{-}Loaded}} $.\\

The above guarantee that either $\neg [\upsilon ]loaded$ or 
$[\upsilon]loaded$ 
will follow from $[\tau ,\upsilon ]spin$ (remark that the set of
qualification assumptions $\Delta_{AQ}$ is maximised), but not both. As a
consequence, two possible extensions will arise given the above
non-deterministic action.

Dealing with non-determinism could be more complicated when the information
used to encode the action description is disjunctive. As we only restrict the
conclusion of an action description rule to contain only fluent literals,
such disjunctive effect is not straightforwardly dealt with in our
framework. However, note that the restriction is similar to that imposed on
action language $\cal A$ \cite{GL98}. An extension to action descriptions
which is similar to the way the action language $\cal A$ is extended into
the action language $\cal C$ can be done to allow a complex expression
in the conclusion of action description rule. However, for the sake of 
presentation, we choose to use a simpler language to introduce our 
framework to the reader.

\subsection{Formalisation}

From the analysis in the introductory section regarding indirect effects, we observe that
the ordering in which domain constraints are applied plays an essential role in
a technically sound framework. Moreover, it's no longer guaranteed that
domain constraints would be strictly satisfied at every time point.\footnote{Of course,
  it's not necessary that the state of the world at every time point is observable to a
  reasoner. However, it is important that she be aware of such states and able to reason
  about them.} To help the reader better understand this technical subtlety, it's useful
to think that changes 
are attributable to events. However, events are further divided into two
categories: external and internal. Basically, \emph{external events} 
correspond to
the direct effects of actions performed by some agents (including the
reasoner.) On the other hand, \emph{internal events} correspond to the 
indirect effects when certain conditions about the world are met and can be
attributed to Nature.\footnote{We avoid the use of the terms 
exogenous/endogenous events to label these two categories because throughout
the literature of reasoning about action, exogenous events are used to refer
to actions that carried out by agents that are different from the reasoner
or outside events whose occurrences are beyond the reasoner's control.}

Like external events, internal events also happen in a certain order.
Although it is not straightforward to observe this order\footnote{%
Unless indirect effects are somehow delayed and become observable to the
reasoner, they usually take place immediately after direct effects.}, it is
important that a reasoner be able to reason about them. Hence we propose to
add one more dimension into the set of assumptions of a given domain
description. Since these assumptions play essentially the same role as that
of qualification assumptions,\footnote{%
The only difference is that these assumptions are qualified over the indirect
effects which can be considered to be the effects of the actions of Nature.} 
we can subsume them under the set of qualification assumptions 
$AQ_{{\cal AF}}$. As they are not associated with any specific action, we can
ignore the initial of the action name from the subscripts of $AQ$. For
example we will write $AQ_{broken}$ in case we want to qualify over the
fluent $broken$ as an indirect effect, i.e. independently of any action.
Moreover, to avoid the axiomatiser from the confusion of determining the time
span taken by indirect effects, we will assume that it is atomic. It means
all indirect effects always take place between one time point and the next
one. This does not mean that all indirect effects have the same real-time
duration, it simply means that relative to the given time structure ${\mathbf T}$
they take place between two consecutive time points. This allows us to avoid
the granularity problem as it is irrelevant from the viewpoint of the
problems we are trying to solve.

\subsubsection{A Representation Issue and Some Notations:}
One important remark is in place here. Until now, we have used integers 
and the corresponding expressions to 
denote time points. There are two reasons for this pratice: (i) It 
significantly simplifies the presentation, and (ii) Without the
complication of the ramification problem, all time points which
are reasoned about are also observable to the reasoner. However, as
will be discussed thoroughly in the next section, in the presence of
ramifications a time point at which some change takes place maight not
be observable to the reasoner as such a change could be one of the indirect
effects after the execution of some action. Such representation issues 
make the integer-based time structure employed so far in this paper 
inappropriate. We do need a richer representation of time structure. 
Following \citeS{San94} basic formulation, the only basic constant to be
included in the representation of the time structure ${\mathbf T}$ is
denoted by the symbol $\Theta$\index{$\Theta$} and is referred to as the \emph{origin} 
of ${\mathbf T}$. The standard algebraic operations $+$ and $-$ are still
employed to obtain time expressions and bear their usual meanings. The 
relation symbol $<$ will also be used to compare time expressions.
However, we can no longer allow expressions such as $\Theta + 1$ for 
integers are no longer elements of the time structure.

Given a time expression $\tau$:
\begin{itemize} 
\item We will continue to denote the next time point of $\tau$ by $\tau^+$. 
\item We define $\tau^{1+}$ to be $\tau^+$ and, let $n > 1$, $\tau^{n+}$ 
to be $(\tau^{(n-1)+})^+$\index{$\tau^{n+}$}.
\end{itemize}

Furthermore, as we will assume throughout that
an indirect effect takes place between two consecutive time points, 
we also simplify the presentation by using the following syntactical sugar: 
instead of writing $[\tau ,\tau^{+}]AQ_l$ (for some $\tau \in {\cal TE}$ 
and $l \in {\cal F}^{*}$), we will write $[\tau ]AQ_l$. This also provides
a simple way to distinguish between qualification assumptions for
ramificational effects and those caused directly by an action or event.\\[-1ex]

How are domain descriptions affected from this augmentation? The only change
is for the set ${\cal R}_A$ of action descriptions which consists of rules
either of the form 
$$
\frac{\Phi ,[\tau ,\upsilon ]\alpha,[\tau ,\upsilon ]AQ_{\alpha\mbox{-}l}}
{[\upsilon]l \wedge \neg [\tau ]FA_{\neg l}} 
$$
or of the form%
$$
\frac{\Phi ,[\tau ]AQ_l}
{[\tau ^{+}]l \wedge \neg [\tau]FA_{\neg l}}. 
$$

For convenience, we will refer to the set of inference rules having the
latter form as ${\cal R}_I$, i.e. $\displaystyle {\cal R}_I=\{r\in {\cal R}_A\ |\ 
r= \frac{\Phi ,[\tau ]AQ_l}{[\tau ^{+}]l \wedge \neg [\tau
]FA_{\neg l}} \mbox{ for some fluent literal }l \in {\cal F}^{*} \}$. 
Now, regarding the ramification problem, the basic
idea is that the state obtained by updating the previous state may not
necessarily be stable due to the presence of indirect effects. By
representing indirect effects as causal rules (using inference rules in our
framework) we can reason about which causal rules have fired and
(relatively) when. Moreover, since these causal rules may not take the same
amount of time to fire, we should be able to reason about different possible
orders in which they fire. This will be achieved by a distinction between
stable and unstable states.

\begin{Def}\label{DefStb}
{\rm 
A time-point expression $\theta \in {\cal TE}$\ is 
{\em stable} 
wrt a given domain description $D=\langle {\cal L}_D,{\cal R},
{\cal AB},\Gamma \rangle $\ and $\Delta \subseteq {\cal AB}$\ iff
there does not exist any fluent literal $l \in {\cal F}^{*}$
% ramification-based inference rule }$r\in {\cal R}_I$%
\ such that 
\begin{enumerate}
\item  $\displaystyle\frac{\Phi ,[\tau ]AQ_l}
{[\tau^{+}]l \wedge \neg [\tau]FA_{\neg l}} \in {\cal R}_I$
\ and 
$\Gamma \cup \Delta \vdash_{{\cal R}}\Phi ,[\theta]AQ_l$, and 
\item $\Gamma \cup \Delta \not \vdash _{{\cal R}}[\theta]l$.
\end{enumerate}
}
\end{Def}

\begin{Def}
{\rm 
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $\ be a
domain description. A set of assumptions $\Delta $\ is said to be 
{\em ramification-compliant} iff
\begin{enumerate}
\item there does not exist any $\delta \in {\cal AB}_{AQ}$\ such
that $Th_{{\cal R}}(\Delta \cup \{\delta \})\neq Th_{{\cal R}}(\Delta )\cup
\{\delta \}$.
\item there does not exist any unstable time-point expression $\tau \in 
{\cal TE}$\ such that $[\tau ]FA_l \in \Delta $\ for every $l \in {\cal F}^{*}$.
\end{enumerate}
}
\end{Def}

We note that by using unstable time points, we have conceptually isolated the
ramification problem from the task of reasoning about the (explicit) actions.

\begin{Def}
{\rm 
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $\ be a
domain description. A set of assumptions $\Delta $\ is {\em generally
plausible for action domains}, or simply 
{\em AD-plausible}\index{AD-plausible}, iff
\begin{itemize}
\item   $\Delta $\ is ramification-compliant, and
\item   $\Delta $\ is Q-plausible relative to the above condition.
\end{itemize}
}
\end{Def}
\textsc{ Remarks:}
\begin{enumerate}
\item From the above definition, it can be seen that a solution for the
ramification is (in a sense) independent from the frame and the
qualification problems regarding action occurrences.

\item Given the above temporal ontology, it is worth noting that the
traditional notion of state constraints may no longer hold in this
representation regarding time points. More precisely, only states associated
with stable time points are subject to these constraints.
\end{enumerate}

\subsection{Connection to Causation-Based Formalisms}

The question is, of course, whether the above computational mechanism gives
satisfactory conclusions for problems in reasoning about action. While many
formalisms have been proposed, a general criterion for reasoning about
action formalisms still seems to be missing. The major stream of research
towards a solution to the ramification problem is based on the notion of
causality \cite<e.g.,>{Lin95,MT95,Thi97}. As has been
discussed above, none of these approaches can deal with domains in which
(potentially) infinite sequences of indirect effects are present. Most of
these approaches (including the above three references), however, produce a
successor state after the execution of an action to capture changes that
have taken place either as direct or as indirect effects of that action. In
this sub-section, we show how our formalism captures the notion of successor
states in the absence of the infinite sequences of indirect effects.

\begin{Def}
{\rm 
A domain description $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma
\rangle $\ is {\em non-stratified}\index{non-stratified} iff there 
exist two sets $\Phi \subseteq \Lambda $\ 
and $\{l_1,\ldots ,l_n\}\subseteq {\cal F}^{*}$\ such that
\begin{enumerate}
\item for each $1\leq i\leq n$, $\Phi \cup \{[\tau ]l_i\}$\ is 
${\cal R}$-consistent, for every $\tau \in {\cal TE}$; and
\item for each $1\leq i\leq n$, if $k=(i\ mod\ n) + 1$, then there exists 
a set $\Psi ^k\subseteq \Lambda $\ such that 
$\Phi \cup \{[\tau ]l_i\}\vdash _{{\cal R}}\Psi ^k$, and 
$$
\frac{\Psi ^k,[\tau ]AQ_{l_k}}{[\tau ^{+}]l_k\wedge \neg [\tau
]FA_{\neg l_k}}\in {\cal R}_I. 
$$
\end{enumerate}
}
\end{Def}

Of course, a domain description is 
{\em stratified}\index{domain description!stratified}
if and only if it is not
non-stratified. Given a domain description $D=\langle {\cal L}_D,{\cal R},%
{\cal AB},\Gamma \rangle $, we'll denote $E_D(\Delta )\stackrel{def}{=}Th_{%
{\cal R}}(\Gamma \cup \Delta )$, the extension of an action theory $D$
according to $\Delta $. We will also write $E_D$ instead of $E_D(\emptyset )$
for brevity.

\begin{Def}
{\rm Let }$\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle ${\rm \ be a 
signature.%
}

\begin{enumerate}
\item  {\rm A set }$S\subseteq {\cal F}^{*}${\rm \ is an \emph{instantwise
state}\index{instantwise state} iff for 
every }$l \in {\cal F}^{*}${\rm , either }$l \in S$
{\rm \ or }$\neg l \in S${\rm . }$IS${\rm \ will be used to denote
the set of instantwise states of }$\Lambda ${\rm ,}

\item  {\rm Let }$\Gamma \subseteq {\cal F}^{*}${\rm \ and }
$\tau \in {\cal TE}$
{\rm , we denote }$\overline{\Gamma }\stackrel{def}{=}\{\neg l$%
{\rm \ }$|${\rm \ }$l \in \Gamma \}${\rm \ and }$[\tau ]\Gamma 
\stackrel{def}{=}\{[\tau ]l${\rm \ }$|${\rm \ }$l \in \Gamma \}$%
{\rm ,}

\item  {\rm Let }$D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle ${\rm %
\ be a domain description. }$D${\rm \ is 
{\em simplistic}\index{domain description!simplistic} iff }
$\Gamma = \emptyset ${\rm .}
\end{enumerate}
\end{Def}

The motivation behind the introduction of instantwise states is to allow
the reasoner to reason about the intermediate states which may not be 
practically observable to her. That is, when indirect effects (following
an occurrence of an action or event) take place, the world might transit
through a number of intermediate states before becoming stabilised in a final 
state in which all domain constraints necessarily hold. The ability to
explicitly reason about such (unstable) intermediate states is one of the 
advantages offered by our approach. For instance, let's consider the scenario
in Example~\ref{exa:4.2} which was originally introduced by \citeA{Thi97}.
\citeS{Thi97} approach allows two possible successor states as
the results of closing the switch $sw_1$ in the initial state 
$S = \{ \neg sw_1, sw_2, sw_3, \neg relay, \neg light, \neg detect \}$.
These are $T_1 = \{ sw_1, \neg sw_2, sw_3, relay, \neg light, \neg detect \}$
and $T_2 = \{ sw_1, \neg sw_2, sw_3, relay, \neg light, detect \}$. 
However, to an outside observer who has no idea about the tricky internal mechanism
of this circuit, it could be quite difficult to explain why $T_2$ should be 
one of the possible outcomes of the action of closing the switch $sw_1$: 
starting from an initial state in which $detect$ and $light$ are both 
off, after performing an action $toggle(sw_1)$, $light$ remains off but 
somehow $detect$ becomes on. In other words, \citeS{Thi97} framework
fails to render the intermediate (and unstable) state in which $light$
was on, albeit for only a short instant, before it was turned off again.
On the other hand, such states are explicitly represented and reasoned 
about as instantwise states in our framework. As a consequence, domain
constraints do not necessarily hold in an instantwise state.

In the following, we abbreviate simplistic and stratified domain
descriptions as {\em SSD}s\index{SDD|see{stratified domain description}}. 
Let $\Omega \subseteq {\cal R}_I$, we denote:
$$
CONS_R(\Omega )\stackrel{def}{=}\{l \in {\cal F}^{*}\ |\ 
\frac{[\tau ]\Psi ,[\tau]AQ_l}
{[\tau ^{+}]l \wedge \neg [\tau ]FA_{\neg l}} \in \Omega \}.$$ 
Similarly, let $\Omega \subseteq {\cal R}_A$, we denote 
$$
CONS_A(\Omega )\stackrel{def}{=}\{l \in {\cal F}^{*}\ |\ 
\frac{[\tau_1]\Psi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\alpha\mbox{-}l}}
{[\tau_2]l \wedge \neg [\tau_1]FA_{\neg l}}\in \Omega \}.$$ 

The action description 
$\displaystyle \frac{[\tau_1]\Psi ,[\tau_1,\tau_2]\alpha ,
[\tau_1,\tau_2]AQ_{\alpha\mbox{-}l}}
{[\tau_2]l \wedge \neg [\tau_1]FA_{\neg l}}\in 
{\cal R}_A$\ is {\em applicable}\index{action description!applicable} 
in $S$\ iff $\Psi \subseteq S$. We use $\Upsilon_\alpha ^S$\index{$\Upsilon_\alpha ^S$}\ 
to denote the set of action descriptions that is applicable (in 
$S$) regarding the action $\alpha $. $\Omega \subseteq \Upsilon _\alpha ^S$\
is a {\em possible application} of $\alpha $ in $S$ iff $CONS_A(\Omega )$ is
consistent and there does not exist any $\Omega ^{\prime }\subseteq
\Upsilon _\alpha ^S$ such that $\Omega \subset \Omega ^{\prime }$ and $%
CONS_A(\Omega ^{\prime })$ is consistent.

\begin{Def}
{\rm 
Let $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be a signature
and $D=\langle {\cal L}_D,{\cal R},{\cal AB},\emptyset \rangle $\ a SSD.
Suppose $S\in IS$\ and $\alpha \in {\cal A}$. We formalise the 
\emph{direct effects} of an action $\alpha $\ using a relation $Res_D$:
for all $S,S^{\prime }\in IS$, $(S,\alpha ,S^{\prime })\in Res_D$\ iff there 
is a possible application $\Omega $\ of $\alpha $\ in $S$\ such that:
\begin{enumerate}
\item[(i)] $CONS_A(\Omega )\subseteq S^{\prime }$, and
\item[(ii)] there does not exist any instantwise state $S^{\prime \prime }$%
\ such that $S^{\prime \prime }$\ satisfies (i) and $S^{\prime
\prime }\setminus S\subset S^{\prime }\setminus S$.
\end{enumerate}
}
\end{Def}

\begin{Def}
{\rm 
Let $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be a signature
and $D=\langle {\cal L}_D,{\cal R},{\cal AB},\emptyset \rangle $\ a SSD.
The \emph{causation relation}\index{causation relation} 
according to $D$, denoted as $Causes_D$\index{$Causes_D$}, 
is defined as follows: for all $S,S^{\prime }\in IS$, 
$Causes_D(S,S^{\prime })$\ iff there exists a non-empty set 
$\Omega \subseteq {\cal R}_I$\ of ramification inference rules such that
\begin{enumerate}
\item[(i)] for each $\displaystyle \frac{[\tau]\Psi ,[\tau]AQ_l}
{[\tau^{+}]l \wedge \neg [\tau]FA_{\neg l}}\in \Omega $, 
$\Psi \subseteq S$\ and
\item[(ii)] $CONS_R(\Omega )\subseteq S^{\prime }$, and
\item[(iii)] there does not exist any instantwise state $S^{\prime \prime }$\ such 
that $S^{\prime \prime }$\ satisfies (i) and (ii) and 
$S^{\prime \prime }\setminus S\subset S^{\prime }\setminus S$.
\end{enumerate}
}
\end{Def}

Given a domain description $D$, a state $S\in IS$ is {\em stable} regarding $%
D$ iff there does not exist any $S^{\prime }\in IS$ such that $%
Causes_D(S,S^{\prime })$.

\begin{Def}
{\rm 
Let $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be a signature
and $D$\ a SSD. Suppose $w\in IS$\ and $\alpha \in {\cal A}$. The 
\emph{state transition}\index{state transition} from $w$\ in $D$\ according to $\alpha $, denoted 
$Trans_D^\alpha (w)$, is the transitive closure of $Causes_D$\ regarding the 
state $\omega _1\in IS $\ satisfying $(w,\alpha ,\omega _1)\in Res_D$. Formally, 
$Trans_D^\alpha (w)=\{ \varpi \in IS \ |\ \mbox{there exists a sequence } 
\omega _1,\ldots ,\omega _n\in IS \mbox{ such that } (w,\alpha ,\omega_1)
\in Res_D \mbox{ and } \varpi =\omega _n \mbox{ and } (\omega _i,\omega_{i+1})
\in Causes_D \mbox{ for each } 1\leq i<n \mbox{ and }\varpi 
\mbox{ is stable regarding }D \}$.
}
\end{Def}

Let $I$ be an interpretation for ${\cal L}_D$ and $t\in \mathbb{T}$,
\begin{itemize}
\item we use $[I]^t$ to denote the instantwise state specified by $I$
at time point $t$: $[I]^t\stackrel{def}{=}\{l \in {\cal F}^{*}\ |\ 
I(l,t)= \mathbf{true} \}$. If $[I]^t$ is stable then $t$ is said to be a 
\emph{stable time point}\index{stable time point} in $I$.

\item we use $N_I$ to denote a function that maps a time point $t\in 
\mathbb{T}$ to the next stable time point 
in $I$: $N_I(t)\in \mathbb{T}$\index{$N_I$} such
that $[I]^{N_I(t)}$ is stable and for every $u\in \mathbb{T}$, if $t<u<N_I(t)$
then $[I]^u$ is not stable.
\end{itemize}

\begin{The}\label{th7}
Let $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be a signature and $%
D_0=\langle {\cal L}_D,{\cal R},{\cal AB},\emptyset \rangle $ a SSD and $%
\alpha \in {\cal A_0}$. Suppose that $w\in IS$. Define a domain description $%
D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $, where $\Gamma
=\{[\Theta ]\varphi $ $|$ $\varphi \in w\}\cup \{[\Theta ,\Theta ^{+}]\alpha
\}$. A set $\Delta \subseteq {\cal AB}$ of assumptions is AD-plausible wrt $%
D $ iff for each model $M$ of $E_D(\Delta )$, $[M]^{N_M(\Theta )}\in
Trans_D^\alpha ([M]^\Theta )$, i.e. $[M]^{N_M(\Theta )}$ belongs to the
state transition from $[M]^\Theta $ in $D$ according to $\alpha $.
\end{The}


We now re-consider the motivating examples introduced in Section~\ref{sec:ramp}.\\[2ex]
\begin{aExa}{\bf \ \ref{exa:4.2}}
{\rm
({\em continued}.) 
We re-formulate the action theory for
this example in terms of our formalism: \\

\begin{tabular}{l@{\hspace{9ex}}l}
$\displaystyle \frac{[\tau ]sw_1,[\tau ]sw_2,[\tau ]AQ_{light}}{[\tau ^{+}]light\wedge \neg
[\tau ]FA_{\neg light}},$ & 
$\displaystyle \frac{[\tau ]sw_1,[\tau ]sw_3,[\tau ]AQ_{relay}}{[\tau ^{+}]relay
\wedge \neg [\tau ]FA_{\neg relay}},$ \\[2ex]
$\displaystyle \frac{\neg [\tau
]sw_i,[\tau ]AQ_{\neg light}}{\neg [\tau ^{+}]light\wedge \neg [\tau
]FA_{light}}(i=1,2),$ &  $\displaystyle \frac{\neg [\tau ]sw_i,[\tau ]AQ_{\neg relay}}{\neg
[\tau ^{+}]relay\wedge \neg [\tau ]FA_{relay}}(i=1,3),$ \\[2ex]
$\displaystyle \frac{[\tau]relay,[\tau ]AQ_{\neg sw_2}}{\neg [\tau ^{+}]sw_2\wedge \neg [\tau
]FA_{sw_2}},$ & $\displaystyle \frac{[\tau ]light,[\tau ]AQ_{detect}}{[\tau
^{+}]detect\wedge \neg [\tau ]FA_{\neg detect}},$ %% \\[2ex]
\end{tabular}

\begin{tabular}{l@{\hspace{9ex}}l}
$\displaystyle \frac{\neg [\tau ]sw_i,[\tau
,\upsilon ]toggle_i}{[\upsilon ]sw_i\wedge \neg [\tau ]FA_{\neg sw_i}}(i=1,2,3),$
 & $\displaystyle \frac{[\tau ]sw_i,[\tau ,\upsilon ]toggle_i}{\neg [\upsilon
]sw_i\wedge \neg [\tau ]FA_{sw_i}}(i=1,2,3),$ \\ [2ex]
$\displaystyle \frac{[\tau ]\zeta,[\tau ]FA_\zeta }{[\tau ^{+}]\zeta }
\mbox{, where }\zeta \in {\cal F}^{*}.$
\end{tabular}

% \begin{gather*}
% \frac{[\tau ]sw_1,[\tau ]sw_2,[\tau ]AQ_{light}}{[\tau ^{+}]light\wedge \neg
% [\tau ]FA_{\neg light}}, \qquad \frac{[\tau ]sw_1,[\tau ]sw_3,[\tau ]AQ_{relay}}{%
% [\tau ^{+}]relay\wedge \neg [\tau ]FA_{\neg relay}}, \\
% \frac{\neg [\tau
% ]sw_i,[\tau ]AQ_{\neg light}}{\neg [\tau ^{+}]light\wedge \neg [\tau
% ]FA_{light}}(i=1,2), \qquad \frac{\neg [\tau ]sw_i,[\tau ]AQ_{\neg relay}}{\neg
% [\tau ^{+}]relay\wedge \neg [\tau ]FA_{relay}}(i=1,3), \\
% \frac{[\tau
% ]relay,[\tau ]AQ_{\neg sw_2}}{\neg [\tau ^{+}]sw_2\wedge \neg [\tau
% ]FA_{sw_2}}, \qquad \frac{[\tau ]light,[\tau ]AQ_{detect}}{[\tau
% ^{+}]detect\wedge \neg [\tau ]FA_{\neg detect}}. \\
% \frac{[\tau ]\zeta
% ,[\tau ]FA_\zeta }{[\tau ^{+}]\zeta }\mbox{, where }\zeta \in {\cal F}^{*}.
% \end{gather*}

\vspace*{3.5ex}

The theory is described as follows:\\[-1.5ex]

$\Gamma =\{\neg [\Theta ]sw_1,[\Theta
]sw_2,[\Theta ]sw_3,\neg [\Theta ]relay,\neg [\Theta ]light, \neg [\Theta
]detect\}\cup \{[\Theta ,N(\Theta )]toggle_1\}.$\\[-2ex]

Consider $\Delta $ such that $\Delta _{AQ}={\cal AB}_{AQ}\setminus
\{[\Theta^{2+}]AQ_{detect},[\Theta^{3+}]AQ_{detect}\}$ and
 $\Delta _{FA}= {\cal AB}_{FA}\setminus$ $ \{[\Theta^+]FA_{\neg light},[\Theta^+]FA_{\neg
relay},[\Theta^{2+}]FA_{sw_2},[\Theta^{3+}]FA_{light}\}$.
$\Delta $ is AD-plausible resulting in the next stable state being $\omega
=\{sw_1,\neg sw_2,sw_3,relay,\neg light,\neg detect\}$ at $[\Theta^{4+}]$.\\[-1.5ex]

In addition, the set $\Delta ^{\prime }\subseteq {\cal AB}$, where $\Delta
_{AQ}^{\prime }={\cal AB}_{AQ}\setminus \{[\Theta^{2+}]AQ_{detect}\}$ and $%
\Delta _{FA}^{\prime }={\cal AB}_{FA}\setminus $ $\{[\Theta^+]FA_{\neg light}, 
[\Theta^+]FA_{\neg relay}, [\Theta^{2+}]FA_{sw_2} , 
[\Theta^{3+}]FA_{light}$, $[\Theta^{3+}]FA_{\neg detect}\}$,
is also AD-plausible which results to the next stable state 
$\omega ^{\prime }=\{sw_1,\neg sw_2,sw_3,relay,\neg light,detect\}$ at $%
[\Theta^{4+}]$.\\[-2ex]

Moreover, the set $\Delta ^{\prime \prime }\subseteq {\cal AB}$, where 
$\Delta _{AQ}^{\prime \prime }={\cal AB}_{AQ}$ and 
$\Delta _{FA}^{\prime \prime }\ = {\cal AB}_{FA}\setminus \{[N(\Theta )]FA_{\neg light},$
$[\Theta^+]FA_{\neg relay}, [\Theta^{2+}]FA_{sw_2},
[\Theta^{2+}]FA_{\neg detect},
[\Theta^{3+}]FA_{light}\}$, is also AD-plausible which also results to
the next stable state $\omega ^{\prime }$ at $[\Theta^{4+}]$. In other
words, the model implied by $\Delta^{\prime }$ reflects a domain in which
it takes the same amount of time for the $detect$ to be on and the switch 
$sw_2$ to jump off. On the other hand, the model implied by 
$\Delta ^{\prime\prime }$ reflects a domain in which the amount of time for the 
$detect$ to
be on is (approximately) equal to the amount of time for switch $sw_2$ to
jump off and cause the $light$ to be off as well. The $detect$ implied by 
$\Delta $ is so insensitive that even though the $light$ and the $relay$ are
on at the same time ($\Theta^{2+}$), the $relay$ causes switch $sw_2$ to
jump off and then leads to the $light$ to be off as well but the $detect$ is
yet on.\\
}
\end{aExa}

\begin{aExa}{\bf \ \ref{exa:4.3}}
{\rm
({\em continued}.) 
We re-formulate the action theory for this example in terms of our formalism:\\

\begin{tabular}{l@{\hspace{9ex}}l}
$\displaystyle \frac{[\tau ]upL_1,[\tau ]upL_2,[\tau ]AQ_{open}}{[\tau ^{+}]open\wedge \neg
[\tau ]FA_{\neg open}},$ & $\displaystyle \frac{[\tau ,\upsilon ]flip_i,[\tau ]upL_i}{\neg
[\upsilon ]upL_i\wedge \neg [\tau ]FA_{upL_i}}(i=1,2),$ \\[2ex] 
$\displaystyle \frac{[\tau,\upsilon ]flip_i,\neg [\tau ]upL_i}
{[\upsilon ]upL_i\wedge \neg [\tau]FA_{\neg upL_i}}(i=1,2),$ 
& $\displaystyle \frac{[\tau ,\upsilon ]close,[\tau ]upL_1,[\tau]upL_2}
{\neg [\upsilon ]open\wedge \neg [\tau ]FA_{open}},$ \\[2ex] 
$\displaystyle \frac{[\tau_1,\tau _2]hold\_closed,
\neg [\tau _1]open,\tau _1\leq \tau \leq \tau _2}
{[\tau ]held\_closed\wedge \neg [\tau ]FA_{\neg held\_closed}},$ 
& $\displaystyle \frac{[\tau]held\_closed}{\neg [\tau ]AQ_{open}},$ \\[2ex] 
$\displaystyle \frac{[\tau ]\zeta ,[\tau]FA_\zeta }
{[\tau ^{+}]\zeta } \mbox{, where }\zeta \in {\cal F}^{*}. $\\
\end{tabular}

\vspace*{2ex}
% \begin{gather*}
% \frac{[\tau ]upL_1,[\tau ]upL_2,[\tau ]AQ_{open}}{[\tau ^{+}]open\wedge \neg
% [\tau ]FA_{\neg open}}, \qquad \frac{[\tau ,\upsilon ]flip_i,[\tau ]upL_i}{\neg
% [\upsilon ]upL_i\wedge \neg [\tau ]FA_{upL_i}}(i=1,2), \\ 
% \frac{[\tau
% ,\upsilon ]flip_i,\neg [\tau ]upL_i}{[\upsilon ]upL_i\wedge \neg [\tau
% ]FA_{\neg upL_i}}(i=1,2), \qquad \frac{[\tau ,\upsilon ]close,[\tau ]upL_1,[\tau
% ]upL_2}{\neg [\upsilon ]open\wedge \neg [\tau ]FA_{open}}, \\ 
% \frac{[\tau
% _1,\tau _2]hold\_closed,\neg [\tau _1]open,\tau _1\leq \tau \leq \tau _2}{%
% [\tau ]held\_closed\wedge \neg [\tau ]FA_{\neg held\_closed}}, \qquad \frac{[\tau
% ]held\_closed}{\neg [\tau ]AQ_{open}}. \\ 
% \frac{[\tau ]\zeta ,[\tau
% ]FA_\zeta }{[\tau ^{+}]\zeta } \mbox{, where }\zeta \in {\cal F}^{*}. 
% \end{gather*}
% $$
% \begin{array}{ll}
% \end{array}
% $$

The theory is described as follows:\\[1ex]
$\Gamma =\{[\Theta ]upL_1,[\Theta ]upL_2,[\Theta ]open,[\Theta ]\neg held\_closed\}
\cup \{[c_1,c_2]close,[c_2,c_3]hold\_closed,[c_4,c_5]flip_1\}\cup $
$\{\Theta \leq c_1<c_2\leq c_4<c_5\leq c_3\}$.\\[-1.5ex]

Consider $\Delta \subseteq {\cal AB}$ such that $\Delta _{AQ}={\cal AB}%
_{AQ}\setminus \{[c]AQ_{open}$ $|$ $c_2\leq c\leq c_3\}$ and $\Delta _{FA}=%
{\cal AB}_{FA}\setminus (\{[c_1]FA_{open}\}\cup \{[c]FA_{\neg held\_closed}$ 
$|$ $c_2\leq c\leq c_3\}\cup \{[c_4]FA_{upL_1}\})$.
$\Delta $ is AD-plausible and resulting in the following:\\

$[c_1]\{upL_1,upL_2,open,\neg held\_closed\},$

$[c_2]\{upL_1,upL_2,\neg open,held\_closed\},$

$[c_4]\{upL_1,upL_2,\neg open,held\_closed\},$

$[c_5]\{\neg upL_1,upL_2,\neg open,held\_closed\},$

$[c_3]\{\neg upL_1,upL_2,\neg open,held\_closed\}.$\\
}
\end{aExa}

%% \newpage
\begin{aExa}{\bf \ \ref{exa:4.4}}
{\rm
({\em continued}.) 
The domain description:\\

\begin{tabular}{l@{\hspace{9ex}}l}
$\displaystyle \frac{[\tau ]sw_1,[\tau ]sw_2,[\tau ]AQ_{relay_1}}{[\tau ^{+}]relay_1\wedge
\neg [\tau ]FA_{\neg relay_1}},$ & $\displaystyle \frac{[\tau ]sw_1,\neg [\tau ]sw_2,[\tau
]AQ_{relay_2}}{[\tau ^{+}]relay_2\wedge \neg [\tau ]FA_{\neg relay_2}},$ \\ 
$\displaystyle \frac{[\tau ]relay_1,[\tau ]AQ_{\neg sw_2}}{\neg [\tau ^{+}]sw_2\wedge \neg
[\tau ]FA_{sw_2}},$ & $\displaystyle \frac{[\tau ]relay_2,[\tau ]AQ_{sw_2}}{[\tau
^{+}]sw_2\wedge \neg [\tau ]FA_{\neg sw_2}},$ \\ 
$\displaystyle \frac{\neg [\tau ]sw_i,[\tau
,\upsilon ]toggle_i}{[\upsilon ]sw_i\wedge \neg [\tau ]FA_{\neg sw_i}}(i=1,2),$
 & $\displaystyle \frac{[\tau ]sw_i,[\tau ,\upsilon ]toggle_i}{\neg [\upsilon
]sw_i\wedge \neg [\tau ]FA_{sw_i}}(i=1,2),$ \\ 
$\displaystyle \frac{[\tau ]\zeta ,[\tau
]FA_\zeta }{[\tau ^{+}]\zeta } \mbox{, where }\zeta \in {\cal F}^{*}. $\\
\end{tabular}

% \begin{gather*}
% \frac{[\tau ]sw_1,[\tau ]sw_2,[\tau ]AQ_{relay_1}}{[\tau ^{+}]relay_1\wedge
% \neg [\tau ]FA_{\neg relay_1}}, \qquad \frac{[\tau ]sw_1,\neg [\tau ]sw_2,[\tau
% ]AQ_{relay_2}}{[\tau ^{+}]relay_2\wedge \neg [\tau ]FA_{\neg relay_2}}, \\ 
% \frac{[\tau ]relay_1,[\tau ]AQ_{\neg sw_2}}{\neg [\tau ^{+}]sw_2\wedge \neg
% [\tau ]FA_{sw_2}}, \qquad \frac{[\tau ]relay_2,[\tau ]AQ_{sw_2}}{[\tau
% ^{+}]sw_2\wedge \neg [\tau ]FA_{\neg sw_2}}. \\ 
% \frac{\neg [\tau ]sw_i,[\tau
% ,\upsilon ]toggle_i}{[\upsilon ]sw_i\wedge \neg [\tau ]FA_{\neg sw_i}}%
% (i=1,2), \qquad \frac{[\tau ]sw_i,[\tau ,\upsilon ]toggle_i}{\neg [\upsilon
% ]sw_i\wedge \neg [\tau ]FA_{sw_i}}(i=1,2). \\ 
% \frac{[\tau ]\zeta ,[\tau
% ]FA_\zeta }{[\tau ^{+}]\zeta } \mbox{, where }\zeta \in {\cal F}^{*}. 
% \end{gather*}

\vspace{3ex}

The state of the circuit in Figure~\ref{fig:cir2} is captured by the following 
action theory:\\[2ex]
$\Gamma =\{\neg [\Theta ]sw_1,[\Theta ]sw_2,\neg [\Theta ]relay_1,\neg
[\Theta ]relay_2\}\cup \{[c_1,c_2]toggle_1,[c_3,c_4]toggle_1\}\cup $
$\{\Theta \leq c_1 <c_2 <c_3 <c_4\}$\\[-1.5ex]

Consider $\Delta \subseteq {\cal AB}$ such that $\Delta _{AQ}={\cal AB}_{AQ}$
and $\Delta _{FA}={\cal AB}_{FA}\setminus (\{[c_1]FA_{\neg sw_1}\}\cup
\{[c_3]FA_{sw_1}\}\cup \{[c]FA_{\neg relay_1}$ $|$ $c_2\leq c\leq c_3$ and 
$c=(c_2)^{k+}$ where $k=4i$ and $i=0,1,2,\ldots \}\cup $\\$%
\{[c]FA_{sw_2},[c]FA_{relay_1}$ $|$ $c_2\leq c\leq c_3$ and $c=(c_2)^{k+}$
where $k=4i+1$ and $i=0,1,2,\ldots \}\cup $\\$\{[c]FA_{\neg relay_2}$ $|$ 
$c_2\leq c\leq c_3$ and $c=(c_2)^{k+}$ where $k=4i+2$ and $i=0,1,2,\ldots
\}\cup $\\$\{[c]FA_{\neg sw_2},[c]FA_{relay_2}$ $|$ $c_2\leq c\leq c_3$ and 
$c=(c_2)^{k+}$ where $k=4i+3$ and $i=0,1,2,\ldots \})$. \\
$\Delta $ is AD-plausible resulting to several possible models for this
domain depending on when switch $sw_1$ is toggled off:

$[c_1]\{\neg sw_1,sw_2,\neg relay_1,\neg relay_2\},$

$[c_2]\{sw_1,sw_2,\neg relay_1,\neg relay_2\},$

$[c_3]\{sw_1,\pm sw_2,\mp relay_1,\pm relay_2\},$

$[c_4]\{\neg sw_1,\pm sw_2,\mp relay_1,\pm relay_2\}.$
}
\end{aExa}

\subsubsection*{Remark:\footnote{The authors would like to acknowledge
an anonymous referee for pointing out this very subtle issue.}} 
Here, it is also important to raise the question whether our solution to the
ramification problem conflicts with the formulation of concurrent actions. 
When two actions $\alpha_1$ and $\alpha_2$ are concurrently performed: 
$\alpha_1$ causes an indirect effect 
$E$ and $\alpha_2$ triggers a non-terminating chains of effects. 
If the direct and indirect effects caused by $\alpha_2$ don't
interfere with $\alpha_1$'s production of $E$ then the reasoner can reason
about time points after the execution of $\alpha_1$ where $E$ holds for
being an indirect effect of $\alpha_1$. These time points are of course
unstable due to the non-terminating chains of indirect effects caused by
$\alpha_2$. On the other hand,
if the direct and indirect effects caused by $\alpha_2$ have the potential 
to prevent the former from producing $E$, the reasoning could be more 
complex. If it is observable that the direct effects of both actions
take place at the same time then the concurrent occurrences of the
two actions can be viewed as one single occurrence of one complex actions
whose direct effects are a combination of the direct effects of the two
actions. Further reasoning about ramifications will then be carried out 
as usual. On the other hand, when the reasoner herself is unsure about
the temporal correlation between the direct effects of the two actions,
every possible order of changes must be taken into consideration leading
to a highly nondeterministic outcome about what fluent will hold
in the future time points. However, such a situation can still be handled
nicely by our formalisation. The only representation issue which is not 
addressed by our framework is about indirect effects with \emph{duration}.
As asserted above, given the state of the world at a time point $\tau$, we
assume that all subsequent indirect effects will take place at the next 
time point $\tau^+$. This certainly fails to deal properly with indirect 
effects whose durations are \emph{different}. A simple solution to this
problem can be to associate one next time point operator for each
possible indirect effect. This, however, will significantly complicate
the representation.


\section{Discussion and Future Work}\label{sec:conc}

We developed a uniform framework for reasoning about action using an
argumentation-theoretic approach (more precisely, assumption-based approach). 
We have also presented how our framework
copes with the frame, the qualification and the ramification problems in
several sophisticated settings. We have shown how our framework can be
naturally extended to become more expressive.

We also explored a new abstraction level which we believe to be an
intermediate layer between the common sense knowledge and the scientific
knowledge. Sophisticated domain knowledge as well as representation are, we
argue, required to achieve an adequate underlying representation and
reasoning process. Among the merits of this approach, we emphasise the
following:

\begin{itemize}

\item \emph{Non-monotonicity} is handled by assumptions and
argumentation-theoretic approach.

\item The \emph{flexibility} of working with different kinds of information
representation since there is no restriction on the syntax of the system.

\item \emph{Expressivity}: temporal information is explicitly represented.
Thus the system is capable of capturing many important features of temporal
reasoning.
\end{itemize}

As reviewed in the introductory section of this paper, numerous approaches to 
reasoning about action have been proposed. As such, much research related to 
these approaches and frameworks has evolved around the central problems addressed
in this paper, namely the frame, qualification and the ramification problems.
However, as non-monotonic reasoning-based formalisms for reasoning about actions 
were shown to be flawed by \citeA{HM87}, many existing 
% were shown to be flawed by Hanks and McDermott (\cite{HM87}), many existing 
solutions of the frame problem are based on other approaches which are usually 
monotonic. Since one of the inherent properties of the argumentation-theoretic
approach is monotonicity, few have attempted to solve the problems of reasoning
about actions using this approach. 

A framework for reasoning about actions under the argumentation-theoretic approach 
is independently proposed by \citeA{KMT99,KMT00,KMT01}.
%% is independently proposed by Kakas, Miller and Toni (see \cite{KMT99}, \cite{KMT00} and \cite{KMT01}).
In their approach, the admissibility semantics is also employed to resolve conflicts 
between adversary arguments. To represent common sense knowledge, e.g. the common
sense law of inertia, an order is imposed on the set of inference rules of the 
assumption-based framework. The computation of the arguments and their competing 
is performed on top of the so-called {\em proof trees}. Nodes on the proof trees are
arguments which are sets of propositions.\footnote{In \citeS{KMT99,KMT00}
terminologies, each node is a set of arguments which is equivalent to the notion of 
arguments in our exposition.} Construction of proof trees is on the same level of
hardness as known frameworks for argumentation-theoretic computation. While their 
framework allows the persistence of (inertial) fluents to be captured and dealt with,
it is not very clear whether their formalisation can be extended to deal with other
problems of reasoning about actions such as the qualification and the ramification 
problems.
%%  Also, the issues of non-deterministic actions and concurrent actions have 
%% never been dealt with in their expositions.

More recently, \citeA{dimopoulos04reasoning}, and \citeA{bracciali04frame} extended 
Kakas et al.'s framework to deal with the ramification and the qualification
problems. Essentially, in their solution to the ramification problem, the
so-called \emph{r-propositions} of the following form:\footnote{$L$ is a fluent
literal and $C$ is a set of fluent literals which is essentially equivalent
to a conjunction of fluent literals.}
\[ L \mbox{ \texttt{whenever} } C
\]
are added to the domain description. A resulting model for a given domain 
description will then be computed by first computing all possible indirect 
effects as the fixed point of repeated application of r-propositions, and then
completing the model by allowing unaffected fluent literals to persist over
time. It should be clear that the above representation of indirect effects
is quite restrictive as it doesn't allow more complex expressions for
the conditions of an indirect effects and the indirect effects themselves.
These restriction is essentially due to their use of Answer Set Programming
(ASP) as the underlying computation mechanism of their framework.
On the other hand, their solution to the qualification problem lies in the 
use of default rules for representing the effects of actions. This approach 
is fairly similar to \citeS{thielscher01qualification} solution to
the qualification problem discussed above. As their approach is essentially
based on stability semantics, it's not clear how the argumentation-theoretic
approach will bring about any benefit to their framework.


As discussed earlier in the paper, the key insight behind the solutions implemented 
in our framework is the exploitation of causality to drive the inference. It is
causality that has helped throughout in our solutions to the frame and the
qualification problems to provide the mechanisms to eliminate the anomalous
models while retaining the intuitive models during the process of reasoning.
This insight is certainly a more general version of the conclusions derived
by \citeA{San94} when investigating the reason behind the production
of anomalous models in early approaches to the frame problem, namely the 
failure to distinguish between normal changes which are triggered by actions
and abnomalous changes. Sandewall's insight has certainly originated the 
occlusion-based solution to the frame problem 
\cite{San94,doherty94reasoning,gustafsson96embracing}. Roughly speaking, in this 
approach each action type is associated with a subset of fluents that are 
influenced by the action. Also, a predicate $Occlude$ is introduced to allow 
this subset of fluents to be specified. When reasoning about dynamic domains,
changes are minimised with the exception of the fluents specified by 
$Occlude$. In other words, $Occlude$ distinguishes the normal changes (associated
with the action types) from the anomalous changes and thus avoids 
unintended models from arising. 

Regarding the qualification problem, \citeS{thielscher01qualification} 
solution to the problem of anomalous models in relation to the qualification
problem shares the key insight of \emph{causality} with our approach. 
However, Thielscher's framework is based on the standard semantics of 
Default Logic (with the initial theories are generated
using circumscription). Thus, his approach does not deal with problem
domains where standard semantics of Default Logic does not produce
an extension. Furthermore, as discussed in the introductory section
of our paper, in Thielscher's framework qualifications are taken over
the executability conditions for the actions instead of over different
effects of the actions.

In parallel to the causality-based insight to dynamic domains, other 
mechanisms for solving various problems of reasoning about action exist.
For instance, a number of approaches employ the concept of 
\emph{chronological ignorance} \cite{shoham87reasoning,shoham88chronological}
to tackle the problem of anomalous models. In general, causality-based
frameworks and approaches based on chronological ignorance share the notion
of directedness: when changes are minimised chronologically, causes are
minimised instead of effects as causes are likely to precede effects.
However, as a consequence, backward reasoning is blocked which prevents
chronological ignorance-based approaches from dealing with surprises
and expectation failures. Furthermore, non-deterministic actions or 
incomplete state knowledge are known to cause difficulty to
chronological minimization. For a more detailed comparison between
causality-based approaches and their counterparts that are based on
chronological ignorance, the reader is referred to an article by
\citeA{thielscher01qualification}. On the other hand, approaches
that are based on \emph{Motivated Action Theory} (MAT)
\cite{amsterdam91temporal,stein94motivated} can be considered as 
a special case of the causality-based paradigm.
MAT frameworks also advocate for the insight that an appropriate 
notion of causality is necessary when assuming away abnormalities.
MAT frameworks, however, don't cope very well with the explanation
problem and the ramification problem as pointed out by
\citeA{ortiz99explanatory} who also introduce an approach to improve
MAT and overcome these problems.

Nonetheless, several issues still remain within our framework and will 
need further treatment to achieve an optimal
solution. Firstly, this formalism may not be very suitable for the
large-scale problems as too many assumptions will need to be taken into
account. To address this problem, a localisation procedure is invented to
guarantee that only an adequate sub-language will be used to capture the
circumstance the agent is reasoning about. As a consequence, the set of
assumptions will be restricted to those which are necessary to infer the
conclusions the agent is interested. This idea is under development.
Furthermore, while
a uniform solution to all major problems of reasoning about action may 
be quite attractive especially regarding the toy
scenarios such as those considered in this paper as well as in the
literature, such a solution may not be pragmatic. By considering the
locality account of reasoning, in particular of the assumptions used in
default reasoning, promising solution can be achieved from both
computational and representational points of view. We are undertaking further 
investigation towards this research direction.

A major limitation of our framework is the ability to deal with
disjunctive axiomatisation of action occurrences. For instance, when
the domain axiomatisation constains a disjunction about the action 
occurrences such as $[t_1, t_2]\alpha_1 \vee [t_1, t_2]\alpha_2$, then
no plausible sets of assumptions, and accordingly, no CPMMs 
(resp. CPMQMs) will be produced to account for the effects of these actions.
While an initial formalisation of our framework allowed complex expressions
for action occurrences in the premises of inference rules which overcame
this problem, the formalisation appeared to be too complex and some of
the technical results could not be established. Further investigation,
therefore, is needed to overcome this problem while avoiding to
produce an overly complex formalisation.

Provided that our formalism has been designed to provide a general framework for reasoning
about action, the following comes as a natural question: \emph{To what extent the proposed 
approach can be used to formalise dynamic domains?}
\citeA{San94} suggests that one should systematise a framework for
reasoning about action against some standard criteria to provide the formal 
indications about the expressiveness and capacity of a formalism. This is in contrast
to the more traditional approach that had prevailed for many years in reasoning
about action in which one tries to come up with some examples to show that no existing 
approaches are able to deal with such a scenario and claims that one's approach is
better than others in which it can solve the proposed scenario.

Relative to Sandewall's standard criteria, our approach enjoys the following properties:
\begin{enumerate}
\item Our approach is non-inertia as it allows observations about the later state 
to correct the system's predictions about those states using some explanation
mechanism through the use of assumptions.

\item Our formalism is able to deal with non-deterministic and concurrent events.
\end{enumerate}

Another issue is the abduction problem which is also known in the literature
as the explanation problem. For example, in the Stolen car scenario, by
observing that the car disappeared from the parking lot where the reasoner
had left it, an expectation failure arises. Most formalisms would try to
accommodate this problem by introducing a stealing action as part of the
vocabulary and try to bind the disappearance of the car to this action. This
arguably is not very intuitive as there is no good reason why we should
include this action in the vocabulary in the first place but not others such
as the car being towed away by the police or a fairy turning the car into
a pumpkin, etc. From a pragmatic point of view, some reasoners may just simply
acquire more information (perhaps from the police) instead of confusing
themselves with all kinds of explanations towards possible but uncertain
causes. In other words, we effectively isolate the issues of deducing the
new conclusions from the existing knowledge base from abducing the possible
causes of some observations. This is of course closely related to Shanahan's
approach in his IJCAI'95 paper \cite{Sha89} whose title clearly indicated
that ``{\em Prediction is Deduction but Explanation is Abduction}''. We are
also working on an assumption-based framework to solve the abduction problem.

\subsection*{Acknowledgements}
This work was performed when the first author was at the School of Computer 
Science and Engineering, University of New South Wales.
The authors wish to thank other members of the Knowledge Systems Group, in 
paricular Dongmo Zhang and Maurice Pagnucco, and the anonymous
reviewers of an earlier version of this paper for very helpful comments and 
suggestions that have significantly improve the quality as well as the 
readability of this paper. The first author was partially supported by
an International Postgraduate Research Scholarship (IPRS) sponsored
by the Australian government. The first author is presently
supported by a by a DEST IAP grant (2004-2006, grant CG040014).

\section*{\textsc{Appendix A}}

\begin{aThe}{\bf \ \ref{th1}}
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
S-domain. If $I$ is a CPMM of $D$ then $\Delta _{QF}^I$ is plausible.\\[2ex]
\end{aThe}
\emph{Proof:} Suppose that $I$ is a CPMM of $D$,

(i) \emph{we prove that $\Delta _{QF}^I$ is presumable:}

$\Delta _{QF}^I$ is ${\cal R}$-consistent since $I$ is a model of $D$. From
Observation \ref{ob2}, we have $\Delta _{QF}^I$ is closed and does not
attack itself.
From Lemma \ref{le1}, for each assumption $\delta \in AB$, if $\delta \notin
\Delta _{QF}^I$ then $\delta $ is rejected by $\Delta _{QF}^I$.

(ii) \emph{we prove that $Lr(\Delta _{QF}^I)$ is minimal:}

Suppose by way of contradiction that there exists a presumable set of
assumptions $\Delta $ (wrt $D$) such that $Lr(\Delta )\subset Lr(\Delta
_{QF}^I)$.
Let $I_\Delta $ be the $\Delta $-relativised model of $D$. It is obvious
that $I_\Delta $ is coherent. We will derive a contradiction by proving
that $Occ^{I_\Delta }\subset Occ^I$:

(ii.1) $OA_D\subseteq Occ^I$: obvious as 
$OA_D=\{(\phi(\tau_1),\alpha,\phi(\tau_2))\in 
{\Bbb T}\times {\cal A}_0\times {\Bbb T}\ |\ \Gamma \models
[\tau_1,\tau_2]\alpha\}$, and $I$ is a model of $D$.

(ii.2) $DAS(\Delta )\subseteq Occ^I$: Let $(t,da_{\neg l},t^{+})\in
DAS(\Delta )$, then there do not exist any action $\alpha \in {\cal A}_0$
and $s \in {\Bbb T}$
such that 
\[
r=\frac{\Phi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\neg l }}
{\neg [\tau_2]l \wedge \neg [\tau_1]FA_l} \in {\cal R}
\] 
and $I\models prem(r)[\tau_1/s, \tau_2/t^{+}] \}$. 
Thus, the assumption $\delta =[t]FA_l \in Lr(\Delta )$.
Thus, $\delta \in Lr(\Delta _{QF}^I)$ (from the hypothesis.)
From Lemma \ref{le2}, $I\models [t,t^{+}]da_{\neg l}$. Thus 
$(t,da_{\neg l},t^{+})\in Occ^I$.

(ii.3) $Occ^I\not \subseteq Occ^{I_\Delta }$: Let $\delta =[t]FA_l
\in Lr(\Delta _{QF}^I)\setminus Lr(\Delta )$ for some $t \in {\Bbb T}$
and $l \in {\cal F}^{*}$.

Since $I$ is a CPMM of $D$, from Lemma \ref{le2}, 
$I\models [t ,t^{+}]da_{\neg l}$. Thus $(t,da_{\neg l},t^{+})\in Occ^I$.

Moreover, $\delta \notin Lr(\Delta )$ \textbf{iff}
either (a) $\delta \in \Delta $,
or (b) there is $\alpha \in {\cal A}_0$\ such that 

$\displaystyle
r=\frac{\Phi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\neg l }}
{\neg [\tau_2]l \wedge \neg [\tau_1]FA_l} \in {\cal R}
$ 
and $\Gamma \cup \Delta \vdash _{{\cal R}} 
\Phi[\tau_1/t, \tau_2/t^{+}] ,[t,t^{+}]\alpha,[t,t^{+}]AQ_{\neg l }$

\textbf{iff}, following the construction of $\Delta $-relativised models, $I_\Delta 
\not \models [t,t^{+}]da_{\neg l}$. 
Thus $(t,da_{\neg l},t^{+})\notin Occ^{I_\Delta }$.
%
Therefore, $Occ^{I_\Delta }\subset Occ^I$. % Contradiction.

Hence, $Lr(\Delta _{QF}^I)$ is minimal and $\Delta _{QF}^I$ is plausible.%
\hspace*{\fill}$\Box$ \\[2ex]

\begin{aThe}{\bf \ \ref{th2}}
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
S-domain and $\Delta \subseteq {\cal AB}$. $\Delta $ is plausible wrt $D$
iff $Mod_\Delta ^S(D)\neq \emptyset $ and for each $I\in Mod_\Delta ^S(D)$, $%
I$ is a CPMM of $D$.\\[2ex]
\end{aThe}
\emph{Proof:} 

($\Rightarrow $) Suppose that $\Delta \subseteq {\cal AB}$ is
plausible wrt $D$. Then $\Gamma \cup \Delta $ is ${\cal R}$-consistent, i.e. 
$\Gamma \cup \Delta \not \vdash _{{\cal R}}{\mathbf{false}} $. 
From the construction of $%
\Delta $-relativised models, $Mod_\Delta ^S(D)\neq \emptyset $.

For each $I=\langle h,\phi ,\eta ,\varepsilon _q,\varepsilon _f\rangle \in
Mod_\Delta ^S(D)$, we prove that $I$ is a CPMM of $D$.

(i) \emph{$I$ is a coherent S-model of $D$:} obvious from the definition of $\Delta 
$-relativised models.

(ii) \emph{$Occ^I$ is minimal:}

Assume the contrary, i.e. there is a non-empty set ${\cal M}_I=\{J$ $|$ $J$
is a coherent S-model of $D$ and $Occ^J\subset Occ^I\}$.
Let $H\in {\cal M}_I$ such that there does not exist any model $J\in {\cal M}%
_I$ and $FA^H\subset FA^J$.

Consider the set of assumptions $\Delta _{QF}^H$:

(ii.a) $\Delta _{QF}^H$ is presumable wrt $D$:

\begin{itemize}
\item  $\Delta _{QF}^H$ is closed and does not attack itself (since $H$ is a
model of $D$);

\item  Let $\delta \in {\cal AB}$, if $\delta =[\tau ]FA_l \not \in
\Delta _{QF}^H$ (for some $\tau \in {\cal TE}$ and $l \in {\cal F}^{*}$%
) and $\delta $ isn't rejected by $\Delta _{QF}^H$ then we can easily
construct a model $J$ that interprets everything except $FA$ the same as $H$
and $FA^J=FA^H\cup \{(\phi (\tau ),FA_l)\}$. Obviously, $J\in {\cal M}%
_I$ and $FA^J\subset FA^H$ which is a contradiction. Thus $\delta $ is
rejected by $\Delta _{QF}^H$.
\end{itemize}

Therefore, $\Delta _{QF}^H$ is presumable.

(ii.b) $Lr(\Delta _{QF}^H)\subset Lr(\Delta )$:

$Occ^H\subset Occ^I$ since $H\in {\cal M}_I$.

Let $\delta \in Lr(\Delta _{QF}^H)$. Since ${\cal AB}_{AQ}\subseteq \Delta
_{QF}^H$, $\delta =[t]FA_l \in {\cal AB}_{FA}$ for some $t \in {\Bbb T}$
and $l \in {\cal F}^{*}$.
From the definition of leniently rejected assumptions, $\Gamma \cup \Delta
_{QF}^H\not \vdash _{{\cal R}}{\mathbf{false}}$ 
but $\Gamma \cup \Delta _{QF}^H\cup \{\delta \}\vdash _{{\cal R}}{\mathbf{false}}$.
But then, from the definition of coherent models, 
$H\models [t,t^{+}]da_{\neg l}$ (since $H$ is a coherent model of $D$).
Thus, $I\models [t,t^{+}]da_{\neg l}$.

From the construction of $\Delta $-relativised models, 
$[t]FA_l \not \in \Delta $. 
Thus, $\delta $ is rejected by $\Delta $ (since $\Delta$ is plausible wrt $D$).
Also from the construction of $\Delta $-relativised models, $\Gamma \cup
\Delta \not \vdash _{{\cal R}}\neg \delta $.
Therefore, $\delta \in Lr(\Delta )$, or $Lr(\Delta _{QF}^H)\subseteq
Lr(\Delta )$.
Now, $Occ^I=OA_D\cup DAS(\Delta )$.
$OA_D\subseteq Occ^H$ since $H$ is a model of $D$.
Thus, $Occ^I\setminus Occ^H=DAS(\Delta )\setminus Occ^H$.
Let $(t,da_{\neg l},t^{+})\in DAS(\Delta )\setminus Occ^H$.
From the construction of $\Delta $-relativised models, $\delta
=[t]FA_l \in Lr(\Delta )$.

Suppose further that $\delta \in Lr(\Delta _{QF}^H)$. Then, $\delta \notin
\Delta _{QF}^H$ (as $\Delta _{QF}^H$ is presumable).
We construct a model $J$ in such a way that $J$ interprets everything except 
$FA$ the same as $H$.
From the definition of coherent models, 
$(t,da_{\neg l},t^{+})\notin Occ^H$ 
iff either (1) $H\not \models [t]l \wedge \neg [t^{+}]l$; 
or (2) there is $\alpha \in {\cal A}_0$, and 
\[
r=\frac{\Phi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\neg l }}
{\neg [\tau_2]l \wedge \neg [\tau_1]FA_l} \in {\cal R}
\] 
and 
$\Gamma \cup \Delta \models prem(r)[\tau_1/t, \tau_2/t^{+}]$,
i.e., $\Gamma \cup \Delta \models \Phi[\tau_1/t, \tau_2/t^{+}],
[t,t^{+}]\alpha,[t,t^{+}]AQ_{\neg l}$.
Since $\delta =[t]FA_l \in Lr(\Delta )$, condition (2) can not be
satisfied.

Thus, $(t,da_{\neg l},t^{+})\notin Occ^H$ iff 
$H\not \models [t]l \wedge \neg [t^{+}]l$.
In other words, it is consistent to add the assumption $[t]FA_l$ to
the set of assumptions $\Delta _{QF}^H$. Or, from a model-theoretic point of
view, to augment the denotation of $FA$ in $H$ with $(t,FA_l)$ and we
can still obtain a coherent S-model $J$ such that $FA^H\subset FA^J$. But
this is a contradiction.
Hence, $\delta \notin Lr(\Delta _{QF}^H)$.

We have shown that $Lr(\Delta _{QF}^H)\subset Lr(\Delta )$.

From (ii.a) and (ii.b) we are led to the conclusion that $Occ^I$ is minimal.
As a consequence, $I$ is a CPMM of $D$ (from (i) and (ii)).

($\Leftarrow $) Suppose that $Mod_\Delta ^S(D)\neq \emptyset $ and for each $%
I\in Mod_\Delta ^S(D)$, $I$ is a CPMM of $D$. We prove that $\Delta $ is
plausible wrt $D$.
Take an arbitrary model $I\in Mod_\Delta ^S(D)$. Following Observation \ref
{ob3}, $\Delta =\Delta _{QF}^I$. From Theorem \ref{th1} and the hypothesis
that $I$ is a CPMM of $D$, we conclude that $\Delta $ is plausible wrt $D$.%
\hspace*{\fill}$\Box$\\[1ex]

\begin{aThe}{\bf \ \ref{th3}}
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be an
S-domain. Furthermore, suppose that $CPMM(D)$ is the set of CPMMs of $D$ and 
$Plaus(D)$ is the set of plausible sets of assumptions of $D$, then $%
CPMM(D)=\bigcup_{\Delta \in Plaus(D)}Mod_\Delta ^S(D)$.\\[2ex]
\end{aThe}
\emph{Proof:}

($\supseteq $) Let $\Delta \in Plaus(D)$, then $Mod_\Delta ^S(D)\subseteq CPMM(D)$ (Following Theorem \ref{th2}). Therefore,
$\bigcup_{\Delta \in Plaus(D)}Mod_\Delta ^S(D)\subseteq CPMM(D)$.

($\subseteq $) Let $I\in CPMM(D)$, then
$\Delta _{QF}^I\in Plaus(D)$ (Following Theorem \ref{th1}).

We prove that $I\in Mod_{\Delta _{QF}^I}(D)$ based on Definition \ref{df17}:

1) $I$ is an S-model of $D$,

2) for each $\delta =[\tau ]FA_l \in {\cal AB}_{FA}$
(for some $\tau \in {\cal TE}$ and $l \in {\cal F}^{*}$), $\delta \in
\Delta _{QF}^I$ iff $(\phi(\tau),FA_l)\in FA^I$ (Following the
definition of $\Delta _{QF}^I$ - Definition \ref{df16})

3) We prove that $Occ^I=OA_D\cup DAS(\Delta _{QF}^I)$:

(3.$\supseteq $) 

\begin{itemize}

\item $OA_D=\{(\phi(\tau_1),\alpha,\phi(\tau_2))\in 
{\Bbb T}\times {\cal A}_0\times {\Bbb T}\ |\ \Gamma \models
[\tau_1,\tau_2]\alpha\} \subseteq Occ^I$ (as $I$ is a model of $D$),

\item $(t,da_{\neg l},t^{+})\in DAS(\Delta _{QF}^I)$.

From Definition \ref{df17},

(i) $\delta =[t]FA_l \notin \Delta _{QF}^I$, and

(ii) there exists no action $\alpha \in {\cal A}_0$\ such that: 
\[
r=\frac{\Phi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\neg l }}
{\neg [\tau_2]l \wedge \neg [\tau_1]FA_l} \in {\cal R}
\] 
and 
$\Gamma \cup \Delta \models \Phi[\tau_1/t, \tau_2/t^{+}],
[t,t^{+}]\alpha,[t,t^{+}]AQ_{\neg l}$.

From Lemma \ref{le1}, $\delta \notin \Delta _{QF}^I$ iff $\delta $ is
rejected by $\Delta _{QF}^I$ iff --- as $I$ is a coherent model ---

either (a) there are $\alpha \in {\cal A}_0$ and $s \in {\Bbb T}$
such that
\[
r=\frac{\Phi ,[\tau_1,\tau_2]\alpha,[\tau_1,\tau_2]AQ_{\neg l }}
{\neg [\tau_2]l \wedge \neg [\tau_1]FA_l} \in {\cal R}
\] 
and $I\models prem(r)[\tau_1/s, \tau_2/t^{+}]$,

or (b) $I\models [t,t^{+}]da_{\neg l}$.

Since (a) violates condition (ii) above, (b) must be the case. Thus 
$(t,da_{\neg l},t^{+})\in Occ^I$.

$\Rightarrow DAS(\Delta _{QF}^I)\subseteq Occ^I$.
\end{itemize}

$\Rightarrow Occ^I\supseteq OA_D\cup DAS(\Delta _{QF}^I)$.

(3.$\subseteq $) Suppose that $Occ^I\not \subseteq OA_D\cup DAS(\Delta
_{QF}^I)$.
From (3.$\supseteq $), we have $Occ^I\supset OA_D\cup DAS(\Delta _{QF}^I)$.
Since $\Delta _{QF}^I$ is plausible, there exists a model $J\in Mod_{\Delta
_{QF}^I}^S(D)$ such that $J$ is a CPMM of $D$.
Following Definition \ref{df17}, $Occ^J=OA_D\cup DAS(\Delta _{QF}^I)$ which
is a proper subset of $Occ^I$. Contradiction!
Therefore, $Occ^I\subseteq OA_D\cup DAS(\Delta _{QF}^I)$.

Thus we have shown that $I\in Mod_{\Delta _{QF}^I}^S(D)$,

$\Rightarrow M\in \bigcup_{\Delta \in Plaus(D)}Mod_\Delta ^S(D)$ (Since $%
\Delta _{QF}^I\in Plaus(D)$)

$\Rightarrow CPMM(D)\subseteq \bigcup_{\Delta \in Plaus(D)}Mod_\Delta ^S(D)$.

Therefore, $CPMM(D)=\bigcup_{\Delta \in Plaus(D)}Mod_\Delta ^S(D)$.
\hspace*{\fill}$\Box$\\[2ex]

%% \newpage
\begin{aThe}{\bf \ \ref{th4}}
Let $D$ be a Q-domain. If $I$ is a CPMQM of $D$ then $\Delta
_{QF}^I$ is Q-plausible wrt $D$.\\[2ex]
\end{aThe}
\emph{Proof:} 

Suppose that $I$ is a CPMQM of $D$,

(i) it's easy to verify that $\Delta _{QF}^I$ is semi--Q-plausible wrt $D$:
similar to the proof of theorem \ref{th1}, but using Lemma \ref{le3} instead
of Lemma \ref{le1} and Lemma \ref{le2}.

(ii) $\Delta _{AQ}^I$ is maximal:

Assume the contrary, i.e. there exists a set of assumptions $\Delta $ such
that $\Delta $ is semi--Q-plausible wrt $D$ and $\Delta _{AQ}^I\subset
\Delta _{AQ}$.
Since $\Delta $ is presumable, $\Gamma \cup \Delta $ is ${\cal R}$%
-consistent.
Let $I_\Delta $ be the $\Delta $-relativised model of $D$. Obviously, $%
I_\Delta $ is a coherent Q-model of $D$.
It's easy to verify that $Occ^{I_\Delta }$ is minimal because otherwise a
coherent Q-model $J$ (of $D$) can be constructed such that $Occ^J\subset
Occ^{I_\Delta }$.
We have $Occ^{I_\Delta }=OA_D\cup DAS(\Delta )$ and $OA_D\subseteq Occ^J$
since $J$ is a model of $D$.
Thus there exists $(t,da_{\neg \varphi },t^{+})\in DAS(\Delta )\setminus
Occ^J$. But then $\Delta _{QF}^J$ is presumable wrt $D$ and $Lr(\Delta
_{QF}^J)\subset Lr(\Delta )$ which is a contradiction.
Thus, $Occ^{I_\Delta }$ is minimal. But then the model $I_\Delta $ is a PMQM
of $D$ and $AQ^{I_\Delta }\subset AQ^I$ which contradicts with the fact that 
$I$ is a CPMQM of $D$.
Therefore, $\Delta _{AQ}^I$ is maximal.

(iii) $\Delta _{FA}^I$ is maximal (relative to (i) and (ii)):

Assume the contrary, i.e. there exists a set of assumptions $\Delta $ such
that $\Delta $ is semi--Q-plausible wrt $D$ and $\Delta _{AQ}$ is maximal
and $\Delta _{FA}^I\subset \Delta _{FA}$.
Let $I_\Delta $ be the $\Delta $-relativised model of $D$. Similar to the
proof in part (ii), we can easily verify that $I_\Delta $ is a PMQM of $D$.
As the fact that $\Delta _{AQ}$ is maximal and $\Delta _{FA}^I\subset \Delta
_{FA}$ contradicts with the given hypothesis that $I$ is a CPMQM of $D$, we
conclude that $\Delta _{FA}^I$ is maximal.
Therefore, $\Delta _{QF}^I$ is Q-plausible wrt $D$.
\hspace*{\fill}$\Box$\\[2ex]

\begin{aThe}{\bf \ \ref{th5}}
Let $D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $ be a
Q-domain and $\Delta \subseteq {\cal AB}$. $\Delta $ is Q-plausible wrt $D$
iff $Mod_\Delta ^Q(D)\neq \emptyset $ and for each $I\in Mod_\Delta ^Q(D)$, $%
I$ is a CPMQM of $D$.\\[2ex]
\end{aThe}
\emph{Proof:} 

($\Rightarrow $) Suppose that $\Delta $ is Q-plausible wrt $D$.

As $\Delta $ is presumable, $\Gamma \cup \Delta $ is ${\cal R}$-consistent.
Following the construction of $\Delta $-relativised models, $Mod_\Delta
^Q(D)\neq \emptyset $.

Let $I\in Mod_\Delta ^Q(D)$:

(i) it's easy to verify that $I$ is coherent from the construction of $%
\Delta $-relativised models.

(ii) $Occ^I$ is minimal:

Assume the contrary, i.e. the set $\Sigma _I=\{\sigma $ $|$ $\sigma $ is a
coherent Q-model of $D$ and $Occ^\sigma \subset Occ^I\}$ is non-empty.

Let $J\in \Sigma _I$ such that the following conditions are satisfied:

1. there does not exist any model $\sigma \in \Sigma _I$ such that $%
Occ^\sigma \subset Occ^J$.

2. $AQ^J$ is maximal relative to 1.

3. $FA^J$ is maximal relative to 1. and 2.

Consider the set of assumptions $\Delta _{QF}^J$:
Obviously, $\Delta _{QF}^J$ is closed and does not attach itself.
For each $\delta \in {\cal AB}$, if $\delta \notin \Delta _{QF}^J$ then $%
\delta $ is rejected by $\Delta _{QF}^J$, otherwise it would violate the
maximality of $\Delta _{AQ}^J$ and $\Delta _{FA}^J$.
Thus, $\Delta _{QF}^J$ is presumable.

Remark that $Occ^J\subset Occ^I$. Besides, $Occ^I=OA_D\cup DAS(\Delta )$.
But $OA_D\subseteq Occ^J$ as $J$ is a model of $D$.
Thus there exists $(t,da_{\neg \varphi },t^{+})\in DAS(\Delta )\setminus
Occ^J$. But then $\Delta _{QF}^J$ is presumable wrt $D$ and $Lr(\Delta
_{QF}^J)\subset Lr(\Delta )$ which is a contradiction.
Thus, $Occ^I$ is minimal. As a consequence, $I$ is a PMQM of $D$.

(iii) $AQ^I$ is maximal (relative to (i) and (ii)):

Assume the contrary, i.e. the set $\Sigma _I=\{\sigma $ $|$ $\sigma $ is a
PMQM of $D$ and $AQ^I\subset AQ^\sigma \}$ is non-empty.

Let $J\in \Sigma _I$ such that the following conditions are satisfied:

1. $FA^J$ is maximal; and

2. $AQ^J$ is maximal relative to 1.

We can prove that that $\Delta _{QF}^J$ is semi-Q-plausible (i.e. presumable
wrt $D$ and $Lr_{FA}(\Delta _{QF}^J)$ is minimal):

That $\Delta _{QF}^J$ is presumable wrt $D$ is easy to verify.

It's also easy to verify that $Lr_{FA}(\Delta _{QF}^J)$ is minimal as $J$ is
coherent and $Occ^J$ is minimal. This would guarantee that the set of
occurrences of dummy actions in $J$ is minimised and as a consequence the set
of leniently rejected frame assumptions is also minimised. Formally, if a
presumable set of assumptions $\Pi $ is such that $Lr_{FA}(\Pi )\subset
Lr_{FA}(\Delta _{QF}^J)$ then the $\Delta $-relativised model $I_\Pi $ is a
coherent Q-model and $Occ^{I_\Pi }\subset Occ^J$, which is a contradiction
with the fact that $J\in \Sigma _I$ and thus $J$ is a PMQM of $D$.

Thus, $\Delta _{QF}^J$ is semi-Q-plausible wrt $D$. But, $\Delta
_{AQ}\subset \Delta _{AQ}^J$ which is a contradiction.

Therefore, we have shown that $AQ^I$ is maximal (relative to (i) and (ii)).

(iv) Now, we can prove that $FA^I$ is maximal (relative to (i), (ii) and
(iii)):

Assume the contrary, i.e. there exists a PMQM $J$ of $D$ such that $%
FA^I\subset FA^J$.

Among those models satisfying the above condition, we choose a model $K$
such that there does not exist any PMQM $K^{\prime }$ of $D$ such that $%
FA^K\subset FA^{K^{\prime }}$. Thus, $K$ is a CPMQM of $D$.

Following Theorem \ref{th4}, we have the set of assumptions $\Delta _{QF}^K$
is Q-plausible and $\Delta _{FA}\subset \Delta _{FA}^K$ since $FA^I\subset
FA^K$. Contradiction with the hypothesis that $\Delta $ is Q-plausible.

From (i), (ii), (iii) and (iv) we are led to the conclusion that $I$ is a
canonical prioritised minimal Q-model of $D$.

($\Leftarrow $) Suppose that $Mod_\Delta ^Q(D)\neq \emptyset $ and $I$ is a
canonical prioritised minimal model of $D$ for each $I\in Mod_\Delta ^Q(D)$,
we prove that $\Delta $ is plausible.

Take an arbitrary model $I\in Mod_\Delta ^Q(D)$. Following Observation \ref
{ob4}, $\Delta =\Delta _{QF}^I$. From Theorem \ref{th4} and the hypothesis
that $I$ is a canonical prioritised minimal Q-model of $D$, we conclude that 
$\Delta $ is Q-plausible. 
\hspace*{\fill}$\Box$\\[2ex]

\begin{aThe}{\bf \ \ref{th6}}
Let $D$ be a Q-domain. Furthermore, suppose that $CPMQM(D)$ is
the set of CPMQMs of $D$ and $Plaus^Q(D)$ is the set of Q-plausible sets of
assumptions of $D$, then $CPMQM(D)=\bigcup_{\Delta \in Plaus^Q(D)}Mod_\Delta
^Q(D)$. \\[2ex]
\end{aThe}
\emph{Proof:} Similar to the proof of Theorem~\ref{th3}.
\hspace*{\fill}$\Box$\\[2ex]

\begin{aThe}{\bf \ \ref{th7}}
Let $\sigma =\langle {\cal T},{\cal F},{\cal A}\rangle $\ be a signature and $%
D_0=\langle {\cal L}_D,{\cal R},{\cal AB},\emptyset \rangle $ a SSD and $%
\alpha \in {\cal A}_0$. Suppose that $w\in IS$. Define a domain description $%
D=\langle {\cal L}_D,{\cal R},{\cal AB},\Gamma \rangle $, where $\Gamma
=\{[\Theta ]\varphi $ $|$ $\varphi \in w\}\cup \{[\Theta ,\Theta ^{+}]\alpha
\}$. A set $\Delta \subseteq {\cal AB}$ of assumptions is AD-plausible wrt $%
D $ iff for each model $M$ of $E_D(\Delta )$, $[M]^{N_M(\Theta )}\in
Trans_D^\alpha ([M]^\Theta )$, i.e. $[M]^{N_M(\Theta )}$ belongs to the
state transition from $[M]^\Theta $ in $D$ according to $\alpha $. \\[2ex]
\end{aThe}
\emph{Proof:} 

($\Rightarrow $) Suppose that $\Delta \subseteq {\cal AB}$ is
AD-plausible wrt $D$, we prove that for each model $M$ of $E_D(\Delta )$, $%
[M]^{N_M(\Theta )}\in Trans_D^\alpha ([M]^\Theta )$.

Let $M\in Mod(E_D(\Delta ))$, as $M\models \Gamma $, we have $M\models
[\Theta ]\varphi $ iff $\varphi \in w$. Thus $w=[M]^\Theta $.

We prove that $[M]^{N_M(\Theta )}\in Trans_D^\alpha (w)$, i.e. there exists
a sequence $\omega _1,\ldots ,\omega _n\in IS$\ such that $(w,\alpha ,\omega
_1)\in Res_D$\ and $[M]^{N_M(\Theta )}=\omega _n$\ and $(\omega _i,\omega
_{i+1})\in Causes_D$\ for each $1\leq i<n$.

If $\Upsilon _\alpha ^w=\emptyset $: to the reasoner's knowledge, $\alpha $
is not applicable in the instantwise state $w$ due to either
non-executability of $\alpha $ in $w$, or $\alpha $ does not bring about any
effects concerned to the reasoner. Thus, $[M]^{\Theta ^{+}}=w$. Of course, $%
(w,\alpha ,[M]^{\Theta ^{+}})\in Res_D$.

If $\Upsilon _\alpha ^w\neq \emptyset $: let $\Omega =\{r\in {\cal R}_A$ $|$ 
$M\models prem(r)$ and $M\models cons(r)\}$, we prove that $\Omega $ is a
possible application of $\alpha $ in $w$.

Apparently, $\Omega \subseteq \Upsilon _\alpha ^w$. $\Omega $ is maximal
since otherwise we can construct a model $M^{\prime }$ such that $M^{\prime
} $ satisfies the qualification assumption of the additional action
description rule. But it means $M^{\prime }$ is a PMQM model of $D$ such
that $AQ^M\subset AQ^{M^{\prime }}$. Thus $M$ is not a CPMQM of $D$.
Following Theorem \ref{th5}, $\Delta $ is not Q-plausible wrt $D$.
Contradiction.

We now prove that there does not exists any instantwise state $S$ such that $%
CONS_A(\Omega )\subseteq S$ and $[M]^{\Theta ^{+}}\setminus w\subset
S\setminus w$.

Assume the contrary, i.e. there exists a fluent literal $\varphi \in {\cal F}%
^{*}$ such that $\varphi \in (S\setminus w)\setminus ([M]^{\Theta
^{+}}\setminus w)$.

Then $M\not \models [\Theta ]FA_\varphi $ since $M$ is a model of $D$.

Construct a model $M^{\prime }$ in such a way that $M^{\prime }$ interprets
everything the same as $M$ except $FA$, and $FA^{M^{\prime }}=FA^M\cup
\{(\Theta ,FA_\varphi )\}$. Obviously, $M^{\prime }$ is a PMQM of $D$ and $%
AQ^{M^{\prime }}=AQ^M$, but $FA^M\subset FA^{M^{\prime }}$. Thus $M$ is not
a CPMQM of $D$. Following Theorem \ref{th5}, $\Delta $ is not Q-plausible
wrt $D$. Contradiction.
Therefore, $(w,\alpha ,[M]^{\Theta ^{+}})\in Res_D$.

($\Leftarrow $) Suppose that for each model $M$ of $E_D(\Delta )$, $%
[M]^{N_M(\Theta )}\in Trans_D^\alpha ([M]^\Theta )$, we prove that $\Delta
\subseteq {\cal AB}$ is AD-plausible wrt $D$ which is obvious.
\hspace*{\fill}$\Box$

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%\bibliographystyle{plain}
%% \bibliographystyle{theapa}
%% \bibliography{ref}

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Amsterdam}{Amsterdam}{1991}]{amsterdam91temporal}
Amsterdam, J.~B. \BBOP1991\BBCP.
\newblock \BBOQ Temporal reasoning and narrative conventions\BBCQ\
\newblock In Allen, J.~F., Fikes, R., \BBA\ Sandewall, E.\BEDS, {\Bem {KR}'91:
  Principles of Knowledge Representation and Reasoning}, \BPGS\ 15--21,
  Cambridge, MA. Morgan Kaufmann.

\bibitem[\protect\BCAY{Baker}{Baker}{1989}]{Bak89}
Baker, A.~B. \BBOP1989\BBCP.
\newblock \BBOQ A simple solution to the {Yale Shooting} problem\BBCQ\
\newblock In Brachman, R.~J., Levesque, H.~J., \BBA\ Reiter, R.\BEDS, {\Bem
  {KR}'89: Principles of Knowledge Representation and Reasoning}, \BPGS\
  11--20, San Mateo, California. Morgan Kaufmann.

\bibitem[\protect\BCAY{Baral}{Baral}{1995}]{Bar95}
Baral, C. \BBOP1995\BBCP.
\newblock \BBOQ Reasoning about actions: Non-deterministic effects,
  constraints, and qualification\BBCQ\
\newblock In {\Bem International Joint Conference on Artificial Intelligence}.

\bibitem[\protect\BCAY{Bondarenko, Dung, Kowalski,\ \BBA\ Toni}{Bondarenko
  et~al.}{1997}]{BDK97}
Bondarenko, A., Dung, P.~M., Kowalski, R.~A., \BBA\ Toni, F. \BBOP1997\BBCP.
\newblock \BBOQ An abstract, argumentation-theoretic approach to default
  reasoning\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 93}, 63--101.

\bibitem[\protect\BCAY{Bracciali\ \BBA\ Kakas}{Bracciali\ \BBA\
  Kakas}{2004}]{bracciali04frame}
Bracciali, A.\BBACOMMA\  \BBA\ Kakas, A.~C. \BBOP2004\BBCP.
\newblock \BBOQ Frame consistency: computing with causal explanations\BBCQ\
\newblock In {\Bem 10th International Workshop on Non-Monotonic Reasoning (NMR
  2004)}, \BPGS\ 79--87.

\bibitem[\protect\BCAY{Castilho, Gasquet,\ \BBA\ Herzig}{Castilho
  et~al.}{1999}]{Cas99}
Castilho, M.~A., Gasquet, O., \BBA\ Herzig, A. \BBOP1999\BBCP.
\newblock \BBOQ {Formalizing action and change in modal logic I: The frame
  problem}\BBCQ\
\newblock {\Bem Journal of Logic and Computation}, {\Bem 9(5)}, 701--735.

\bibitem[\protect\BCAY{Dimopoulos, Kakas,\ \BBA\ Michael}{Dimopoulos
  et~al.}{2004}]{dimopoulos04reasoning}
Dimopoulos, Y., Kakas, A.~C., \BBA\ Michael, L. \BBOP2004\BBCP.
\newblock \BBOQ Reasoning about actions and change in answer set
  programming\BBCQ\
\newblock In {\Bem International Conference on Logic Programming and
  Nonmonotonic Reasoning - LPNMR' 04}, \BPGS\ 61--73.

\bibitem[\protect\BCAY{Doherty}{Doherty}{1994}]{doherty94reasoning}
Doherty, P. \BBOP1994\BBCP.
\newblock \BBOQ Reasoning about action and change using occlusion\BBCQ\
\newblock In {\Bem European Conference on Artificial Intelligence}, \BPGS\
  401--405.

\bibitem[\protect\BCAY{Doherty\ \BBA\ Kvarnstr{\"o}m}{Doherty\ \BBA\
  Kvarnstr{\"o}m}{1998}]{DK98}
Doherty, P.\BBACOMMA\  \BBA\ Kvarnstr{\"o}m, J. \BBOP1998\BBCP.
\newblock \BBOQ Tackling the qualification problem using fluent dependency
  constraints: Preliminary report\BBCQ\
\newblock In {\Bem 5th Workshop on Temporal Representation and Reasoning -
  TIME}, \BPGS\ 97--104.

\bibitem[\protect\BCAY{Doyle}{Doyle}{1979}]{Doy79}
Doyle, J. \BBOP1979\BBCP.
\newblock \BBOQ A truth maintenance system\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 12(3)}, 231--272.

\bibitem[\protect\BCAY{Drakengren\ \BBA\ Bj\protect{\"{a}}reland}{Drakengren\
  \BBA\ Bj\protect{\"{a}}reland}{1999}]{DB99}
Drakengren, T.\BBACOMMA\  \BBA\ Bj\protect{\"{a}}reland, M. \BBOP1999\BBCP.
\newblock \BBOQ Reasoning about action in polynomial time\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 115}, 1--24.

\bibitem[\protect\BCAY{Fikes\ \BBA\ Nilsson}{Fikes\ \BBA\ Nilsson}{1971}]{FN71}
Fikes, R.\BBACOMMA\  \BBA\ Nilsson, N.~J. \BBOP1971\BBCP.
\newblock \BBOQ {STRIPS: A new approach to the application of theorem proving
  to problem solving}\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 2(3/4)}, 189--208.

\bibitem[\protect\BCAY{Foo, Zhang, Vo,\ \BBA\ Peppas}{Foo
  et~al.}{2001}]{FZVP01}
Foo, N.~Y., Zhang, D., Vo, Q.~B., \BBA\ Peppas, P. \BBOP2001\BBCP.
\newblock \BBOQ Circumscriptive models and automata\BBCQ\
\newblock In Thielscher, M.\BBACOMMA\  \BBA\ Williams, M.-A.\BEDS, {\Bem
  Workshop on Non-monotonic Reasoning, Action and Change - colocated with
  IJCAI-01}.

\bibitem[\protect\BCAY{Gelfond\ \BBA\ Lifschitz}{Gelfond\ \BBA\
  Lifschitz}{1998}]{GL98}
Gelfond, M.\BBACOMMA\  \BBA\ Lifschitz, V. \BBOP1998\BBCP.
\newblock \BBOQ Action languages\BBCQ\
\newblock {\Bem Electronic Transactions on AI}, {\Bem 3(16)}, 193--210.

\bibitem[\protect\BCAY{Ginsberg\ \BBA\ Smith}{Ginsberg\ \BBA\
  Smith}{1988}]{GS88}
Ginsberg, M.~L.\BBACOMMA\  \BBA\ Smith, D.~E. \BBOP1988\BBCP.
\newblock \BBOQ {Reasoning about action I: A possible worlds approach}\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 35(2)}, 165--196.

\bibitem[\protect\BCAY{Giunchiglia, Kartha,\ \BBA\ Lifschitz}{Giunchiglia
  et~al.}{1997}]{giunchiglia97representing}
Giunchiglia, E., Kartha, G.~N., \BBA\ Lifschitz, V. \BBOP1997\BBCP.
\newblock \BBOQ Representing action: Indeterminacy and ramifications\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 95(2)}, 409--438.

\bibitem[\protect\BCAY{Giunchiglia\ \BBA\ Lifschitz}{Giunchiglia\ \BBA\
  Lifschitz}{1998}]{giunchiglia98action}
Giunchiglia, E.\BBACOMMA\  \BBA\ Lifschitz, V. \BBOP1998\BBCP.
\newblock \BBOQ An action language based on causal explanation: Preliminary
  report\BBCQ\
\newblock In {\Bem National Conference on Artificial Intelligence}, \BPGS\
  623--630.

\bibitem[\protect\BCAY{Green}{Green}{1969}]{Gre69}
Green, C. \BBOP1969\BBCP.
\newblock \BBOQ Application of theorem proving to problem solving\BBCQ\
\newblock In {\Bem International Joint Conference on Artificial Intelligence},
  \BPGS\ 219--240.

\bibitem[\protect\BCAY{Gustafsson\ \BBA\ Doherty}{Gustafsson\ \BBA\
  Doherty}{1996}]{gustafsson96embracing}
Gustafsson, J.\BBACOMMA\  \BBA\ Doherty, P. \BBOP1996\BBCP.
\newblock \BBOQ Embracing occlusion in specifying the indirect effects of
  actions\BBCQ\
\newblock In {\Bem Principles of Knowledge Representation and Reasoning},
  \BPGS\ 87--98.

\bibitem[\protect\BCAY{Haas}{Haas}{1987}]{Haa87}
Haas, A.~R. \BBOP1987\BBCP.
\newblock \BBOQ The case for domain-specific frame axioms\BBCQ\
\newblock In {\Bem The frame problem in artificial intelligence: proc. of 1987
  workshop}. Morgan Kaufmann.

\bibitem[\protect\BCAY{Hanks\ \BBA\ McDermott}{Hanks\ \BBA\
  McDermott}{1987}]{HM87}
Hanks, S.\BBACOMMA\  \BBA\ McDermott, D. \BBOP1987\BBCP.
\newblock \BBOQ Nonmonotonic logic and temporal projection\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 33(3)}, 379--412.

\bibitem[\protect\BCAY{Jr.}{Jr.}{1999}]{ortiz99explanatory}
Jr., C. L.~O. \BBOP1999\BBCP.
\newblock \BBOQ Explanatory update theory: Applications of counterfactual
  reasoning to causation\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 108(1-2)}, 125--178.

\bibitem[\protect\BCAY{Kakas, Miller,\ \BBA\ Toni}{Kakas et~al.}{1999}]{KMT99}
Kakas, A.~C., Miller, R., \BBA\ Toni, F. \BBOP1999\BBCP.
\newblock \BBOQ An argumentation framework of reasoning about actions and
  change\BBCQ\
\newblock In {\Bem International Conference on Logic Programming and
  Nonmonotonic Reasoning - LPNMR' 99}, \BPGS\ 78--91.

\bibitem[\protect\BCAY{Kakas, Miller,\ \BBA\ Toni}{Kakas et~al.}{2000}]{KMT00}
Kakas, A.~C., Miller, R., \BBA\ Toni, F. \BBOP2000\BBCP.
\newblock \BBOQ E-res - a system for reasoning about actions, events and
  observations\BBCQ\
\newblock In Baral, C.\BBACOMMA\  \BBA\ Truszczynski, M.\BEDS, {\Bem
  International Workshop on Non-Monotonic Reasoning, Special Session on System
  Descriptions and Demonstration - NMR'2000}.

\bibitem[\protect\BCAY{Kakas, Miller,\ \BBA\ Toni}{Kakas et~al.}{2001}]{KMT01}
Kakas, A.~C., Miller, R., \BBA\ Toni, F. \BBOP2001\BBCP.
\newblock \BBOQ E-res: Reasoning about actions, events and observations\BBCQ\
\newblock In {\Bem International Conference on Logic Programming and
  Nonmonotonic Reasoning - LPNMR' 01}, \BPGS\ 254--266.

\bibitem[\protect\BCAY{Kautz}{Kautz}{1986}]{Kau86}
Kautz, H. \BBOP1986\BBCP.
\newblock \BBOQ The logic of persistence\BBCQ\
\newblock In {\Bem National Conference on Artificial Intelligence}.

\bibitem[\protect\BCAY{Kowalski\ \BBA\ Sergot}{Kowalski\ \BBA\
  Sergot}{1986}]{KS86}
Kowalski, R.\BBACOMMA\  \BBA\ Sergot, M.~J. \BBOP1986\BBCP.
\newblock \BBOQ A logic-based calculus of events\BBCQ\
\newblock {\Bem New Generation Computing}, {\Bem 4}, 67--95.

\bibitem[\protect\BCAY{Kowalski}{Kowalski}{1992}]{Kow92}
Kowalski, R. \BBOP1992\BBCP.
\newblock \BBOQ Database updates in the event calculus\BBCQ\
\newblock {\Bem Journal of Logic Programming}, {\Bem 12}, 121--146.

\bibitem[\protect\BCAY{Kushmerick}{Kushmerick}{1996}]{Kus96}
Kushmerick, N. \BBOP1996\BBCP.
\newblock \BBOQ Cognitivism and situated action: two views on intelligent
  agency\BBCQ\
\newblock {\Bem Computers and Artificial Intelligence}, {\Bem 15(5)}.

\bibitem[\protect\BCAY{Lifschitz}{Lifschitz}{1987}]{Lif87}
Lifschitz, V. \BBOP1987\BBCP.
\newblock \BBOQ On the semantics of {STRIPS}\BBCQ\
\newblock In Georgeff\BBACOMMA\  \BBA\ Lansky\BEDS, {\Bem Reasoning about
  Actions and Plans}. Morgan Kauffman, Los Altos.

\bibitem[\protect\BCAY{Lin}{Lin}{1995}]{Lin95}
Lin, F. \BBOP1995\BBCP.
\newblock \BBOQ Embracing causality in specifying the indirect effects of
  actions\BBCQ\
\newblock In {\Bem International Joint Conference on Artificial Intelligence}.

\bibitem[\protect\BCAY{Lin}{Lin}{1996}]{lin96embracing}
Lin, F. \BBOP1996\BBCP.
\newblock \BBOQ Embracing causality in specifying the indeterminate effects of
  actions\BBCQ\
\newblock In {\Bem National Conference on Artificial Intelligence}, \BPGS\
  670--676.

\bibitem[\protect\BCAY{Lin\ \BBA\ Reiter}{Lin\ \BBA\ Reiter}{1994}]{LR94}
Lin, F.\BBACOMMA\  \BBA\ Reiter, R. \BBOP1994\BBCP.
\newblock \BBOQ State constraints revisited\BBCQ\
\newblock {\Bem Journal of Logic and Computation}, {\Bem 4(5)}, 655--678.

\bibitem[\protect\BCAY{Lin\ \BBA\ Shoham}{Lin\ \BBA\ Shoham}{1995}]{LS95}
Lin, F.\BBACOMMA\  \BBA\ Shoham, Y. \BBOP1995\BBCP.
\newblock \BBOQ Provably correct theories of action\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 42(2)}, 293--320.

\bibitem[\protect\BCAY{McCain\ \BBA\ Turner}{McCain\ \BBA\ Turner}{1995}]{MT95}
McCain, N.\BBACOMMA\  \BBA\ Turner, H. \BBOP1995\BBCP.
\newblock \BBOQ A causal theory of ramifications and qualifications\BBCQ\
\newblock In {\Bem International Joint Conference on Artificial Intelligence}.

\bibitem[\protect\BCAY{McCain\ \BBA\ Turner}{McCain\ \BBA\ Turner}{1997}]{MT97}
McCain, N.\BBACOMMA\  \BBA\ Turner, H. \BBOP1997\BBCP.
\newblock \BBOQ Causal theories of action and change\BBCQ\
\newblock In {\Bem National Conference on Artificial Intelligence}, \BPGS\
  460--465.

\bibitem[\protect\BCAY{McCarthy}{McCarthy}{1977}]{McC77}
McCarthy, J. \BBOP1977\BBCP.
\newblock \BBOQ Epistemological problems of artificial intelligence\BBCQ\
\newblock In {\Bem International Joint Conference on Artificial Intelligence},
  \BPGS\ 555--562.

\bibitem[\protect\BCAY{McCarthy}{McCarthy}{1980}]{McC80}
McCarthy, J. \BBOP1980\BBCP.
\newblock \BBOQ Circumscription - a form of non-monotonic reasoning\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 13(1-2)}, 27--39.

\bibitem[\protect\BCAY{McCarthy}{McCarthy}{1986}]{McC86}
McCarthy, J. \BBOP1986\BBCP.
\newblock \BBOQ Applications of circumscription to formalizing common sense
  knowledge\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 26(3)}, 89--116.

\bibitem[\protect\BCAY{McCarthy\ \BBA\ Hayes}{McCarthy\ \BBA\
  Hayes}{1969}]{MH69}
McCarthy, J.\BBACOMMA\  \BBA\ Hayes, P. \BBOP1969\BBCP.
\newblock \BBOQ Some philosophical problems from the standpoint of artificial
  intelligence\BBCQ\
\newblock In Michie, D.\BBACOMMA\  \BBA\ Meltzer, B.\BEDS, {\Bem Machine
  Intelligence 4}. Edinburgh University Press.

\bibitem[\protect\BCAY{McDermott}{McDermott}{1987}]{McD87}
McDermott, D.~V. \BBOP1987\BBCP.
\newblock \BBOQ We've been framed: Or why ai is innocent of the frame
  problem\BBCQ\
\newblock In Pylyshyn, Z.\BED, {\Bem The Robots Dilemma: The Frame Problem in
  Artificial Intelligence}, \BPGS\ 113--122. Ablex.

\bibitem[\protect\BCAY{McDermott\ \BBA\ Doyle}{McDermott\ \BBA\
  Doyle}{1980}]{MD80}
McDermott, D.~V.\BBACOMMA\  \BBA\ Doyle, J. \BBOP1980\BBCP.
\newblock \BBOQ {Non-monotonic logic I}\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 13(1-2)}, 41--72.

\bibitem[\protect\BCAY{Moore}{Moore}{1985}]{Moo85}
Moore, R.~C. \BBOP1985\BBCP.
\newblock \BBOQ Semantical considerations on nonmonotonic logic\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 25(1)}, 75--94.

\bibitem[\protect\BCAY{Morris}{Morris}{1988}]{Mor88}
Morris, P.~H. \BBOP1988\BBCP.
\newblock \BBOQ The anomalous extension problem in default reasoning\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 35(3)}, 383--399.

\bibitem[\protect\BCAY{Pednault}{Pednault}{1989}]{Ped89}
Pednault, E. \BBOP1989\BBCP.
\newblock \BBOQ {ADL: Exploring the middle ground between STRIPS and the
  situation calculus}\BBCQ\
\newblock In {\Bem KR'89: First International Conference on Principles of
  Knowledge Representation and Reasoning}, \BPGS\ 324--332. Morgan Kaufmann.

\bibitem[\protect\BCAY{Poole}{Poole}{1988}]{poole88logical}
Poole, D. \BBOP1988\BBCP.
\newblock \BBOQ A logical framework for default reasoning\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 36(1)}, 27--47.

\bibitem[\protect\BCAY{Reiter}{Reiter}{1980}]{Rei80}
Reiter, R. \BBOP1980\BBCP.
\newblock \BBOQ A logic for default reasoning\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 13}, 81--132.

\bibitem[\protect\BCAY{Reiter}{Reiter}{1991}]{Rei91}
Reiter, R. \BBOP1991\BBCP.
\newblock \BBOQ The frame problem in the situation calculus: A simple solution
  (sometimes) and a completeness result for goal regression\BBCQ\
\newblock In Lifschitz, V.\BED, {\Bem AI and Mathematical Theory of
  Computation: Papers in Honor of John McCarthy}, \BPGS\ 418--420. Academic
  Press.

\bibitem[\protect\BCAY{Sandewall}{Sandewall}{1994}]{San94}
Sandewall, E. \BBOP1994\BBCP.
\newblock {\Bem Features and Fluents}.
\newblock Oxford University Press, Oxford.

\bibitem[\protect\BCAY{Schubert}{Schubert}{1990}]{Sch90}
Schubert, L. \BBOP1990\BBCP.
\newblock \BBOQ Monotonic solution of the frame problem in the situation
  calculus; an efficient method for worlds with fully specified actions\BBCQ\
\newblock In Kyburg, H., Loui, R., \BBA\ Carlson, G.\BEDS, {\Bem Knowledge
  Representation and Defeasible Reasoning}, \BPGS\ 23--67. Kluwer Academic
  Publishers, Dordrecht.

\bibitem[\protect\BCAY{Shanahan}{Shanahan}{1989}]{Sha89}
Shanahan, M. \BBOP1989\BBCP.
\newblock \BBOQ Prediction is deduction but explanation is abduction\BBCQ\
\newblock In {\Bem International Joint Conference on Artificial Intelligence},
  \BPGS\ 1055--1060.

\bibitem[\protect\BCAY{Shanahan}{Shanahan}{1997}]{Sha97}
Shanahan, M. \BBOP1997\BBCP.
\newblock {\Bem Solving the Frame Problem: A Mathematical Investigation of the
  Common Sense Law of Inertia}.
\newblock MIT Press, Cambridge, Massachussets.

\bibitem[\protect\BCAY{Shanahan}{Shanahan}{1999}]{shanahan99ramification}
Shanahan, M. \BBOP1999\BBCP.
\newblock \BBOQ The ramification problem in the event calculus\BBCQ\
\newblock In {\Bem International Joint Conference on Artificial Intelligence},
  \BPGS\ 140--146.

\bibitem[\protect\BCAY{Shoham}{Shoham}{1987}]{shoham87reasoning}
Shoham, Y. \BBOP1987\BBCP.
\newblock {\Bem Reasoning about Change}.
\newblock MIT Press, Cambridge, MA.

\bibitem[\protect\BCAY{Shoham}{Shoham}{1988}]{shoham88chronological}
Shoham, Y. \BBOP1988\BBCP.
\newblock \BBOQ Chronological ignorance: Experiments in nonmonotonic temporal
  reasoning\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 36}, 279--331.

\bibitem[\protect\BCAY{Stein\ \BBA\ Morgenstern}{Stein\ \BBA\
  Morgenstern}{1994}]{stein94motivated}
Stein, L.~A.\BBACOMMA\  \BBA\ Morgenstern, L. \BBOP1994\BBCP.
\newblock \BBOQ Motivated action theory: a formal theory of causal
  reasoning\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 71(1)}, 1--42.

\bibitem[\protect\BCAY{Thielscher}{Thielscher}{1997}]{Thi97}
Thielscher, M. \BBOP1997\BBCP.
\newblock \BBOQ Ramification and causality\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 89}, 317--364.

\bibitem[\protect\BCAY{Thielscher}{Thielscher}{1999}]{thielscher97from}
Thielscher, M. \BBOP1999\BBCP.
\newblock \BBOQ From situation calculus to fluent calculus: State update axioms
  as a solution to the inferential frame problem\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 111(1-2)}, 277--299.

\bibitem[\protect\BCAY{Thielscher}{Thielscher}{2001}]{thielscher01qualificatio%
n}
Thielscher, M. \BBOP2001\BBCP.
\newblock \BBOQ The qualification problem: A solution to the problem of
  anomalous models\BBCQ\
\newblock {\Bem Artificial Intelligence Journal}, {\Bem 131(1-2)}, 1--37.

\bibitem[\protect\BCAY{Turner}{Turner}{1997}]{Tur97}
Turner, H. \BBOP1997\BBCP.
\newblock \BBOQ Representing actions in logic programs and default theories: A
  situation calculus approach\BBCQ\
\newblock {\Bem Journal of Logic Programming}, {\Bem 31(1-3)}, 245--298.

\bibitem[\protect\BCAY{Vo\ \BBA\ Foo}{Vo\ \BBA\ Foo}{2001}]{VF01}
Vo, Q.~B.\BBACOMMA\  \BBA\ Foo, N.~Y. \BBOP2001\BBCP.
\newblock \BBOQ Solving the qualification problem\BBCQ\
\newblock In {\Bem Australian Joint Conference on Artificial Intelligence},
  \BPGS\ 519--531.

\bibitem[\protect\BCAY{Vo\ \BBA\ Foo}{Vo\ \BBA\ Foo}{2002}]{VF02}
Vo, Q.~B.\BBACOMMA\  \BBA\ Foo, N.~Y. \BBOP2002\BBCP.
\newblock \BBOQ Solving the ramification problem: Causal propagation in an
  argumentation-theoretic approach\BBCQ\
\newblock In {\Bem 7th Pacific Rim International Conference on Artificial
  Intelligence - PRICAI2002}, \BPGS\ 49--59.

\bibitem[\protect\BCAY{Zhang\ \BBA\ Foo}{Zhang\ \BBA\ Foo}{2002}]{FZ01}
Zhang, D.\BBACOMMA\  \BBA\ Foo, N.~Y. \BBOP2002\BBCP.
\newblock \BBOQ Interpolation properties of action logic: Lazy-formalization to
  the frame problem\BBCQ\
\newblock In Flesca, S., Greco, S., Leone, N., \BBA\ Ianni, G.\BEDS, {\Bem
  Logics in Artificial Intelligence, European Conference, JELIA 2002}, \BPGS\
  357--368.

\end{thebibliography}

%% \include{appendix/raa_app}
%% \printindex
\end{document}
