We propose three search methods for obtaining exact minimum AND-EXOR expressions: the depth-first, the breadth-first, and the depth-first-when-optimum searches. They minimize up to 7-variable functions in a practical computation time. Experimental results to compare the efficiency of these methods are presented. The depth-first search, which saves the memory consumption, minimizes the 16-variable benchmark function t481 without memory exhaustion. This search method is the fastest among these three methods on the average computation time for randomlygenerated single-output functions. The depth-firstwhen- optimum search is the fastest on the computation time for the most of benchmark functions. For some benchmark functions, however, the breadth-first search is the fastest.