Binary Decision Diagrams (BDDs) and Shared Binary Decision Diagrams (SBDDs), which are improved BDDs, are useful for implementing VLSI logic design systems. Recently, these representations, which are graph representations of Boolean functions, have become popular because of their efficiency in terms of time and space. The forms of the BDD vary with the order of the input variables though they represent the same function. The size of the graphs greatly depends on the order. The variable ordering algorithm is one of the most important issues in the application of BDDs. In this paper, we consider methods which reduce the graph size by reordering input variables on a given BDD with a certain variable order. We propose the Minimum-Width Method which gives a considerably good order in a practicable time and space. In the method, the order is determined by width of BDDs as a cost function. In addition, we show the effect of combining our method with the local search method, and also describe the improvement using the threshold. Experimental results show that our method can reduce the size of BDDs remarkably for most examples. The method needs no additional information, such as the topological information of the circuit. The results can be a measure for evaluation of other ordering methods.

Proposed here is an internal representation and mapping method for multimedia information in which retrieval is based on the impression documents desired to make. A user interface design for a system using this method is also proposed. The proposed internal representation and mapping method represents each desired document impression as an axis in a semantic space. Documents are represented as points in the space. Queries are represented as subspaces. The proposed user interface design employs a method of visual presentation of the semantic space. Pictorial examples are given to illustrate the range of impressions represented by the axes. The relations between the axes are represented by dispersion diagrams for the documents stored in the document base. With this method, the user can intuitively decide the appropriate subspace for his needs and can specify it directly. For evaluation purposes, a prototype system has been developed. An image retrieval experiment shows that the proposed internal representation and mapping method and the user interface design provide effective tools for information retrieval.