Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
The equivalence of Boolean functions with respect to five invariance (aka translation) operations has been well considered with respect to the Rademacher-Walsh spectral domain. In this paper, we introduce a hybrid approach that uses both the Reed-Muller and the Rademacher-Walsh spectra. A novel hybrid algorithm that maps a Boolean function to a representative function for the equivalence class containing the original function is presented. The algorithm can be used to determine a sequence of translations that maps one function to an equivalent function. We present experimental results that show the hybrid algorithm can determine the equivalence classes for 5 variables much more efficiently than before. We also show that for 6 variables where there are 150,357 equivalence classes, 8 are very difficult, a further 58 are difficult and the remainder are straightforward in terms of the CPU time required by the hybrid algorithm.
Giovanni De Micheli, Mathias Soeken, Dewmini Sudara Marakkalage, Eleonora Testa, Heinz Riener
Giovanni De Micheli, Alessandro Tempia Calvino, Gianluca Radi
Mika Tapani Göös, Gilbert Théodore Maystre