The row incompatibility and complement graph - A Novel concept of graph for logic synthesis1

The paper presents a new concept of graph - the Row Incompatibility and Complement Graph. The idea was developed as a part of a new decomposition algorithm dedicated for PAL-based CPLD-s. A specific feature of the graph is that it contains two kinds of edges: connecting mutually incompatible nodes, and connecting mutually complementing nodes. The graph can be useful in certain class of optimization problems, in which compatibility of bit patterns in both the true and the complemented form has to be analyzed. Appropriate algorithms for the graph building and coloring are also presented.