Blind spots of qualitative simulators

Abstract

Qualitative simulators are important tools for analyzing the possible behaviors of a dynamical system. The technique of qualitative simulation has some theoretical limitations. For some input system models, a qualitative simulator either predicts spurious (impossible) behaviors or does not predict some possible behaviors. It has been shown that a “perfect” qualitative simulator cannot be built, because there are some spurious behaviors which cannot be proven to be spurious. This thesis questions the possibility of building a qualitative simulator which can detect and eliminate all spurious behaviors which can be proven to be so. We find the answer to be negative. For each qualitative simulator which possesses some reasonable properties, there is an efficiently constructible, provably inconsistent input which cannot be rejected by the simulator in question. In addition, it is shown that there exist spurious behaviors which require exponential time to detect.