The task of Weighted Model Counting is to compute the sum of the weights of all satisfying assign- ments of a propositional sentence. One recent key insight is that, by allowing negative weights, one can restructure the sentence to obtain a representation that allows for more efficient counting. This has been shown for formulas representing Bayesian networks with noisy-OR structures (Vomlel and Savicky 2008; Li, Poupart, and van Beek 2011) and for first-order model counting (Van den Broeck, Meert, and Darwiche 2014). In this work, we introduce the relaxed Tseitin transformation and show that the aforementioned techniques are special cases of this relaxation.

@inproceedings{MeertStarAI16,
  author = "Meert, Wannes and Vlasselaer, Jonas and Van den Broeck, Guy",
  title = "A Relaxed Tseitin Transformation for Weighted Model Counting",
  booktitle = "International Workshop on Statistical Relational AI",
  month = Feb,
  year = "2016",
  url = "http://starai.cs.ucla.edu/papers/MeertStarAI16.pdf",
  keywords   = {workshop}
}