Invariant-preserved Transformation of State Machines from Equations into Rewrite Rules

A state machine can be specified as either an equational theory or a rewrite theory in algebraic approaches. The former is used for theorem proving, and the latter for model checking. We have proposed an approach to transform a class of equational theories into rewrite theories in order to use them in the combination of the two verification techniques. This paper shows the correctness of the transformation with respect to its preservation of invariant properties. Invariant-preservation guarantees that a counterexample found by model checking a generated rewrite theory is also a counterexample of the same invariant in the original equational theory, which provides the theoretical support to the utilization of the transformation in combination of theorem proving and model checking.