Boolean matching is to check the equivalence of two target functions under input permutation and input/output phase assignment. This paper addresses the permutation independent (P-equivalent) Boolean matching problem. We will propose a matching algorithm seamlessly integrating Simulation and Boolean Satisfiability (S&S) techniques. Our proposed algorithm will first utilize functional properties like unateness and symmetry to reduce the searching space. In the followed simulation phase, three types of input vector generation and checking method will be used to match the inputs of two target functions. Experimental results on large benchmarking circuits demonstrate that our matching algorithm is indeed very effective and efficient to solve Boolean matching for large Boolean networks.

In this paper, we will propose an incremental learning approach to solve Boolean matching for incompletely specified functions. This approach can incrementally analyze current feasible partial mappings, detect and eliminate redundant manipulations in a proactive way. A new type of signature exploiting single variable symmetries is also given to reduce the searching space. Moreover, a SAT model of Boolean matching will be proposed to handle large Boolean functions. Through the utilization of these novel mechanisms, a drastic improvement on the performance of our Boolean matching algorithms are achieved. The experimental results demonstrate the effectiveness and efficiency of the proposed learning-based and SAT-based Boolean matching algorithms on many large benchmarking circuits.