Generalized Symmetries in Boolean Functions: Fast Computation and Application to Boolean Matching
Jin S. Zhang, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Jerry R. Burch · 2005
In recent years, the notion of symmetry has been extended from classical symmetries to also include constant cofactor symmetries, single variable symmetries and Kronecker symmetries. All these symmetries form a generalized symmetry scheme. Existing methods to detect generalized symmetries require computing the cofactors for each pair of variables to check certain relationships between the cofactors. In this paper, we present a new algorithm that detects all pairs of symmetric variables in one pass over a multi-output BDD. Experiments on the MCNC benchmarks are encouraging. We also propose a potential application of generalized symmetries in Boolean matching. Keywords: Kronecker symmetries, generalized symmetries, Boolean matching.