Design of decision diagrams with increased functionality of nodes through group theory

Abstract

This paper presents a group theoretic approach to the design of Decision diagrams (DDs) with increased functionality of nodes. Basic characteristics of DDs determine their applications, and thus, the optimization of DDs with respect to different characteristics is an important task. Increased functionality of nodes provides for optimization of DDs. In this paper, the methods for optimization of binary DDs by pairing of variables are interpreted as the optimization of DDs by changing the domain group for the represented functions. Then, it is pointed out that, for Abelian groups, the increased functionality of nodes by using larger subgroups may improve some of the characteristics of DDs at the price of other characteristics. With this motivation, we proposed the use of non-Abelian groups for the domain of represented functions by taking advantages from basic features of their group representations. At the same time, the present methods for optimization of DDs, do not offer any criterion or efficient algorithm to choose among a variety of possible different DDs for an assumed domain group. Therefore, we propose Fourier DDs on non-Abelian groups to exploit the reduced cardinality of the Fourier spectrum on these groups.