Ordered binary decision diagrams and their significance in computer-aided design of VLSI circuits

Many problems in computer-aided design of highly integrated circuits (CAD f or VLSI) can be transformed to the task of manipulating objects over finite domains. The efficiency of these operations depends substantially on the c hosen data structures. In the last years, ordered binary decision diagrams (OBDDs) have proven to be a very efficient data structure in this context. Here, we give a survey on these developments and stress the deep interactio ns between basic research and practically relevant applied research with it s immediate impact on the performance improvement of modern CAD design and verification tools.