Incremental Autosymmetry Testing of Regular Functions through AND-Inverter Graphs

Many Boolean functions arising in circuit applications exhibit structural regularities that can be exploited to improve logic synthesis. Among them, autosymmetry is an XOR-based property that allows a function to be studied in a lower-dimensional space through a suitable restriction. In this work, we propose an efficient incremental heuristic for testing autosymmetry directly from And-Inverter Graph representations, without requiring the preliminary construction of a BDD. The method can identify the autosymmetry degree when run to completion, or return a certified lower bound if interrupted, while exploiting algebraic properties of the output to improve performance. Experimental results show the effectiveness of the proposed approach.