Autosymmetry of Incompletely Specified Functions

Autosymmetric Boolean functions are 'regular functions' that are rather frequent in the set of Boolean functions describing standard circuits. Autosymmetry is typically exploited for improving the synthesis time and the quality of the optimized circuits. This paper studies in not a naive way, for the first time, the autosymmetry of incompletely specified functions, i.e., Boolean functions with don't care conditions. The theory of autosymmetry for completely specified functions is extended to the incompletely specified case and a new heuristic algorithm is provided for the detection of autosymmetry. The experimental results validate the theoretical study and show that the 77 % of the considered benchmarks has an improved autosymmetry degree.