Equational Abstractions for Reducing the State Space of Rewrite Theories

AbstractThe combinatorial explosion of state spaces is the biggest problem in applying model checking methods to concurrent systems. In this paper we present a new state-space reduction technique that is tailored to system specifications in Rewriting Logic, a unified semantic framework for concurrency which is based on conditional term rewriting modulo equational theories. The idea is to hide “unimportant” details of the system's behavior (such as internal computations) in the equations, and to represent only “interesting” state changes (such as communication operations) by explicit transitions. We show how this optimization can be implemented by transforming the Rewriting Logic specification, avoiding the construction of the full state space. Moreover we establish the correctness of our technique by proving that the original and the reduced system are weakly bisimilar, and demonstrate its usability by applying it to the concurrent functional programming language Erlang