Abstract: The problem of finding a minimum AND-XOR expression for a given Boolean function is known to be very hard. In this paper we investigate whether a rule-based approach can help minimizing AND-XOR expressions for functions which are too large to be handled by algorithmic-based approaches. We apply a simple greedy search based on a set of local transformations to the positive polarity Reed- Muller expression of Boolean functions. Our experiments on large functions show surprisingly good results. We achieve 23% reduction in the number of literals on average. We believe that much better results can be achieved if a more sophisticated non-greedy search is used. The purpose of this paper is to motivate more research in this direction.
Keywords: Reed-Muller expression; AND-XOR expression; local transformation; greedy search.