O. Yilmaz and A. C. Cem Say

Volume 27, 2006

**Links to Full Text:**

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.

%%[ 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 0which 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]%%