A Unified Approach to Canonical Form-based Boolean Matching

In this paper, we face the problem of P-equivalence Boolean matching. We outline a formal framework that unifies some of the canonical form-based approaches to the problem. As a first major contribution, we show how these approaches are particular cases of a single generic algorithm, parametric with respect to a given linear transformation of the input function. As a second major contribution, we identify a linear transformation that can be used to significantly speed up Boolean matching with respect to the state of the art. Experimental results show that, on average, our approach is five times faster than the main competitor on 20-variables input functions, and scales better, allowing to match even larger components.