The Mathematical Foundation of Symbolic Trajectory Evaluation

In this paper we elucidate the mathematical foundation underlying both the basic and the extended forms of symbolic trajectory evaluation (STE) with emphasis on the latter. In addition, we make three contributions to the the┐ory of STE which, we believe, are new. First, we provide a satisfactory answer to the question: what does it mean for a circuit to satisfy a trajectory assertion? Second, we make the observation that STE is a form of data flow analysis and, as a corollary, propose a conceptually simple algorithm for (extended) STE. Third, we show that the ternary model of circuits used by STE is an abstract interpre┐tation of the ordinary boolean model via a Galois connection. We hope that our exposition will make SТЕ, especially its extended form, less mysterious.