Causes of Ineradicable Spurious Predictions in Qualitative Simulation

O. Yilmaz and A. C. Cem Say

Volume 27, 2006

Links to Full Text:

Abstract:
It was recently proved that a sound and complete qualitative simulator does not exist, that is, as long as the input-output vocabulary of the state-of-the-art QSIM algorithm is used, there will always be input models which cause any simulator with a coverage guarantee to make spurious predictions in its output. In this paper, we examine whether a meaningfully expressive restriction of this vocabulary is possible so that one can build a simulator with both the soundness and completeness properties. We prove several negative results: All sound qualitative simulators, employing subsets of the QSIM representation which retain the operating region transition feature, and support at least the addition and constancy constraints, are shown to be inherently incomplete. Even when the simulations are restricted to run in a single operating region, a constraint vocabulary containing just the addition, constancy, derivative, and multiplication relations makes the construction of sound and complete qualitative simulators impossible.

Extracted Text

%%[ ProductName: ESP Ghostscript ]%%


Journal of Artificial Intelligence Research 27 (2006) 551-575           
Submitted 03/06; published 12/06   (C)2006 AI Access Foundation. All rights
reserved. 

Causes of Ineradicable Spurious Predictions in Qualitative Simulation  O"zgu"r
Yilmaz       YILMOZGU@BOUN.EDU.TR A. C. Cem Say   

SAY@BOUN.EDU.TR Department of Computer Engineering  

Bog*azic,i University Bebek 34342 I.stanbul, Turkey 

    Abstract 

  It was recently pro ved that a sound and complete qualitative simulator
does not exist, that is, as long as the input -output vocabulary of the state
-of-the-art QSIM algorithm is used, there will  always be input models which
cause any simulator with a coverage guarantee to mak e spurious predictions
in its output.  In this paper, we examine whether a  meaningfully expressive
restriction  of this vocabulary is possible so that one can build a simulator
with both the sound ness and completeness  properties. We prove several negative
re sults:  All sound  qualitative  simulators,  employing subsets of the
QSIM representation which retain the operating region transition feature
, and support at least the addition and constancy constraints , are shown
to be inherently incomplete.  Even when the si mulations are restricted to
run in a single operating region, a constraint vocabulary containing just
the addition,  constancy, derivative, and  multiplication relations makes
the construction of sound and complete qualitative simulators impossible.

1. Introduction  It was recently proved  (Say & Akin, 2003)  that a sound
and complete qualitative simulator does not exist, that is, as long as the
input -output vocabulary of the state -of-the-art QSIM algorithm 

(Kuipers, 1994)  is used, there will always be input mo dels which cause
any simulator with a coverage guarantee to make spurious predictions in its
output. In this paper, we examine whether  a meaningfully expressive restriction
of this vocabulary is possible so that one can build a simulator which will
always  output all and only the consistent solutions of its input model.
We  prove several negative results: All sound qualitative simulators, employing
subsets of the QSIM representation which retain the operating region transition
feature, and support at least th e  addition and constancy constraints, are
shown to be inherently incomplete. The problem persists when all variables
are forced to change continuously during region transitions if a slightly
larger  set of  constraint  types is allowed . Even when the simulati ons
are restricted to run in a single operating region, a constraint vocabulary
containing just the addition, constancy, derivative, and  multiplication
relations makes the construction of sound and complete qualitative simulators
impossible.  Our findings m ay be helpful for researchers interested in constructing
qual itative  simulators with improved theoretical coverage guarantees using
weaker representations. 

2. Background  We start with a brief overview of qualitative simulation,
concentrating on the representations used in the input -output vocabularies
of qualitative simulators. Subsection 2.2 summarizes previous 

work on the two theoretical properties of qualitative simulators that interest
us. Subsection 2.3 is a short "requirements specification" for a hypothetical
sound and complete qualitative simulator.  %%[Page: 1]%%


  YILMAZ & SAY 

552  2.1 Qualitative Simulation  In many domains, scientists and engineers
have only an incomplete amount of information about the model governing the
dynamic system under consideration, which renders formula ting an 

exact ordinary differential equation (ODE) impossible. Incompletely specified
differential equations may also appear in contexts where the aim is to find
collective proofs for behavioral  properties of an infinite set of systems
sharing most, but no t a ll, of the structure of the ODE s describing them.
To proceed with the reasoning task in such cases, mathematical tools embodying
methods making the most use of the available inform ation to obtain a (hopefully
small) set of possible solutions matching th e model are needed.  Qualitative
reasoning  (QR) researchers  develop AI programs which use "weak" representations
(like intervals rather than point values for quantities, and general shape
descriptions rather than exact formulae for functional relationships)   in
their vocabularies to perform various reasoning tasks about systems with
incomplete specifications. In the fo llowing, we use the notation and terminology
of QSIM  (Kuipers, 1994),  which is a state-of-the art qualitative simulation
methodology, although it should be noted that the incompleteness results
that we will be proving are valid for all reasoners whose input -output 
vocabularies are rich enough to support the representational techniques that
will be used in our proofs.    A qualitative simulator take s as input a
qualitative differential equation  model of a system in terms of constraints
representing relations between the system's variables. In addition to this
model, the qualitative values of the variables at the time point from which
the simulation s hould start are also given. The algorithm produces a list
of the possible future behaviors that may be  exhibited by systems whose
ordinary differential equations match the input model.   The variables of
a system modeled in QSIM are continuously differentia ble functions of time.
The limits of each variable and their first derivatives exist as they approach
the endpoints of their domains. Each variable has a  quantity space; a totally
ordered collection of symbols ( landmarks)  representing important values
that  it can take. Zero is a standard landmark common to all  variables.
Quantity spaces are allowed to have the landmarks -e^ and e^ at their ends,
so functional relationships with asymptotic shapes can be explicitly represented.
When appropriate, a quantity 

space can be declared to span only a proper subset of the extended reals;
for instance, it makes sense to bound the quantity space for a variable which
is certainly nonnegative (like pressure)  with 0 at the left. If necessary,
the user can specify one or both  bounds of a quantity space to be  unreachable;
for example, e^ will be an unreachable value for all variables in all the
models to be discussed in this paper. The (reachable) points and intervals
in its quantity space make up the set 

of possible qualitative magnitudes of a variable. The  qualitative direction
of a variable is defined  to be the sign of its derivative; therefore its
possible values are:  inc (+),  dec (-) and  std (0). A variable's  qualitative
value  is the pair consisting of its qualitative magnitu de and qualitative

direction. The collection of the qualitative values of its variables makes
up the state of a system.   The "laws" according to which the system operates
are represented by  constraints describing  time-independent relations between
the variables. At each step of the simulation, QSIM uses a set of transition
rules to implicitly generate all possible "next" values of the variables.
The  combinations of these values are filtered so that only those which constitute
complete states, in which every constraint is still satisfied by the new
values of its variables, remain.    There are seven "basic" types of co nstraints
in QSIM. (See Table  1.) Each type of constraint imposes a different kind
of relation on its arguments. For example, if we have the cons traint  A(t)
= -B(t), any combination of variable values in which variables  A and  B
have the same (nonzero) sign in their magnitudes or directions will be filtered
out. Sometimes, additional  knowledge about the constraints allows further
filtering. In the above example,  if we know that A and B had the landmark
values  a

1 and  b1 at the same moment at some time in the past, we can %%[Page: 2]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

553  eliminate all value combinations in which  A and  B have magnitudes
both less (or both greater) than these landmarks.  a

1 and  b1 are called  corresponding values  of that constraint, and the equation
a 1 = -b1  is a correspondence. Each constraint in a model (except those
of the derivative type) can have such correspondence equations. A "sign algebra"
(Kuipers, 1994) is employed to 

implement the arithmetic relations using qualitative magnitudes. Note that,
s ince each  +M  ( -M )  relationship corresponds to an infinite number of
possible "quantitative" functions having the monotonicity property, a single
QSIM model containing such constraints can corres pond to 

infinitely many ODEs.  

CONSTRAINT NAME  NOTATION  EXPLANATION 

add  X(t) + Y(t) = Z(t)    

constant  X(t) = a landmark   dtd X(t) = 0 

derivative  d/dt(X,Y)  dtd X(t) = Y(t) 

+M   X(t) = f(Y(t)),  f I^ +M   $f such that X(t) = f(Y(t)), where  0>c'f
over f 's domain  -M   X(t) = f(Y(t)),  f I^ -M   $f such that X(t) = f(Y(t)),
where  0   which would
trigger transitions to  other operating regions when they are obtained, and
lists that detail w hich variables inherit their previous magnitudes and/or
directions after such a transition, and which of them are initialized to
new values during that switch. Tables  4-9 describe how to prepare these
items for the operating regions in our target model, ba sed on the program
P. There are  five different operating region  templates (or "types") used
in the construction; one for each URM instruction type, one for OpReg

0, and one for OpReg|P|+1.   The model of  OpReg

0 is depicted in Table 4. This is where our simul ation of P will start.
All the NR i variables are equated to their proper initial values specified
by the "user" of P: The ones initialized to zero are handled by "constant
at 0" constraints. The ones with positive initial values %%[Page: 8]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

559  are specified to be constan t at those values using  add constraints
to link them to the "number" variables exemplified in Table 3; for instance,
if  NR

2 is to be initialized to three, we have the constraint THREE(t)+ Z(t)= NR
2(t). The add constraint between B, U, and ONE serves to express the fact
that the landmark named  one in  U's quantity space is also equal to 1. (Note
that all the 

add constraints mentioned in this paragraph exist only in  OpReg0, since
they would disrupt the intended behavior in the other operating regions.)
As seen in Tables 4-8, exactly which variables keep their values during a
transition depends on the type of the target operating region. Regions corresponding
to instructions of the type  zero(n)  should not inherit the value of R n
from their predecessors, since th ey involve the replacement of that value
by zero anyway. All other types of regions, including the  succ(n) type,
inherit all the  register contents from their predecessors. (Although the
value of R n  does change in a  succ instruction, the new value depends o
n the old one, unlike the case of  zero(n). The corresponding  QSIM variable
NRn increases continuously during the simulation of a region of type  succ(n),
and a new region transition occurs exactly at the moment when it has increased
by one unit.)   

Operating Region: OpReg0  {Type: Initialization}  Constraint Set:   d/dt(U,
W)    B(t)+ U(t)= ONE(t) with correspondence "0 + one = one"    All the required
"number representation" constraints (see Table 3)    add constraints linking
the NRi to the relevant "number" variables (see text)    All variables except
U and B are constant.  Possible Transition:    Trigger: ( U = 
)     New operating region: OpReg1    Variables inheriting magnitudes or
directions: See Table 5, indexed by the type of OpReg1     Variables with
new asserted values: U n^ <0, inc> 

Table 4:  Model of the Operating Region OpReg0, Corresponding to the Initialization
of the URM    

TYPE OF TARGET REGION  VARIABLES INHERITING QUALITATIVE MAGNITUDES  VARIABLES
INHERITING QUALITATIVE DIRECTIONS 

jump(m, n, q)  All variables except U and B  All variables except U, B, and
all the NRi 

succ(n)  All variables except U and B  All variables except U, B, and all
the NRi 

zero(n)  All variables except U and NRn  All variables except U, B, and all
the NRi 

End  All variables except U  All variables except U and all the NRi 

Table 5:  Variables which should Inherit Magnitudes and/or Directions According
to the Type of the Target Operating Region %%[Page: 9]%%


  YILMAZ & SAY 

560    The simulation of the given URM program proceeds as follows: As described
in the previous subsection, the URM starts with an initial configuration,
where the registers R

1, ..., Rk store the nonnegative integers a 1, ..., ak, which form the input
of the program, respectively. The other N -k registers are set to 0. Correspondingly,
each of the  NR

i variabl es in our QSIM model has the quantity space [0,  e^). The  NR i
variables with nonzero initial values start simulation with qualitative values
<(0, e^), std>, whereas the other ones start with <0,  std>. The quantity
space of 

the variable  U is [0,  one], where th e landmark  one is equated to 1, as
mentioned above.  U starts  initially at qualitative value <0 , inc>. The
derivative of  U, W, has as quantity space [0,  speed, e^), where speed is
also equated to 1. It starts at qualitative value < speed, std> and is constant
in the 

whole simulation. The variable  B has the quantity space ( -e^, 0,  e^) and
starts at <(0,  e^),  dec>. When started in  OpReg

0, QSIM will compute a single qualitative behavior segment, which ends with
a transition to OpReg

1 when U reaches  at time-point t1.  

Operating Region: OpRegi  {Type: zero(n)}  Constraint Set:   d/dt(U, W) 
NRn(t)=0     All variables except U are constant.  Possible Transition: 
Trigger: ( U =  )     New operating region: OpRegi+1     Variables
inheriting magnitudes or directions: See Table 5, indexed by the type of
OpRegi+1     Variables with new asserted values: U n^ <0, inc> 

Table 6:  Model Template for Operating Regions Corresponding to zero(n) Instructions

Operating Region: OpRegi  {Type: succ(n)}  Constraint Set:   d/dt(U, W) 
B(t)+ U(t)=  NRn(t)    All variables except U and NRn are constant.  Possible
Transition:    Trigger: ( U =  )     New operating region: OpRegi+1

Variables inheriting magnitudes or directions: See Table 5, indexed by the
type of OpRegi+1     Variables with new asserted values: U n^ <0, inc> 

Table 7:  Model Template for Operating Regions Corresponding to succ(n) Instructions
%%[Page: 10]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

561    Note that there is zero uncertainty about the values of all variables,
even the ones with initial  magnitude (0, e^), at the start of the simulation.
Our model is so constrained that a sound and complete qualitative simulator
is guaranteed to 

produce exactly one behavior prediction for any initial state corresponding
to a valid URM input. To see this, it is sufficient to observe that, at 
any step of the simulation, there is sufficient  information available to
the simulator to compute the exact numerical value of every variable in the
model. (This just corresponds to "tracing" the URM program and keeping note
of the register  contents up to  that step.) If the modeled URM halts on
the particular input given in the initial state, the QSIM behavior  is supposed
to be a finite one, ending when the variable  U attempts to  exceed  one
in  OpReg|P|+1. If the URM computation does not halt, then the QSIM  behavior
is supposed to be a single infinite sequence of states, which never visits
OpReg

|P|+1. Lambda   

Operating Region: OpRegi  {Type: jump(m, n, q)}  Constraint Set:  d/dt(U,
W)     NRm(t)+ B(t)=  NRn(t)     All variables except U are constant.  Possible
Transition:    Trigger: ( U =  ) AND ( B z' <0, std> )    New operating
region: OpRegi+1    Variables inheriting magnitudes or directions: See Table
5, indexed by the type of OpRegi+1    Variables with new asserted values:
U n^ <0, inc>  Possible Transition:    Trigger: ( U =  ) AND (
B = <0, std> )    New operating region: OpRegq    Variables inheriting magnitudes
or directions: See Table 5, indexed by the type of OpRegq    Variables with
new asserted values:  U n^ <0, inc> 

Table 8:  Model Template for Operating Regions Corresponding to jump(m, n,
q) Instructions   

Operating Region: OpReg|P|+1  {Type: End}  Constraint Set:  d/dt(U, W)  
All variables except U are constant. 

Table 9:  Model of the Operating Region OpReg|P|+1, Corresponding to the
End of the URM Program      We are now ready to state a new version of the
incompleteness theorem. %%[Page: 11]%%


  YILMAZ & SAY 

562  Theorem 2:  Even if the qualitative representation is narrowed so that
only the  derivative,  add, mult, and constant constraints can be used in
QDE's, and each variable is forced to start at a finite  value with zero
uncertainty in the initial state, it is still impossible to build a sound
and complete qualitative simulator based on this input-output vocabulary.

Proof: Assume that such a sound and  complete simulator exists. We  now show
how to s olve the halting problem for URMs using that algorithm as a subroutine.
Construct the corresponding QSIM model as described in Theorem 1 for the
URM program P whose halting status on a particular input is supposed to be
decided. Now define a new variable  S  with quantity space [0, one, e^),
where the landmark one is equated to the number 1. S starts at the value
 in the initial state. Add constraint s indicating that   S  is
constant  to all the  operating regions, and specify that the value of  S
is inherited in all possible transitions. Insert the new constraint  S(t)
= 0 in  OpReg

|P|+1. Consider what the simulator is supposed to do when checking the initial
state for consistency. Note that we would have an inconsistency if the 

simulation ever enters OpReg|P|+1, since the new constraint that we inserted
to that region says that S is zero, which would contradict with the inherited
value of  one. So a simulator which is  supposed not to make any spurious
predictions is expected to reject the initial state at tim e t0 as inconsistent
if the simulation is going to enter  OpReg

|P|+1, in other words, if the URM program under consideration is going to
halt. If this sound and complete simulator does not reject the 

initial state due to inconsistency, but goes on with the  simulation, then
we can conclude that the program P will not halt. This forms a decision procedure
for the halting problem. Since the  halting problem is undecidable,  we have
obtained a contradiction, and conclude that  a sound and complete simulator
using this representation can not exist. Lambda  

  It is in fact possible to remove the derivative constraint (which is only
used in our proof to ensure that the behavior tree has at most one branch)
from the representation as well, and the  incompleteness result shown above
would still stand:  Theorem  3:  Even if the qualitative representation is
narrowed so that only the  add, mult,  and constant constraints can be used
in QDE's, and each variable is forced to start at a finite value 

with zero uncertainty in the initial state, it is still impossible to buil
d a sound and complete qualitative simulator based on this input-output vocabulary.

Proof:  We will make a minor modification to the proof of Theorem 2. We observe
that in the construction of Theorem 1, U always starts every operating region
at <0, inc> and the fact that its  derivative is a positive constant forces
it to reach the value   in the next time point. Then the transition
to next operating region occurs, and U again receives the value <0, inc>.
What  happens if we remove the variable  W and  all derivative constraints
from the model? In this case, since  U's derivative is not fixed, there are
three possible states for  U in the  second time point   during the simulation
of any operating region: , , and <(0, one), std>. We
fix this problem by inserting another possible region transition specification
to all of our regions,  except OpReg|P|+1. This transition will be triggered
when  U has one of the values  , and <(0, one), std>, and its target
will be  OpReg

|P|+1. The variab le S from the proof of Theorem 2, as well as all other
variables, are inherited completely during this transition. So all the "unwanted"

behaviors which would be created due to the elimination of  U's derivative
end up in  OpReg|P|+1, and should therefore be  eliminated as spurious in
accordance with the argument of the previous  proof. Hence, once again, the
simulator is supposed to accept the initial state as consistent if and only
if P does not halt, meaning that a sound and complete simulation is impossible
wi th this  representation as well. Lambda  %%[Page: 12]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

563    Interestingly, one can even restrict the representation so that only
nonnegative numbers are supported, and the incompleteness result we proved
above still stands:  Theorem 4:  Even if the qualitative representation is
narrowed so that only the  add, mult,   and constant constraints can be used
in QDE's, each variable is forced to start at a finite value with  zero uncertainty
in the initial state, and no variable is allowed to have a negative value
at any time during the simulation, it is still impossible to  build a sound
and complete qualitative simulator  based on this input-output vocabulary.
Proof: In our previous proof, only variable  B ever has the possibility of
having a negative value, and that can occur only in a  jump region. We replace
the definition o f the  jump region template 

with Table 10, and introduce the new variables  C and Y. We insert constraints
that say that these variables are constant to all operating regions.  C and
Y start at zero, and are inherited by all  transitions, except when the targe
t region is of type  jump. As can be seen in Table 10,  B gets the value
1 if and only if the two compared register values are equal. If they are
unequal,  B has a  positive value different than 1. In this setup,  B's quantity
space is defined as [0,  one, e^), where one is equated to 1, and no variable
ever has a negative value during the simulation.  B now starts  simulation
with the value  to satisfy the  add constraint seen in Table 4.
The rest of the argument is identical to that of Theorem 3. Lambda    

Operating Region: OpRegi  {Type: jump(m, n, q)}  Constraint Set:  NRm(t)
+ ONE(t) = C(t)    NRn(t) + ONE(t) = Y(t)    B(t) * C(t) = Y(t)    All variables
except U are constant.  Possible Transition:    Trigger: ( U = 
) AND ( B z'  )    New operating region: OpRegi+1    Variables
inheriting magnitudes or directions: Depends on the type of OpRegi+1, as
before    Variables with new asserted values:  U n^ <0, inc>  Possible Transition:
Trigger: ( U =  ) AND ( B =  )    New operating region:
OpRegq    Variables inheriting magnitudes or directions: Depends on the type
of OpRegq, as before    Variables with new asserted values:  U n^ <0, inc>

Table 10:  Alternative Model Template for Operating Regions Corresponding
to jump(m, n, q) Instructions which Avoids Negative Numbers      Alternatively,
we can keep negative numbers and remove the  mult constraint from the representation,
if we drop the requirement that each variable starts simulation at a value
with zero 

uncertainty. %%[Page: 13]%%


  YILMAZ & SAY 

564  Theorem 5: Even if the qualitative repre sentation is narrowed so that
only the  add and constant constraints can be used in QDE's, it is still
impossible to build a sound and complete qualitative  simulator based on
this input-output vocabulary.  Proof: We used the  mult constraint in the
proofs of  Theorems 1-3 only for equating  variable and landmark values to
unambiguous integers. Assume that we delete the  mult constraints from our

model of Theorem 3.  The "number" variables of Table 3  are replaced  with
the setup shown in Table 11. If R

i is supposed  to be initialized to the positive integer a i in P, we equate
NRi to the "a i*unit" variable in OpReg0 using the method explained in the
proof of Theorem 1. Note that we only use constant and add constraints (and
a lot of auxiliary variables) for this purpose. 

 

CONSTRAINTS  CONCLUSIONS  ONEUNIT(t) = unit    ONEUNIT(t) + ONEUNIT(t) =
TWOUNITS(t)  TWOUNITS is constant at 2*unit  ONEUNIT(t) + TWOUNITS(t) = THREEUNITS(t)
THREEUNITS is constant at 3*unit 

Table 11:  Sample Model Fragment for Equating Variables to Integer Multiples
of the Positive Landmark unit      The landmarks previously named  one in
other variables' quantity spaces are now equated to unit. In this new model,
execution of a  succ(n) instruction increments  NR

n's value by one  unit. The  jump instruction co mpares landmarks whose values
equal  u*unit and  v*unit instead of 

comparing two landmarks whose values equal the natural numbers  u and v.
The  zero instruction sets the target register to 0, as in the previous construction.
So the modeled machine does just  what the original URM does, since the multiplication
of all values by the coefficient unit does not change the flow of the program,
and, in particular, whether it halts on its input or not. The rest of  the
argument is identical to that of the proof of Theorem 3. Lambda     We observe
that some of the variables change their qual itative magnitudes and directions
discontinuously during o perating region transitions in the proofs of  the
previous theorems. The 

next theorem proves that maintaining soundness and completeness simu ltaneously
is impo ssible even if we do not allow any qualitative variable to perform
such a change, and force each  variable's magnitude and direction to be inherited
to the next operating region.  Theorem 6: Even if the qualitative representation
is narrowed so that only the derivative, add and constant constraints can
be used in QDE's, and no variable's magnitude and direction are allowed 

to perform discontinuous changes during operating region transitions, it
is still impossible to build a sound and complete qualitative simulator based
on this input-output vocabulary.  

Proof:  Once again, we make  some changes  to the QSIM models used for simulating
the given URM in the previous theorems. As  always, we  have a QSIM variable
NR

i for each of the N registers R i appearing in the URM program. In addition
to that, we define  the variables Dij for all i, j I^ {1, ...,N} such that
i Xi  j. Each  of these satisfies the equation  D

ij = NRi - NRj throughout the simulation; that is, we keep track of the differences
of all pairs of register values. This can clearly 

be achieved by inserting several  add constraints to all the  operating regions
in our  model. These difference variables will enable us to co mpare two
register values in operating r egions of type   jump.  %%[Page: 14]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

565    Furthermore, we define auxiliary variables  TRi for all i  I^ {1,
..., N}. All the TRi are initialized to the same values as the corresponding
NR

i, using the same technique as for the NRi.   For each instruction type in
the given URM program, we define  two operating regions. Our 

clock variable U will increase in the first of these operating regions to
the value < unit, std>, and decrease in the next  one from < unit, std> to
<0,  std>, performing no discontinuous jump in the  program. In order to
obtain a variable with such behavior, we make use of the simple ha rmonic
oscillator model given in Table 12, where the var iable  X  (denoting the
displacement fro m the  "rest" position of the oscillating "object") oscillates
b etween the values  unit/2 and  -unit/2,  and the variable U is equated
to  X + unit/2, oscillating between 0 and  unit. The model template given
in Table 12 is added to every opera ting region. (That table contains some
variable names used in the constructions of the previous proofs. All such
variables are treated in the previously described  manner, unless this proof
specifies otherwise.) The following lemma establishes the correctness of
this construction.   

CONSTRAINTS  CORRESPONDENCES  MEANING  HALFUNIT(t) + HALFUNIT(t) = ONEUNIT(t)
c1 + c1 =  unit  c1 = unit / 2 

HALFUNIT(t) + V(t) = E(t)  c1 + v1  = 0   v1 = -unit / 2 

d/dt(X, V)    VdtdX =  

d/dt(V, A)    AdtXd =

2  

X(t) + A(t) = Z(t)    0

2 =+ X

dt

Xd  

X(t) + HALFUNIT(t) = U(t)    U = X+unit/2 

Table 12:  Model Template to Obtain the Desired Behavior for the Variable
U as a Clock Oscillating between Qualitative Values <0, std> and 
(This Template is to be Inserted 

to All Constructed Operating Regions.)  

Lemma 7: For any number r which can be represented by a QSIM landmark , a
QSIM variable  X  can be equated to the function r sin(t - t0) using only
derivative, add and constant constraints. 

Proof of Lemma 7:  As seen in Table 12, the equation 

  ( ) ( ) 0

2 =+ tXtX

dt d    

can be expressed using only  derivative, add and constant constraints. This
equation has a general solution of the form    ( ) tctctX cossin 21 += ,
(1)  %%[Page: 15]%%


  YILMAZ & SAY 

566  and hence its time derivative V has the form 

( ) tctctV sincos 21 -= .                                               Assume
that X and V are initialized as follows: 

( ) 00 =tX  

( ) rtV =0 .  By substituting these values in the equations above, one obtains
the equation system 

0201 cossin0 tctc +=   0201 sincos tctcr -= ,  whose solution  (Yilmaz, 2005)
yields c1 =  r cos t0 and c2 =  -r sin  t0. Substituting  c1 and  c2 into
Equation ( 1), we get  ( ) ( ) ( )000 sincossinsincos ttrttttrtX -=-*= ,
thereby proving the 

lemma. Lambda  

Proof of Theorem 6 (continued):  Therefore, if we equate the landmark v

1 of V to -unit/2 as shown in Table 12, and initialize X and V to 0 and v
1, respectively, we will ensure that 

( ) ( )0sin2 ttunittX --= , 

i.e., that the variable X oscillates between the values unit/2 and -unit/2,
as desired.    To be consistent with Lemma  7, the oscillating variables
of  Table 12 start simulation with the  qualitative values listed in Table
13. All other variables,  except  B, which starts with the value  <(0, e^),
inc>, are initialized as previously described.  

VARIABLE  QUANTITY SPACE  INITIAL VALUE 

U  [0, unit]  <(0, unit), dec> 

E  (-e^, 0, e^)  <0, std>  X  (-e^, 0, e^)  <0, dec>  V  (-e^, v1, 0, e^)
  A  (-e^, 0, e^)  <0, inc> 

Table 13:  The Quantity Spaces and Initial Values of the Oscillating Variables
We are going to denote the two o perating regions corresponding to the  ith
i nstruction of the URM program with  OpReg

i,1 and  OpRegi,2. All variables' qualitative values are inherited in all
possible trans itions, such that no variable ever undergoes a discontinuous
change. Looking 

carefully at Tables 14 -21, which correspond to the i nitialization, instruction
types, and ending of the URM, we see that the simulation flows in a unique
branch with the exception of  zero type %%[Page: 16]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

567  operating regions, where there is the possibility that the sim ulation
branches into more than one behavior, and the  b ehaviors which do not correspond
to the expected traje ctory of the actual  URM are directed to  OpReg|P|+1,1.
(Note that transitions to infinite landmarks do not need to be considered,
since we assume that all infinite landmarks are specified as unreachable
values for all  variables in our models.) The registers stay constant when
OpReg|P|+1,1, which is a single operating region correspon ding to the end
of the URM program, is reached. The rest of the proof is the  same as in
Theorem 2. Our co ntradiction varia ble  S  ensures that only the beha vior
of a non -halting URM leads to a consistent initial state, hence dete rmining
the consistency of the initial  state is equivalent to deciding the halting
problem, leading to a contradiction. Lambda   

Operating Region: OpReg0  {Type: Initialization}  Constraint Set:  All the
required "input value representation" constraints (see Table 11)    B(t)+
U(t)= ONEUNIT(t) with correspondence "0 + unit = unit"    add constraints
linking the NRi and the TRi to the relevant "n*unit" variables     add constraints
defining the Dij variables    the "clock" constraints (Table 12)     All
variables except B, U, X, V, E, and A are constant.  Possible Transition:
Trigger: ( U = <0, std> )      New operating region: OpReg1,1    Variables
inheriting qualitative values: All variables 

Table 14:  Template for the Single Operating Region Corresponding to the
Initialization Stage   3.2 Simulation within a Single Operating Region  The
incompleteness proofs in subsection 3.1 (as well as that of Say & Akin, 2003)
depend on the capability of "turning the constraints on or off" when necessary,
which is provided by the 

operating region transition feature. Would the problem persist if we forsook
that feature, and focused on the simulation of qualitative models with a
single operating r egion? We now show  that the answer to this question is
affirmative. 

3.2.1 HILBERT'S TENTH PROBLEM  As the name suggests, Hilbert's Tenth Problem
is the tenth of 23 problems which were announced in 1900 by the famous mathematician
David Hilbert as a challeng e to the 

mathematicians of the 20 th century. It asks for an algorithm for deciding
whether a given multivariate polynomial with integer coefficients has integer
solutions. It has been proven that no  such algorithm exists (Matiyasevich,
1993). This fact was  used by Say and Akin (2003) in their original proof
of the existence of ineradicable spurious predictions in the outputs of all
qualitative  simulators employing the operating region transition feature
and a larger set of constraint types than those we deal with in this paper.
%%[Page: 17]%%


  YILMAZ & SAY 

568    In the proof to be presented shortly, we use the undecidability of
a slightly modified variant of the setup described by Hilbert: We assume
a guarantee that none of the variables in the given  polynomial are zero
in the solution whose  existence is in question. It is clear that this modified
problem is unsolvable as well, by the following argument: Assume that we
do have an algorithm  A which takes a multivariate polynomial with integer
coefficients as input, and announces whether a solution where all the variables
have nonzero integer values exists or not in finite time.  We can use A as
a subroutine in the construction of the algorithm sought in Hilbert's original
problem as follows: We systematically produce 2 n polynomials from the input
polynomial with n  variables, such that each of these new polynomials corresponds
to a different subset of the variables of the original polynomial replaced
with zero. We then run A on each of these new  polynomials. It is easy to
see that A will find that  one or more of these polynomials have nonzero
integer solutions if and only if the original polynomial has integer solutions.

Operating Region: OpRegi,1  {Type: zero(n)}  Constraint Set:  add constraints
defining the Dij variables    the "clock" constraints (Table 12)     All
variables except U, X, V, E, A, NRn, and Dij with n I^ {i,j} are constant.
Possible Transition:    Trigger: ( U =  ) AND ( NRn =  <0, std>
)      New operating region: OpRegi,2    Variables inheriting qualitative
values: All variables  Possible Transition:    Trigger: (( U = 
) AND ( NRn Xi   <0, std> )) OR ( NRn = <(0, e^), std> ) OR ( NRn = <(-e^,
0), std> )     New operating region: OpReg|P|+1, 1    Variables inheriting
qualitative values: All variables 

Table 15:  Template for the First Operating Region Corresponding to zero(n)
Instructions   3.2.2  SOUND AND COMPLETE QSIM WITHIN A SINGLE OPERATING REGION
SOLVES HILBERT'S T

ENTH PROBLEM 

Theorem 8 : Even if the qualitative representation is na rrowed so that only
the  derivative,  add, mult and constant constraints can be used in QDE's,
and the simulation pr oceeds only in a single 

operating region, it is still impossible to build a sound and complete qualitative
simulator based on this input-output vocabulary. 

  We are going to start our proof w ith some preliminary lemmata, the first
of which is reminiscent of Lemma 7 from the previous subsection:  Lemma 9
: For any real constant equated to the QSIM variable  Xi, a QSIM variable
Yi can be  equated to the function  ( )( )0sin ttX i -*  using only derivative,
add, mult, and constant constraints. 

Proof: The case for Xi = 0 is trivial, and can be handled with a single 
constant constraint. For the remaining case, we will consider the following
equation set: %%[Page: 18]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

569  Operating Region: OpRegi,2  {Type: zero(n)}  Constraint Set:  add constraints
defining the Dij variables    the "clock" constraints (Table 12)     All
variables except U, X, V, E, A, and TRn are constant.  Possible Transition:
Trigger: ( U = <0, std> ) AND ( TRn = <0, std> )      New operating region:
OpRegi+1,1    Variables inheriting qualitative values: All variables  Possible
Transition:    Trigger: (( U = <0, std> ) AND ( TRn Xi  <0, std> ) ) OR
( TRn = <(0, e^), std> ) OR ( TRn = <(-e^, 0), std> )      New operating
region: OpReg|P|+1, 1    Variables inheriting qualitative values: All variables

Table 16:  Template for the Second Operating Region Corresponding to zero(n)
Instructions 

  Operating Region: OpRegi,1  {Type: succ(n)}  Constraint Set:  TRn(t)+ U(t)=
NRn(t)    add constraints defining the Dij variables    the "clock" constraints
(Table 12)     All variables except U, X, V, E, A, NRn, and Dij with n I^
{i,j} are constant.  Possible Transition:    Trigger: ( U =  )
New operating region: OpRegi,2    Variables inheriting qualitative values:
All variables 

Table 17:  Template for the First Operating Region Corresponding to succ(n)
Instructions     ( ) ( ) 0

2 =*+ tYWtY

dt d

iii   (2)  

  2ii XW = , so that  Delta Theta Lambda  <- >= .0   , 0      ,

ii

iii XX

XXW  

(3) 

with the initial values    ( ) 00 =tYi  %%[Page: 19]%%


  YILMAZ & SAY 

570  Operating Region: OpRegi,2  {Type: succ(n)}  Constraint Set:  TRn(t)+
U(t)= NRn(t)    add constraints defining the Dij variables    the "clock"
constraints (Table 12)     All variables except U, X, V, E, A, and TRn are
constant.  Possible Transition:    Trigger: ( U = <0, std> )      New operating
region: OpRegi+1,1    Variables inheriting qualitative values: All variables

Table 18:  Template for the Second Operating Region Corresponding to succ(n)
Instructions   

Operating Region: OpRegi,1  {Type: jump(m, n, q)}  Constraint Set:  add constraints
defining the Dij variables    the "clock" constraints (Table 12)     All
variables except U, X, V, E, and A are constant.  Possible Transition:  
Trigger: ( U =  )       New operating region: OpRegi,2    Variables
inheriting qualitative values: All variables 

Table 19:  Template for the First Operating Region Corresponding to jump(m,
n, q) Instructions     ( ) ii XtV =0 ,    where Vi(t) is the time derivative
of Yi(t).   The general solution of Equation (2) is:  

( ) ( ) ( )tWctWctY iii *+*= cossin 21 .  Substituting the  iW  from Equation
( 3) and the initial values in the equations for  Yi and Vi, and  solving
these equation systems results in the following (Yilmaz, 2005):  

For Xi > 0,  c1 = cos(Xi*t0) and c2 = -sin(Xi*t0).  For Xi < 0,   c1 = -cos(Xi*t0)
and c2 = -sin(Xi*t0).  When we substitute these in the formula for Yi(t),
we obtain: 

( ) ( ) ( ) ( ) ( ) ( )( )000 sincossinsincos ttXtXtXtXtXtY iiiiii -*=**-**=
,  Xi > 0, %%[Page: 20]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

571  Operating Region: OpRegi,2  {Type: jump(m, n, q)}  Constraint Set: 
add constraints defining the Dij variables    the "clock" constraints (Table
12)     All variables except U, X, V, E, and A are constant.  Possible Transition:
Trigger: ( Dmn = <0, std> ) AND ( U = <0, std> )      New operating region:
OpRegq,1    Variables inheriting qualitative values: All variables  Possible
Transition:    Trigger: ( Dmn Xi  <0, std> ) AND ( U = <0, std> )      New
operating region: OpRegi+1,1    Variables inheriting qualitative values:
All variables 

Table 20:  Template for the Second Operating Region Corresponding to jump(m,
n, q) Instructions   

Operating Region: OpReg|P|+1, 1   {Type: End}  Constraint Set:  S(t) = 0
All variables except U, X, V, E, and A are constant. 

Table 21:  Model of the Operating Region Corresponding to the End of the
URM Program   ( ) ( ) ( )( ) ( ) ( )( ) ( )( )000 sincossinsincos ttXtXtXtXtXtY
iiiiii -*=*-*-*-*-= ,  Xi < 0.  Hence, we have Yi(t) =  ( )( )0sin ttX i
-*  for all Xi Xi  0.    Table 22 shows that Equations ( 2) and (3) and
the initial va lues given above are representable using the derivative, add,
mult, and constant constraints. Note that  X

i has to be kept constant and initialized to either (0, Delta ) or (-Delta
, 0), depending on the intended sign for that number, and both  Y

i  and C i  must start at zero, to be consistent with the construction above.
Lambda  

Lemma 10: Starting at  t0, the function  Y = sin( t-t0) reaches the value
0 for the first time at time  point tE = t0 + p. Moreover the f unction Yi
= sin( Xi*(t-t0)) reaches 0 at the same time point  tE if and only if X

i is an integer. 

Proof: The equation sin(t-t0) = 0 implies t-t0 = np, n I^ Z, and since we
are i nterested in the first  time point  after  t0 where  it becomes 0 ,
we get  tE  = t 0  +  p. For the "only if" part of the second  statement,
assume that the fun ction  Yi = sin( Xi*(t-t0))  reaches 0 at  tE  = t 0
+  p.  Then ( )( ) ( )

0sinsin 00 =*=-+* pp ii XttX  implies that Xi is an i nteger. For the "if"
part, we use the 

knowledge that Xi is an integer to conclude that Yi(tE)= sin(Xi*(t0 + p -
t0))= sin(Xi*p)= 0. Delta  %%[Page: 21]%%


  YILMAZ & SAY 

572  CONSTRAINTS  MEANING 

Z = 0    Xi(t) + Ci(t) = Vi(t)  Vi(t0)  = Xi 

d/dt(Yi, Vi)  ( )tVdtdY ii =  

d/dt(Vi, Ai)  ( )tAdtYd ii =

2  

Xi(t) * Xi(t) = Wi(t)  2ii XW =  

Wi(t) * Yi(t) = Li(t)  ( ) ( )tYWtL iii *=  

Ai(t) + Li(t) = Z(t)  ( ) 0

2 =*+ tYW

dt

Yd

iii  

  Table 22:  Model Fragment Used to Obtain the Relationship  ( )( )0sin ttXY
ii -*=    

Proof of Theorem  8:  As already mentioned, the  proof rel ies on a co ntradiction,
namely that a sound and  complete simulator, if it existed,  could be used
to construct an algorithm for  solving 

Hilbert's Tenth Problem, as follows:   Assume that we are given a polynomial
P(x

1, x2, x3, ...,  xn) with int eger coefficients. We start by constructing
a QSIM model fragm ent that "says" that  P(x

1, x2, x3, ..., xn)= 0: We have already seen in Section 3.1  how to  equate
any desired integer to a QSIM variable. Represent all integers 

appearing as coefficients in the polynomial in that manner. Introduce a QSIM
variable Xi for each of the x

i, declare all these Xi to be constant, and use add and mult constraints
to equate the sum of products that is P(X

1, X2, X3, ..., Xn) to a QSIM variable P, which will be initialized to 0.
Note that this is tantamount to saying that the present values  of the  X

i form a solution for the polynomial. All this can clearly be done in a single
operating region, with  constraints of the types  mult, add 

and constant.   We then extend  this model with the necessary constraints
and auxiliary variables to equate a  new variable   Y  to the function  
sin(t-t0). (Either Lemma 7 or Lemma  9 can be used for this  purpose.) We
specify Y's quantity space as [0, e^), so that the simulation is guaranteed
to finish at  t = tE = t0 + p. For each  Xi, we define a ssociated auxiliary
variables   Ci, Li, Wi, Vi, Ai and Yi, and  add the template in Table  22
to our model  to express the relationship Yi = sin(Xi*(t-t0)). We also 

equate a variable  YS with the sum of the squares of  the Yi, i.e.  Xi 

==

n i

iYYS 1

2 . Note that if  YS = 0, 

then all the Yi are 0.    Finally, we need  make sure that the  only consistent
behaviors are the ones in which  the X

i are integers (that is, relying on Lemma  10, the behavior s in which the
variable  YS becomes 0 at  t

E). To serve this aim, we add the constraint F(t) * Y(t) = YS(t) to our model.

  We will simulate this model 2 n times, each run corresponding to a different
way of initializing  the  Xi  to  magnitudes selected from the set {(0, 
Delta ), ( -Delta , 0)} . A sound and co mplete simulator %%[Page: 22]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

573  would  accept all and only the initial sta tes  with  those  Xi whose
values  do not cause any inconsistency with our model. But those  X

i  correspond exactly  to  the integer sol utions of  the given polynomial,
by the following reasoning about the variable F: 

  Note that F is defined to be  YS/Y by the F(t) * Y(t) = YS(t) constraint.
We know that Y, Yi, and hence  YS  are  all  initially 0 , meaning that one
has to use l'Ho^pital's rule to find out the initial  value of F. This is
important, since if F's initial magnitude or derivative are infinite, QSIM
is not even supposed to consider successors for the initial state. (We declare
the infinite landmarks as  unreachable values for all variables, as mentioned
earlier. Even if  F's magnitude is finite and just its derivative is infinite,
simulation is not supposed to con tinue, because the  continuity  requirement
would be violated.) Fortunately,  

( ) ( )( )( )

0

1

02

sin

sin

tt

ttX tF

n i

i

-

-* = Xi =  

does have finite magnitude and derivative at t0: At t = t0, we use l'Ho^pital's
rule to find 

( ) ( )( ) ( )( )( ) 0cos

cossin2

0 0

00

00 1

00

0 =-

-*-* == Xi = tt

ttXttXX tF

i

n

i

ii . 

  As for F's qualitative direction; 

( ) ( )( ) ( )( )( ) ( )( ) ( )( )Xi 

= Pi Pi Sigma 

Upsilon Phi Phi  Psi  Omega 

-

--*- -

-*-*= n

i

iiii tt ttttXtt ttXttXXtdtdF 1 02

002 0

00 sin cossinsin cossin2 , 

and it turns out, after several applications of l'Ho^pital's rule, that 

( ) Xi 

==

n i

iXtdtdF 1

20 , 

which is clearly a finite positive number, and F's initial qualitative value
is therefore <0, inc>.   Obviously, F = YS/Y is guaranteed to be  finite
until  t

E, when Y reaches 0.  If the variable  YS is nonzero (implying that at least
one of the Y i is nonzero, and by Lemma 10 that the corresponding X i is
not an  integer) at tE, F(tE) has to  equal Delta , which is impossible
since infinity was declared to be unreachable, so  such states would be eliminated
as  spurious. If, on the other hand,  YS(t

E) = 0, then, we see by l'Ho^pital's rule, and the knowledge that all the
X i are integers, that 

( ) ( )( ) ( )( )( ) ( ) ( )( ) 0cos

cossin2

cos

cossin2 0 0 1

0

0 1

0 =**=

-

-*-* == Xi Xi  == p

pp i n

i

ii

E

Ei n

i

Eii

E

XXX

tt

ttXttXX tF , 

and behaviors ending with such states are su pposed to be included in  the
simulation output. So if our supposedly complete and sound simulator rejects
the initial  states of our model due to  inconsistency  in all the 2 n runs,
we  reason that all the behavior predictions considered by the simulator
ended with F(t

E)= Delta , and this inconsistency propagated back to the initial state
and led to its rejection in all cases. We conclude  that the poly nomial
has no integer solutions.   On the 

other hand, if  even one of the simulations   prints out the initial state
and g oes on with its successors, we conclude that  a solution exists. This
forms   the  decision procedure  required in  %%[Page: 23]%%


  YILMAZ & SAY 

574  Hilbert's Tenth Problem, leading to a contradiction. Therefore, sound
and complete simulation is impossible even if one restricts oneself to a
sin gle operating region and the limited constraint  vocabulary mentioned
in the statement of the theorem. Lambda  

4. Conclusion  In this  paper, we considered several alternative subsets
of the qualitative representation, and showed that the inerad icable spurious
pred iction problem persists even when only the  add and 

constant constraints are allowed. If one allows the  mult co nstraint as
well, then  any  resulting qualitative simulator is inherently incomplete
even when the representation of negative nu mbers  is forbidden  and every
variable is forced to be specified with zero uncertainty (i.e. as a single
unambiguous real number) in the initial state.  Our final proof shows that
even the ability of  handling models with multiple operating regions can
be removed from the representation, and the incompleteness problem  would
still  persist, provided the  add,  constant,  derivative, and  mult  constraints
are allowed in the vocabulary.   Note that  none of these vocabularies include
the monotonic function constraint, which  is the only rel ation type  "native"
to the qualitative   representation.   Although t he results in this  paper
are demonstrated using the QSIM representation for input  and output, they
are valid for all qualitative simulators whose input and output vocabularies
are as expressive as the specified subsets of  those of QSIM.  (Also note
that our proofs apply  automatically to semi -quantitative simulators, whose
representations are an extension of that of pure QSIM.)  We believe that
these results  are important in the sense that they  provide deeper  insight
to the causes of spurious predictions, and they  can be helpful  for researchers
aiming to construct provably sound and complete simulators using weaker representations.
Finally, we wish to stress that  our findings here do not amount  to as bad
a piece of news about the usefulness of qualitative simulators in the practical
domains that they are usually utilized as it  may seem to the uninitiated
eye. When one's model is specified at the level of precision that is involved
in the models i n this paper, one  does not employ a  qualitative reasoner
anyway.  What  really annoys the users of qualitative simulators is the occasional
prediction of  eradicable spurious behaviors, and the strengthening of the
algorithms with additional filters of increa sing  mathematical sophistication
to get rid of  more of  these continues to be an important line of research.
References 

Cutland, N. J. (1980). Computability: An Introduction to Recursive Function
Theory. Cambridge, UK: Cambridge University Press.  

de Kleer , J., & Brown, J. S. (1984). A qualitative physics based on confluences.
Artificial Intelligence, 24, 7-83.  Fouche',  P., &   Kuipers,  B. J.  (1992).
Reasoning  about  energy in  qualitative  simulation. IEEE Transactions on
Systems, Man, and Cybernetics, 22, 47-63.  Ko"nik,  T., &  Say,  A. C. C.
( 2003).  Duration  consistency  filtering for  qualitative  simulation.
Annals of Mathematics and Artificial Intelligence, 38, 269-309.  Kuipers,
B. J., (1986). Qualitative simulation. Artificial Intelligence, 29, 289-338.
%%[Page: 24]%%


  CAUSES OF INERADICABLE SPURIOUS PREDICTIONS IN QUALITATIVE SIMULATION 

575  Kuipers,  B. J. ( 1994).  Qualitative Reasoning: Mo deling and Simulation
with Incomplete Knowledge. Cambridge, MA: MIT Press.  Matiyasevich, Y. (1993).
Hilbert's Tenth Problem. Cambridge, MA: MIT Press.  Missier, A. (1991). Mathematical
structures for qualitative calculus, a contribution to qualitative simulation.
(In French) Ph.D. thesis, Institut National des Sciences Applique'es de Toulouse.

Say,  A. C. C. ( 1998).  L'Ho^pital's filter for QSIM . IEEE Transactions
on Pattern Analysis and Machine Intelligence, 20, 1-8.  Say, A. C. C. ( 2001).
Improved reasoning about infinity using qualitative simulation. Computing
and Informatics, 20, 487-507.  Say, A. C. C. ( 2003). Sound and complete
qualitative simulation requires "quantitative" filtering.  Annals of Mathematics
and Artificial Intelligence, 38, 257-267.  Say,  A. C. C., &  Akin,  H. L.
( 2003).  Sound and  complete  qualitative simulation is  impossible. Artificial
Intelligence, 149, 251-266.  Say, A. C. C., & Kuru, S. (1993). Improved filtering
for the QSIM algorithm. IEEE Transactions on Pattern Analysis and Machine
Intelligence, 15, 967-971.  Shepherdson, J. C., & Sturgis, H. E. (1963).
Computability of recursive functions. Journal of the ACM, 10, 217-255.  Shults,
B., &  Kuipers,  B. (1997).  Proving properties of continuous systems: Quali
tative simulation and temporal logic. Artificial Intelligence, 92, 91-129.
Struss, P. (1990). Problems of interval-based qualitative reasoning. In Weld,
D. S., & de Kleer, J. (Eds.) Readings in Qualitative Reasoning about Physical
Systems.  San Mateo, CA:  Morgan 

Kaufmann, 288-305.  Weld,  D. S., &  de Kleer,  J. (E ds.)  (1990).  Readings
in Qualitati ve Reasoning  about Physical Systems. San Mateo, CA: Morgan
Kaufmann. 

Yilmaz,  O". ( 2005).  Computability-theoretic  limitations of  qualitative
simulation. M. S. Thesis, Bog*azic,i University, I.stanbul, Turkey. 

(http://www.cmpe.boun.edu.tr/graduate/allthesis/m_3.pdf) %%[Page: 25]%%
%%[LastPage]%%