Boolean decomposition using two-literal divisors

This paper is an attempt to answer the following question: how much improvement can be obtained in logic decomposition by using Boolean divisors? Traditionally, the existence of too many Boolean divisors has been the main reason why Boolean decomposition has had limited success. This paper explores a new strategy based on the decomposition of Boolean functions by means of two-literal divisors. The strategy is shown to derive superior results while still maintaining an affordable complexity. The results show improvements of 15% on average, and up to 50% in some examples, w.r.t. algebraic decomposition.Peer ReviewedPostprint (published version