SAT 2004 START ConferenceManager    


Encoding Global Unobservability for Efficient Translation to SAT

Miroslav N. Velev

Presented at The Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004), Vancouver, BC, Canada, 10-13 May 2004


Abstract

The paper studies the use of global unobservability constraints in a CNF translation of Boolean formulas, where the unobservability of logic blocks is encoded with CNF unobservability variables and the logic output values of the blocks with CNF logic variables. Each blocks unobservability variable is restricted by local unobservability constraints, expressing conditions that the output value of the block will not propagate to the primary output, given values of inputs to nearby gates on the path to the primary output. Global unobservability constraints add conditions that a block is unobservable if all paths to the primary output pass through logic blocks that are unobservable. By introducing a cut of unobservability check-points at the inputs of the top gate in a Boolean formula, we can impose global unobservability constraints for every logic block. The results show that global unobservability constraints lead to small additional speedup if local unobservability is exploited, but make the SAT-time less dependent on values of parameters in the translation.


  
START Conference Manager (V2.47.2)
Maintainer: rrgerber@softconf.com