Boolean Matching

• Question:

  Exists P (permutation matrix), such that
  
  f(x) = g(P x) is a tautology

• Use OBDDs for tautology checks

• Vary input order of one graph

• Filters to reduce the # of permutations:

  • Match # of binate and unate inputs
  • Use symmetry

Previous slide

Next slide

Back to first slide

View graphic version