Applications of Zero-Suppressed Decision Diagrams

Jon T. Butler · Tsutomu Sasao

May 2022 · Springer Nature

About this ebook

A zero-suppressed decision diagram (ZDD) is a data structure to represent objects that typically contain many zeros. Applications include combinatorial problems, such as graphs, circuits, faults, and data mining. This book consists of four chapters on the applications of ZDDs. The first chapter by Alan Mishchenko introduces the ZDD. It compares ZDDs to BDDs, showing why a more compact representation is usually achieved in a ZDD. The focus is on sets of subsets and on sum-of-products (SOP) expressions. Methods to generate all the prime implicants (PIs), and to generate irredundant SOPs are shown. A list of papers on the applications of ZDDs is also presented. In the appendix, ZDD procedures in the CUDD package are described. The second chapter by Tsutomu Sasao shows methods to generate PIs and irredundant SOPs using a divide and conquer method. This chapter helps the reader to understand the methods presented in the first chapter. The third chapter by Shin-Ichi Minato introduces the ""frontier-based"" method that efficiently enumerates certain subsets of a graph. The final chapter by Shinobu Nagayama shows a method to match strings of characters. This is important in routers, for example, where one must match the address information of an internet packet to the proprer output port. It shows that ZDDs are more compact than BDDs in solving this important problem. Each chapter contains exercises, and the appendix contains their solutions. Table of Contents: Preface / Acknowledgments / Introduction to Zero-Suppressed Decision Diagrams / Efficient Generation of Prime Implicants and Irredundant Sum-of-Products Expressions / The Power of Enumeration--BDD/ZDD-Based Algorithms for Tackling Combinatorial Explosion / Regular Expression Matching Using Zero-Suppressed Decision Diagrams / Authors' and Editors' Biographies / Index

About the author

Tsutomu Sasao received the B.E., M.E., and Ph.D. degrees in Electronics Engineering from Osaka University, Osaka Japan, in 1972, 1974, and 1977, respectively. He has held faculty/research positions at Osaka University, Japan; IBM T. J. Watson Research Center, Yorktown Heights, NY; the Naval Postgraduate School, Monterey, CA; and Kyushu Institute of Technology, Iizuka, Japan. Now, he is a Professor at the Department of Computer Science, Meiji University, Kawasaki, Japan. His research areas include logic design and switching theory, representations of logic functions, and multiple-valued logic. He has published more than 9 books on logic design including, Logic Synthesis and Optimization, Representation of Discrete Functions, Switching Theory for Logic Synthesis, Logic Synthesis and Verification, and Memory-Based Logic Synthesis, in 1993, 1996, 1999, 2001, and 2011, respectively. He has served Program Chairman for the IEEE International Symposium on Multiple-Valued Logic (ISMVL) many times. Also, he was the Symposium Chairman of the 28th ISMVL held in Fukuoka, Japan, in 1998. He received the NIWA Memorial Award in 1979, Takeda Techno-Entrepreneurship Award in 2001, and Distinctive Contribution Awards from IEEE Computer Society MVL-TC for papers presented at ISMVLs in 1986, 1996, 2003, 2004, and 2013. He has served as an associate editor of the IEEE Transactions on Computers. He is a Fellow of the IEEE.Jon T. Butler received the B.E.E. and M.Engr. degrees from Rensselaer Polytechnic Institute, Troy, New York, in 1966 and 1967, respectively. He received the Ph.D. degree from The Ohio State University, Columbus, Ohio, in 1973. From 1987 until 2010, he was a Professor at the Naval Postgraduate School, Monterey, California. From 1974 to 1987, he was at Northwestern University, Evanston, Illinois. He is now a Distinguished Professor Emeritus. During that time he served two periods of leave at the Naval Postgraduate School, first as a National Research Council Senior Postdoctoral Associate (1980-1981) and second as the NAVALEX Chair Professor (1986-1987). He served one period of leave as a foreign visiting professor at the Kyushu Institute of Technology, Iizuka, Japan. His research interests include logic optimization, multiple-valued logic, and reconfigurable computing. He has served on the editorial boards of the IEEE Transactions on Computers, Computer, and the IEEE Computer Society Press. He has served as the editor-in-chief of Computer and the IEEE Computer Society Press. He received the Award of Excellence, the Outstanding Contributed Paper Award, and a Distinctive Contributed Paper Award for papers presented at the International Symposium on Multiple-Valued Logic. He received the Distinguished Service Award, two Meritorious Awards, and nine Certificates of Appreciation for service to the IEEE Computer Society. He is a Life Fellow of the IEEE.