Symbolic FSM traversals based on the transition relation

We define the new “exist” generalized cofactor and image restrictor, a Boolean operator that supports the distributivity of conjunction and existential quantification. It finds a major application in existentially quantified products, like the transition relations that describe the sequential behavior of synchronous sequential circuits. We prove that the “exist” cofactor extends and includes the previous uses of the cofactor as an image restrictor. Aware of the fact that cofactoring sometimes makes binary decision diagrams (BDD´s) more complex, we introduce selective cofactoring, i.e., we cofactor only subsets of functions, allowing a mix between cofactoring and conjunction. As a result, we propose an image computation method that includes techniques presented earlier. Experimental results show that we are able to reduce memory peaks, to lower overall memory occupation, and to reduce CPU time for symbolic traversal of some large benchmark circuits. We are also able to present experimental evidence on circuits that, to the best of our knowledge, have not yet been traversed