A New Data Structure for Complete Implication Graph with Application for Static Learning
Emil Gizdarski, Hideo Fujiwara · NAIST Digital Library (Nara Institute of Science and Technology) · 2000
In this paper we analyze learning techniques based on the Boolean satisfiability method and find that static indirect ∧-implications and the super gate extraction are useful for increasing the precision of low complexity learning procedures. We propose a new data structure for the complete implication graph that allows efficient processing of the static indirect ∧-implications. We show that by deriving and performing the static indirect ∧-implications, some hard-to-detect static indirect implications can be easily found during static learning. In addition, the static indirect ∧-implications can be used to perform (without spare operations) some dynamic indirect implications during branch and bound search and dynamic learning. In this way, the new data structure of the complete implication graph increases efficiency and precision of both static and dynamic learning as well as branch and bound search. We implement this data structure in two implicit static learning procedures. Experimental results for the ISCAS'85 and ISCAS‘89 benchmark circuits demonstrate the efficiency and precision of the implemented static learning procedures as well as the efficiency of the new data structure of the complete implication graph. We expect that the contribution of the new data structure will be more visible when the super gate extraction is also implemented.