%-*- Mode: Latex; Default-character-style: (:SWISS :ROMAN :LARGE) -*-

\documentstyle[12pt]{article}

\input{z:>elisha>paper>illustrations.tex}
\def\illustrationfileprefix{z:>elisha>ill>}

\setlength{\unitlength}{0.1in}
\renewcommand{\baselinestretch}{1.2}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\topmargin}{0pt}
\setlength{\textheight}{8in}
\setlength{\textwidth}{6.5in}

\newcommand{\bounder}{{\sc bounder}}
\newcommand{\reg}[1]{\mbox{$\langle#1\rangle$}}

\begin{document}

\begin{titlepage}
\begin{center}
{\large\bf A Dynamic Systems Perspective on Qualitative Simulation}\\

Elisha Sacks%
\footnote{This research was performed while I was in the Clinical
Decision Making Group of the M.I.T. Laboratory for Computer Science.
It was supported (in part) by National Institutes of Health Grant No.\
R01 LM04493 from the National Library of Medicine.}\\ 
Department of Computer Science\\
Princeton University\\
Princeton, NJ 08544
\end{center}

\begin{abstract}
\noindent
This paper examines qualitative simulation (QS) from the phase space
perspective of dynamic systems theory.  QS consists of two steps:
{\em transition analysis\/} determines the sequence of qualitative
states that a system traverses and {\em global interpretation\/} derives
its long-term behavior.  I recast transition analysis as a search problem
in phase space and replace the assorted transition rules with two
algebraic conditions.  The first condition determines transitions between
arbitrarily shaped regions in phase space, as opposed to QS which only
handles $n$-dimensional rectangles.  It also provides more accurate
results by considering only the boundaries between regions.  The
second condition determines whether nearby trajectories approach a
fixed point asymptotically.  It obtains better results than QS by
exploiting local stability properties.  I recast global interpretation as a
search for attractors in phase space and present a global interpretation
algorithm for systems whose local behavior determines global behavior
uniquely.  
\end{abstract}

\end{titlepage}

\section{Introduction}

Qualitative reasoning seeks to automate the analysis of dynamic
systems whose exact workings are unimportant to the problem task,
complicated, or unknown.  For example, a computer chef should be
able to infer that turning up the flame under a pot increases the
temperature of its contents without solving heat conduction equations.
Current qualitative reasoning programs derive the abstract behavior of
a system by simulating qualitative versions of its governing equations.
This paper examines qualitative simulation (QS) from the phase space
perspective of dynamic systems theory.

The next section translates AI qualitative reasoning terminology into
the phase space representation.  QS consists of two steps: 
{\em transition analysis\/} determines the sequence of qualitative
states that a system traverses and {\em global interpretation\/} derives
its long-term behavior.  Sections~\ref{s-trans} and~\ref{s-fpa} recast
transition analysis as a search problem in phase space and replace the
assorted transition rules with two algebraic conditions.  These
conditions are more general and more accurate than the original
transition rules.  Section~\ref{s-global} recasts global interpretation as
a search for attractors in phase space.  It presents a global
interpretation algorithm for systems whose local behavior determines
global behavior uniquely.  The final section contains conclusions and
plans future work on global interpretation. 

This paper addresses a generic form of QS, couched in terms of
abstract differential equations that contain arbitrary constants and
functions.  The ideas apply to every formalism in the qualitative
reasoning literature as well.  The discussion pertains solely to
input/output behavior and efficiency, not to cognitive or philosophical
issues.  It makes no claims about {\em human\/} reasoning methods or
about the putative causal ordering that QS imposes on systems.  See
de Kleer and Brown \cite{dekleer6,deKleer-Brown86} and Iwasaki and
Simon \cite{iwasaki86a,iwasaki86b} for a discussion of these issues.

\section{Qualitative Reasoning in Phase Space}

The phase space for a system of first-order differential equations
\begin{equation}\label{e-system}
x_i'=f_i(x_1,\ldots,x_n);\; i=1,\ldots,n
\end{equation}
is the Cartesian product of the $x_i$'s domains.   One can convert
higher-order equations to first-order ones by introducing new variables
as synonyms for higher derivatives.  Points in phase space represent
states of the system.  Curves on which equation~(\ref{e-system}) is
satisfied, called {\em trajectories,} represent solutions.  A {\em phase
diagram\/} for a system depicts its phase space and trajectories
graphically.  The topological and geometric properties of trajectories
characterize the qualitative behavior of solutions.  For example, a
point trajectory, called a {\em fixed point,} indicates a constant
solution, whereas a closed curve indicates a periodic solution.  A fixed
point is {\em stable\/} if every nearby trajectory approaches it
asymptotically, {\em repellent\/} if every nearby trajectory diverges
from it, and {\em unstable\/} otherwise. 

For example, the motion of a block attached to a track from below and
to an elastic band from above (Figure~\ref{f-block}) is typically
modeled by the abstract equations
\begin{equation}\label{e-block}
\left\{\begin{array}{l}
        x'=v\\
        v'=g(x)+h(v)
\end{array}\right.
\end{equation}
where $x$ and $v$ denote the location and velocity of the block.  The
functions $g(x)$ and $h(v)$ decrease monotonically and vanish at
zero, but are otherwise arbitrary.  They represent the elastic and
frictional forces.  (I ignore static friction for simplicity.)
Figure~\ref{f-pblock} shows a typical phase diagram for
equation~(\ref{e-block}).  The system has a single stable fixed point,
$(0,0)$, toward which all other trajectories spiral.  The fixed point
represents the steady state in which the block lies at rest directly
beneath the ceiling.  The spirals represent the decaying oscillations
that arise when the block is displaced from the steady state.

\begin{figure}[htbp]
\illustration{block}{1.35in}
\caption{A block attached to an elastic band.}\label{f-block}  
\end{figure}

\begin{figure}[htbp]
\illustration{pblock}{1.5in}
\caption{Phase diagram for the block equation
          (\protect\ref{e-block}).}\label{f-pblock}
\end{figure}

The QS representation translates directly into phase space terminology.
QS manipulates abstract versions of numbers, called {\em qualitative
values,} organized in {\em quantity spaces:} ordered sets of alternating
intervals and points.  One useful quantity space, called IQ, consists of
the interval $(-\infty,0)$, the point 0, and the interval $(0,\infty)$.  
These abbreviate to $-$, $0$, and $+$.  QS models systems with sets
of {\em quantities:} functions from an independent variable (usually
time) to quantity spaces.  Define the {\em qualitative state\/} of a
system to be the vector of the qualitative values of its quantities.  QS
characterizes the behavior of a system by the sequences of qualitative
states that it can go through.  It represents this information with a
{\em transition graph\/} whose nodes and links denote qualitative
states and possible transitions.

Qualitative values correspond to intervals and points on the real line.
Quantities correspond to phase variables.  Let $Q_i$ denote the
quantity space for quantity $q_i$.  Each qualitative state of a system
with quantities $q_1,\ldots,q_n$ maps to an $n$-dimensional rectangle
in the Cartesian product $Q_1\times\cdots\times Q_n$.  QS cannot
represent non-rectangular regions, such as circles, because the
components of qualitative states are independent.  Qualitative state
transitions correspond to transitions between regions in phase space, so
transition graphs specify the sequences of regions that trajectories
traverse.  The qualitative behaviors of a system are isomorphic to the
paths in its transition graph.

For example, the simplest QS formulation of the block example
represents $x$ and $v$ as IQ-valued quantities.  Figure~\ref{f-tgraph}
shows the transition graph that QS derives for these values.  The phase
space representation of the system appears in Figure~\ref{f-qrspace}.
The nine qualitative states map into four rectangles (\reg{\pm,\pm}),
four line segments (\reg{\pm,0}), and one fixed point (\reg{0,0}).  The
phase space interpretation of the transition graph is that every solution
either remains at \reg{0,0} forever, cycles clockwise through the outer
eight regions forever, or cycles for a while and then approaches
\reg{0,0} from within \reg{-,+} or \reg{+,-}.  In fact, all trajectories 
are eventually trapped in  every circle centered at the origin, but one
cannot represent this information as a sequence of transitions between
rectangular regions.  

\begin{figure}[htbp]
\centering

$\begin{array}{ccccc}
\reg{-,+} & \rightarrow & \reg{0,+} & \rightarrow & \reg{+,+}\\
\uparrow & \searrow    &             &               & \downarrow\\
\reg{-,0} &               & \reg{0,0} &               & \reg{+,0}\\
\uparrow &               &             & \nwarrow   & \downarrow\\
\reg{-,-} & \leftarrow   & \reg{0,-} & \leftarrow  & \reg{+,-}
\end{array}$
\caption{Transition graph for the block.}\label{f-tgraph}
\end{figure}

\begin{figure}[htbp]
\begin{picture}(21,21)(-22,0)
\put(10,20){\vector(0,1){0}}
\multiput(10,0)(0,.5){39}{\makebox(0,0){\tiny.}}
\put(10,21){\makebox(0,0){$v$}}
\put(20,10){\vector(1,0){0}}
\multiput(0,10)(.5,0){39}{\makebox(0,0){\tiny.}}
\put(21,10){\makebox(0,0){$x$}}
\put(5,5){\makebox(0,0){\reg{-,-}}}
\put(10,5){\makebox(0,0){\reg{0,-}}}
\put(15,5){\makebox(0,0){\reg{+,-}}}
\put(5,10){\makebox(0,0){\reg{-,0}}}
\put(10,10){\makebox(0,0){\reg{0,0}}}
\put(15,10){\makebox(0,0){\reg{+,0}}}
\put(5,15){\makebox(0,0){\reg{-,+}}}
\put(10,15){\makebox(0,0){\reg{0,+}}}
\put(15,15){\makebox(0,0){\reg{+,+}}}
\end{picture}

\caption{Phase space representation of qualitative states for the
           block.}\label{f-qrspace} 
\end{figure}

The next two sections examine transition analysis in a phase space
setting.  Transitions involving fixed points are different from those
between other regions.  From here on, let the term {\em region\/}
denote regions other than fixed points.  There are two cases to
consider: transitions between regions and transitions from regions to
fixed points.  Transitions out of fixed points cannot occur by definition. 

\section{Transitions Between Regions}\label{s-trans}

QS calculates the successors of a qualitative state from the signs of
its derivatives.  It derives the signs from the governing equations and
infers the transitions from the intermediate value and mean value
theorems.  (It assumes that solutions are piecewise smooth.)  For
example, given the state $y<0$ and $y'>0$, it concludes that $y$ may
enter the state $y=0$, but cannot enter $y>0$ directly.  The QS
transition rules map directly to phase space.  Let regions $R$ and $S$
be adjacent along the boundary $x_i=k$ with $x_i\leq k$ for $x\in R$
and $x_i\geq k$ for $x\in S$.  QS derives a transition from $R$ to
$S$ unless the governing equations imply $x'_i\leq0$ for every 
$x\in R$ and one from $S$ to $R$ unless the equations imply
$x'_i\geq0$ for every $x\in S$.  In the block example, $x'>0$ on
\reg{-,+} and \reg{0,+} by equation~(\ref{e-block}).  Hence, there
is a transition from \reg{-,+} to \reg{0,+}, but not from \reg{0,+} to
\reg{-,+}.  Figure~\ref{f-qstrans} depicts this example as well as
symmetric transitions between two regions.

\begin{figure}[htbp]
\begin{picture}(65,11)
\put(19,0){\makebox(0,0){(a)}}
\thicklines
\put(23,1){\line(0,1){4}}
\put(23,7){\line(0,1){4}}
\thinlines
\put(15,6){\makebox(0,0){\reg{-,+}}}
\put(23,6){\makebox(0,0){\reg{0,+}}}
\put(19,3.5){\vector(1,0){2}}
\put(19,8.5){\vector(1,0){2}}
\put(15,3.5){\vector(1,0){2}}
\put(15,8.5){\vector(1,0){2}}
\put(23,3.5){\vector(1,0){2}}
\put(23,8.5){\vector(1,0){2}}

\put(44,0){\makebox(0,0){(b)}}
\thicklines
\put(48,1){\line(0,1){4}}
\put(48,7){\line(0,1){4}}
\thinlines
\put(40,6){\makebox(0,0){$R$}}
\put(48,6){\makebox(0,0){$S$}}
\put(42,3.5){\vector(1,0){2}}
\put(44,8.5){\vector(-1,0){2}}
\put(38,3.5){\vector(1,0){2}}
\put(40,8.5){\vector(-1,0){2}}
\put(48,3.5){\vector(1,0){2}}
\put(48,8.5){\vector(-1,0){2}}
\end{picture}
\caption{Sample transitions.  Arrows indicate $x$'s direction of change.
          (a) from \reg{-,+} to \reg{0,+}, but not from \reg{0,+} to \reg{-,+}.
          (b) from $R$ to $S$ and from $S$ to $R$.} \label{f-qstrans}
\end{figure}

The QS transition analysis algorithm only applies to regions whose 
boundaries have the form $x_i=k$.  This prevents QS from reasoning
about regions such as $u>v$ and $u^2+v^2<k$ that have slanted and
circular boundaries respectively.  Also, the QS algorithm can produce
spurious transitions when a derivative takes on positive and negative
values within a single region.  For example, given the equation
$y'=y-y^2$, $y'$ is positive for $y\in(0,1)$ and negative for
$y\in(1,\infty)$.  QS derives a transition from $(0,\infty)$ to $0$ even
though $y$ moves away from $0$ in $(0,1)$, as shown in
Figure~\ref{f-spurious}.  In this case, one can solve the problem by
including the critical points of $y$, $0$ and $1$, in its value space.
This solution becomes cumbersome for systems with many critical
points and impossible when the critical points of one variable depend
on another variable.

\begin{figure}[htbp]
\begin{picture}(30,3)(-17.5,0)
\put(10,0){\makebox(0,0){$0$}}
\put(20,0){\makebox(0,0){$1$}}
\put(0,2){\line(1,0){30}}
\put(10,2){\circle*{.5}}
\put(20,2){\circle*{.5}}
\put(2.5,2){\vector(-1,0){0}}
\put(5,2){\vector(-1,0){0}}
\put(7.5,2){\vector(-1,0){0}}
\put(12.5,2){\vector(1,0){0}}
\put(15,2){\vector(1,0){0}}
\put(17.5,2){\vector(1,0){0}}
\put(22.5,2){\vector(-1,0){0}}
\put(25,2){\vector(-1,0){0}}
\put(27.5,2){\vector(-1,0){0}}
\end{picture}
\caption{Phase diagram for $y'=y-y^2$.  All solutions in $(0,1)$ move
          away from $0$.}\label{f-spurious}
\end{figure}

A phase space perspective generalizes transition analysis to regions
bounded by smooth curves and eliminates the spurious transitions
discussed above.   For a trajectory to cross from region $R$ to $S$
via boundary $u$, its tangent $t$ at the intersection point with $u$
must form an acute angle with the normal $n$, as shown in
Figure~\ref{f-transition}.  In algebraic terms, the inner product 
$t\cdot n$ must be positive.  Hence, a transition exists from $R$ to
$S$ unless $t\cdot n\leq0$ everywhere on $u$.  This condition applies
to any smooth boundary.  It reduces to the QS transition condition,
$x'_i\leq0$, in the special case where $u$ has the form $x_i=k$.  

\begin{figure}[htbp]
\illustration{transition}{2in}
\caption{Trajectory crossing from $R$ to $S$ via $u$. The tangent $t$
           at the crossing point must form an acute angle with $n$, the 
           normal to $u$ that points into $S$.}\label{f-transition}   
\end{figure}

The condition $t\cdot n\leq0$ is evaluated on the boundaries between
regions, making it insensitive to changes in the signs of derivatives
within a region.  In our example, $y'=0$ at the boundary, $0$, between
$(0,\infty)$ and $0$, ruling out a transition to $0$.  In the block
example, $x'>0$ on the boundary, \reg{0,+}, between \reg{-,+} and
\reg{0,+}.  This result agrees with the QS prediction because $x'>0$
throughout \reg{-,+}.  The general case of regions $R$ and $S$
adjacent along $x_i=k$ and governed by equation~(\ref{e-system}) is
analogous.  A transition from $R$ to $S$ occurs unless
\begin{equation}
\lim_{x_i\uparrow k}f_i(x_1,\ldots,x_n)\leq 0
\end{equation}
for all $x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n$ in $R$.  The limit
reduces to $f_i(x_1,\ldots,x_{i-1},k,x_{i+1},\ldots,x_n)$ when  $f_i$ is
continuous from below or when $R$ has zero width in dimension $i$.
Conversely, a transition from $S$ to $R$ occurs unless 
\begin{equation}
\lim_{x_i\downarrow k}f_i(x_1,\ldots,x_n)\geq 0
\end{equation}
for all $x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n$ in $S$.  The limit
reduces to $f_i(x_1,\ldots,x_{i-1},k,x_{i+1},\ldots,x_n)$ when $f_i$ is
continuous from above or when $S$ has zero width in dimension $i$.
These reductions apply to all current QS systems because all
researchers have assumed one-sided (but not two-sided) continuity.

The accuracy of these transition conditions depends on the specificity
of the system equations and on the power of the inequality prover.  If
only sign equations are available, as in de Kleer and Brown
\cite{dekleer6}, one must evaluate the above inequalities by 
{\em qualitative arithmetic,} a special case of interval arithmetic
\cite{moore}.  Better results are possible when algebraic equations are
available, as in the models of Forbus \cite{forbus84} and Kuipers
\cite{kuipers86}.  Powerful inequality provers can rule out impossible
transitions that qualitative arithmetic endorses, perhaps at the cost of
increased computational complexity.  I discuss the tradeoffs between
power and efficiency in existing inequality provers elsewhere
\cite{sacks87a} \cite[Ch.~7]{sacks88b}.  These tradeoffs are
orthogonal to the improvement over QS obtained by examining the
boundaries between regions. 

\section{Transitions between Regions and Fixed Points}\label{s-fpa}

Some QS researchers, including Kuipers, derive transitions from regions
to fixed points in the same manner as transitions between regions. 
Others, including de Kleer and Bobrow \cite{dekleer2}, rule them out
altogether.  An analytic function can be constant on an interval only if
it is always constant; hence, a moving trajectory cannot come to rest.
Neither approach accurately describes the underlying phenomena.
Moving trajectories cannot, in fact, reach fixed points in {\em finite\/}
time, but they can approach fixed points asymptotically.  Moreover, the
stability characteristics of fixed points govern the transitions from
adjacent regions.  Programs that apply the inter-regional transition rule
to this case can overlook important inferences.  This section describes
an algorithm, called FPA (for fixed point analysis), that derives the
transitions into fixed points from their stability characteristics.

FPA calculates the fixed points of a system of differential equations
$$
x_i'=f_i(x_1,\ldots,x_n);\; i=1,\ldots,n \eqno (\ref{e-system})
$$
by setting all derivatives to zero and solving the resulting equations.  In
the block example, it solves
\begin{equation}
\left\{\begin{array}{l}
         v=0\\
         g(x)+h(v)=0
\end{array}\right.
\end{equation}
to obtain the unique fixed point: $(0,0)$.  The solution follows from
the constraints on $g$ and $h$.  Sufficiently complicated systems can
cause any equation solver to fail.  This should rarely be a problem for
FPA, given the simplicity of the equations in the qualitative reasoning
literature.

FPA tests whether each fixed point that it calculates is stable or
repellent.  If a fixed point $p$ is stable, every trajectory that passes
near $p$ converges to it.  Transitions exist from each of $p$'s
neighbors to $p$ because each neighbor contains points arbitrarily near
$p$.  If $p$ is repellent, every trajectory that passes near $p$ diverges
from it.  Hence, there are no transitions into $p$.

A fixed point $p$ of~(\ref{e-system}) is stable (repellent) exactly when
all the eigenvalues of the $n$-by-$n$ matrix
\begin{equation}\label{e-partials}
A(x)=(a_{ij})\;\mbox{with}\;a_{ij}=\frac{\partial}{\partial x_j}
      f_i(x_1,\ldots,x_n)
\end{equation}
have negative (positive) real parts at $x=p$ \cite[Ch.~9]{hirsch74}.
To determine stability, FPA first ignores the magnitudes of the $a_{ij}$
and tests whether their signs alone imply stability.  This condition,
called {\em sign stability,} is easier to ascertain than the weaker
condition of stability, but rarer.  The sign pattern of $A$ expresses the
direction of influence between variables in the neighborhood of $p$.
The $j$th variable influences the $i$th variable positively if
$a_{ij}>0$, not at all if $a_{ij}=0$, and negatively if $a_{ij}<0$.  A
sign stable matrix is one in which this qualitative information implies
stability.    

Sign stability is the strongest condition derivable in formalisms, such as
de Kleer's, where the magnitudes of the $a_{ij}$ are unspecified.  If
$-A=(-a_{ij})$ is sign stable, there are no transitions into $p$.  If not,
there exists an unstable instance of $-A$, hence an instance of $A$
with a negative eigenvalue.  For this instance, every neighborhood of
$p$ contains points whose trajectories approach $p$ asymptotically
\cite[Ch.~1]{guckenheimer86}.  The transition graph must include links
into $p$ from each adjacent region to cover this case. 

Sign stability does not distinguish between spiral and nodal approach to
a fixed point (Figure~\ref{f-approach}) because the magnitudes of the
$a_{ij}$ determine these properties.  In the two-dimensional case, for
example, trajectories spiral for
\begin{equation}\label{e-delta}
\Delta=(a_{11}-a_{22})^2+4a_{12}a_{21}<0
\end{equation}
and are nodal otherwise.  Given only the signs of the $a_{ij}$, QS can
do no better.  I discuss constraints on the magnitudes of the $a_{ij}$
at the end of this section. 

\begin{figure}[htbp]
\illustration{approach}{1in}
\caption{Spiral versus nodal approach to a fixed
           point.}\label{f-approach}
\end{figure}

FPA calculates the $a_{ij}$ from the system~(\ref{e-system}) and
derives their signs with the \bounder\ inequality reasoner
\cite{sacks87a}.  In the block example~(\ref{e-block}), the matrix
\begin{equation}
A(x,v)=
   \left[\begin{array}{cc}
           \frac{\partial}{\partial x} v & \frac{\partial}{\partial v} v\\
           \frac{\partial}{\partial x}(g(x)+h(v)) &
           \frac{\partial}{\partial v}(g(x)+h(v))
   \end{array}\right]=
   \left[\begin{array}{cc}
            0 & 1\\
            g'(x) & h'(v)
   \end{array}\right]
\end{equation}
has the sign pattern
$\setlength{\arraycolsep}{1.75pt}
[\!\begin{array}{cc}
        \scriptstyle0 & \scriptstyle+\\[-1.7ex]
        \scriptstyle- & \scriptstyle-
\end{array}\!]$
at $(0,0)$.  The bottom two entries are `$-$' because $g$ and $h$
are monotone decreasing functions.  The signs of the $a_{ij}$ are also
derivable in all the QS formalisms described in Bobrow \cite{bobrow}.

Jeffries et al.~\cite{jeffries77} derive necessary and sufficient
conditions for sign stability.  Define $R=\{i|a_{ii}\not=0\}$.  Let $G$
be an undirected graph with vertices $V=\{1,\dots,n\}$ and edges 
\begin{equation}
E=\{(i,j)|i\not=j\wedge a_{ij}\not=0\}.
\end{equation}
An {\em R-coloring\/} of $G$ partitions $V$ into black and white sets
such that each vertex in $R$ is black, no black vertex has exactly one
white neighbor, and each white vertex has some white neighbor.  A 
{\em complete matching\/} in $G$ for $Z\subset V$ is a set of edges
satisfying: (1) no two edges touch the same vertex and (2) an edge
touches each vertex in $Z$.  $A$ is sign stable iff:
\begin{enumerate}
\item $a_{ii}\leq0$ for all $i$ and $a_{jj}<0$ for some $j$,
\item $a_{ij}a_{ji}\leq0$ for all $i\not=j$,
\item $a_{k_1k_2}a_{k_2k_3}\cdots a_{k_{m-1}k_m}a_{k_mk_1}=0$
       for any $m\geq3$ distinct indices $k_1,\ldots,k_m$,
\item the only $R$-coloring of $G$ is all black, and
\item a $V-R$ complete matching exists for $G$.
\end{enumerate}
Conditions~1 and~2 rule out positive feedback from a variable to itself
and between pairs of variables.  Klee and van den Driessche
\cite{klee77} present an algorithm that tests conditions~1--5 for an
$n$-by-$n$ matrix $A$ with $e$ nonzero elements in $O(\max\{n,e\})$
time. 

The sign pattern of the block example is
$\setlength{\arraycolsep}{1.75pt}
[\!\begin{array}{cc}
        \scriptstyle0 & \scriptstyle+\\[-1.7ex]
        \scriptstyle- & \scriptstyle-
\end{array}\!]$
at the unique fixed point: $(0,0)$.  This pattern is sign stable, implying
that the oscillations predicted by simulation die down for small initial
displacements.  Conditions~1--3 are immediate.  The graph $G$ has
vertices $V=\{1,2\}$ and edges $E=\{(1,2)\}$.  $R$ is $\{2\}$.  Every
$R$-covering of $G$ paints 2 black by definition; hence 1 must be
black to prevent 2 from having a single white neighbor, implying
condition~4.  The edge $(1,2)$ satisfies condition~5.  

A {\em redundant system\/} contains a set of variables that can be
expressed in terms of its constants and remaining variables.
Redundancy prevents a stable system from being sign stable.  For
example, the following system describes the (inertia-free) flow of liquid
through the U-shaped tube shown in Figure~\ref{f-utube}:
\begin{equation}
\left\{\begin{array}{rcl}
          \mbox{\it level-x} & = & u(\mbox{\it volume-x})\\
          \mbox{\it pressure-x} & = & p(\mbox{\it level-x})\\
          \mbox{\it level-y} & = & v(\mbox{\it volume-y})\\
          \mbox{\it pressure-y} & = & p(\mbox{\it level-y})\\
          \mbox{\it flow-rate} & = & r(\mbox{\it pressure-x}-\mbox{\it pressure-y})\\
          \mbox{\it volume-x}' & = & -\mbox{\it flow-rate}\\
          \mbox{\it volume-y}' & = & \mbox{\it flow-rate}
\end{array}\right.
\end{equation}
with $p$, $r$, $u$, and $v$ monotone increasing functions that vanish
at zero.  The system is redundant because either of the variables 
{\it volume-x\/} and {\it volume-y\/} can be expressed as the
difference between the constant {\it total-volume\/} and the other
variable.

\begin{figure}[htbp]
\begin{picture}(25,10)(-20,0)
\put(0,0){\line(0,1){10}}
\put(0,0){\line(1,0){22.5}}
\put(2.5,1.25){\line(0,1){8.75}}
\put(2.5,1.25){\line(1,0){15}}
\put(17.5,1.25){\line(0,1){8.75}}
\put(22.5,0){\line(0,1){10}}
\put(0,7.5){\line(1,0){2.5}}
\put(17.5,7.5){\line(1,0){5}}
\put(1.25,3.75){\makebox(0,0){$x$}}
\put(20,3.75){\makebox(0,0){$y$}}
\end{picture}
\caption{Fluid flow through a U-shaped tube.}\label{f-utube}
\end{figure}

Redundancy is primarily a modeling issue: flabby models produce weak
conclusions.  Nevertheless, FPA can ameliorate the problem by
eliminating linear dependencies.  It derives dependent sets of
derivatives, $\sum_i \alpha_i v'_i=0$, and integrates them into
dependent sets of variables $\sum_i \alpha_i v_i=k$.  Next, it derives
a maximal independent set of variables and eliminates he remaining
variables by substitution.  In the U-tube example, it obtains 
$\mbox{\it volume-x}'+\mbox{\it volume-y}'=0$ from the last two
constraints, integrates the result into 
$\mbox{\it volume-x}+\mbox{\it volume-y}=k$, and substitutes
$k-\mbox{\it volume-y}$ for {\it volume-x}.  Abbreviating 
{\it volume-y\/} to $y$, the reduced equation
\begin{equation}\label{e-utube}
y'=r(F(y))\;\mbox{with}\; F(y)=p(u(k-y))-p(v(y))
\end{equation}
has $A=(a_{11})$ with
\begin{equation}
a_{11}=\frac{\partial}{\partial y} r(F(y))=
        -r'(F(y))[p'(u(k-y))u'(k-y)+p'(v(y))v'(y)].
\end{equation}
The derivative terms in $a_{11}$ are positive because the
corresponding functions increase monotonically.  Hence, $a_{11}$ is
negative and $A$ satisfies the sign stability conditions.  Small height
differentials between the arms of the U-tube always disappear over
time.

If neither $A$ nor $-A$ is sign stable at the fixed point $p$, FPA tests
whether constraints on the magnitudes of the $a_{ij}$ imply stability.
For example, given $a>b>0$ it determines that 
\begin{equation}
M=
\left[\begin{array}{cc}
        -a & b\\
         b & -a
\end{array}\right]
\end{equation}
is stable even though $M$ violates condition~2 for sign stability and
$-M$ violates condition~1.  FPA also determines that the fixed point is
nodal from equation~(\ref{e-delta}), since $\Delta=4b^2>0$.

Stability of an $n$-by-$n$ matrix is decidable in $O(n^3)$ time with
the Routh-Hurwitz algorithm \cite[Ch.\ 3]{barnett83} when the $a_{ij}$
are numbers.  That algorithm depends solely on inequalities involving
terms in the determinant expansion of $A$.  Hence, it can also handle
symbolic $a_{ij}$, providing the signs of the determinant terms remain
derivable.  FPA tries to resolve the inequalities with the \bounder\
inequality reasoner.  If it succeeds, as in the case of $M$ above, the
Routh-Hurwitz algorithm determines the stability of $A$.  If \bounder\
cannot resolve some inequality, the algorithm fails.  Either the problem
is too hard for \bounder\ or the inequality is indeterminate, implying
that some, but not all, instances of $A$ are stable.  FPA maintains the
completeness of the transition graph by constructing transitions from
every adjacent region to $p$.

The Routh-Hurwitz algorithm must resolve $O(n^3)$ inequalities.  The
full \bounder\ program takes exponential time in each inequality,
making the overall algorithm exponential.  FPA can also use an $O(n)$
subset of \bounder\ that performs interval arithmetic, making the
overall algorithm $O(n^4)$, but sacrificing some predictive power.  The
restricted algorithm suffices for many matrices, including $M$ above.

\section{Global Interpretation}\label{s-global}

The task of global interpretation is to determine the long-term behavior
of a system, as opposed to transient behavior.  For example, the block
asymptotically nears its rest position and the height differential in the
U-tube asymptotically vanishes.  The phase space equivalent of
asymptotic behavior is an {\em attractor:} a connected subset of phase
space that nearby trajectories approach.  The fixed points of the
U-tube and the block are point attractors.  Other possibilities include
limit cycles, separatrices, and strange attractors.

The global interpretation capabilities of QS are quite limited.  It can
detect possible point attractors by identifying sink regions in transition
graphs, such as \reg{0,0} for the block (Figure~\ref{f-tgraph}).
However, it cannot tell whether all, some, or no neighboring
trajectories actually approach such sinks.  Similarly, QS can recognize
cycles in the transition graph as possible limit cycles, but cannot tell
whether nearby trajectories spiral inward, spiral outward, or wobble
around.

Dynamic systems theory provides tools for determining the attractors of
many extremely general equations.   The simplest case, called  
{\em monostability,} is where all trajectories approach a single fixed
point.  A sufficient condition for monostability, proved by Kalman
\cite{kalman57}, is that the matrix $A(x)$ be stable for every $x$.
FPA tests this condition with the Routh-Hurwitz algorithm.  If $A(x)$
has a fixed sign pattern, it first tries the sign stability algorithm, which
takes less time and avoids symbolic algebra and inequality reasoning. 
For example, the matrix
\begin{equation}
A(x,v)=\left[\begin{array}{cc}
                0 & 1\\
                g'(x) & h'(v)
         \end{array}\right]
\end{equation}
for the block equation~(\ref{e-block}) has the sign pattern
$\setlength{\arraycolsep}{1.75pt}
[\!\begin{array}{cc}
        \scriptstyle0 & \scriptstyle+\\[-1.7ex]
        \scriptstyle- & \scriptstyle-
\end{array}\!]$
for every $x$ and $v$.  The system is monostable because this pattern
is sign stable, as proved in the previous section.  This confirms the
intuition that the block's oscillations die out as friction dissipates its
initial energy.  The U-tube equation~(\ref{e-utube}) is also monostable,
implying that arbitrary height differentials between the arms of the
U-tube always disappear over time.

\section{Conclusions}

This paper recasts the terminology and algorithms of qualitative
reasoning into the phase space representation.  It simplifies 
transition analysis from many rules to two algebraic conditions.
The first condition determines transitions between arbitrarily shaped
regions in phase space, as opposed to QS which only handles
$n$-dimensional rectangles.  It also provides more accurate results
by considering only the boundaries between regions.  The second 
condition determines whether nearby trajectories approach a fixed point
asymptotically.  It obtains better results than QS by exploiting local
stability properties.  Both conditions apply to equations at all levels of
abstraction: sign constraints, symbolic constraints, numeric values, and
combinations thereof.  The more information exists, the better they
perform.

Qualitative reasoning includes more than transition analysis. 
Identifying attractors, which determine long-term behavior, is the next
key problem.  The monostability test of the previous section provides a
method for deriving global fixed point attractors.  Some additional
methods for identifying attractors appear in my thesis \cite{sacks88b},
but many remain to be developed.  Mathematicians, scientists, and
engineers explore many properties of dynamic systems beyond
transitions and attractors, including boundedness and periodicity of
trajectories, the existence of unstable limit cycles, and the location of
separatrices.  Incorporating their techniques into qualitative reasoning
is a topic for future research. 

\renewcommand{\baselinestretch}{1}\large\normalsize
\bibliography{z:>medg>bibcite>abbrevs,z:>medg>bibcite>bib,z:>medg>bibcite>crossref}
\bibliographystyle{plain}
\end{document}