On the Detecting of Symmetries of Switching Functions for Eflicient Design of Decision Trees and Decision Diagrams

Abstract

This paper presents an approach to detect symmetries of switching functions for efficient design of Reed-Muller decision trees (DTs) and decision diagrams (DDs). The information theory measures of switching functions are used to determine possible symmetric variabies and therefore to reduce search space. This approach allows to detect different types of symmetries of any variables coincident. We consider the technique to apply symmetries properties that can significantly improve Reed-Muller DT or DD design. We implement symmetry detection algorithm as a part o f program for switching function minimization based on DT design. Experiments have been performed on MCNC benchmarks and the results verify the efficiency of our approach.