A compositional method for deciding equivalence and termination of nondeterministic programs

Abstract. In this paper we address the problem of deciding may- and must-equivalence and termination of nondeterministic finite programs from second-order recursion-free Erratic Idealized Algol. We use game semantics to compositionally extract finite models of programs, and the CSP process algebra as a concrete formalism for representation of models and their efficient verification. Observational may- and must-equivalence and liveness properties, such as divergence and termination, are decided by checking traces refinements and divergence-freedom of CSP processes using the FDR tool. The practicality of the approach is evaluated on several examples.