In this paper, we present the condition for the effective wire addition in Look-Up-Table-based (LUT-based) field programmable gate array (FPGA) circuits, and an optimization procedure utilizing the effective wire addition. Each wire has different characteristics, such as delay and power dissipation. Therefore, the replacement of one critical wire for the circuit performance with many non-critical ones, i.e., many-addition-for-one-removal (m-for-1) is sufficiently useful. However, the conventional logic optimization methods based on sets of pairs of functions to be distinguished (SPFDs) for LUT-based FPGA circuits do not make use of the m-for-1 manipulation, and perform only simple replacement and removal, i.e., the one-addition-for-one-removal (1-for-1) manipulation and the no-addition-for-one-removal (0-for-1) manipulation, respectively. Since each LUT can realize an arbitrary internal function with respect to a specified number of input variables, there is no sufficient condition at the logic design level for simple wire addition. Moreover, in general, simple addition of a wire has no effects for removal of another wire, and it is important to derive the condition for non-simple and effective wire addition. We found the SPFD-based condition that wire addition is likely to make another wire redundant or replaceable, and developed an optimization procedure utilizing this effective wire addition. According to the experimental results, when we focused on the delay reduction of LUT-based FPGA circuits, our method reduced the delay by 24.2% from the initial circuits, while the conventional SPFD-based logic optimization and the enhanced global rewiring reduced it by 14.2% and 18.0%, respectively. Thus, our method presented in this paper is sufficiently practical, and is expected to improve the circuit performance.

In this paper, we will discuss a map synthesis system which handles static information (geographic objects) as well as dynamic information (traffic conditions, weather, etc. ). In addition to geographic thesauruses used in the previous systems, we will use co-existence relationships to improve the quality of maps generation. The system is considered to be general purpose (not restricted to car navigation nor travel maps) and can generate arbitrary maps according to the user's specification. It is very difficult for a user to specify a query which corresponds to the required map, because map description is not easy. The system should automatically generate missing information or find errors in the user specification. For the purpose we use geographic domain thesauruses which contain aggregation and other geographic relationships as well as conventional thesaurus hierarchy. In this paper, we will discuss to use co-existence relationships to enhance ability to select geographic objects automatically. Co-existence specifies relationships among geographic objects which should appear in a map together although they may not have geographic relationship by thesauruses. By utilizing co-existence relationships, a user can acquire much more understandable maps.

Queries to generate a map from geographic detabases are too large and complex for users to specify all components in it. Thematic parts of the map should be described by users as ad hoc queries. However, background parts of it should be inferred from users' queries corresponding to the thematic parts. Furthermore, it is important for the map systems to lead users' constructing their ad hoc queries and to infer visualization methods applied to the data retrieved by the ad hoc queries. This paper discusses a framework to infer supplemental queries and visualization methods in order to make the retrieval results into a feasible map using geographic domain hierarchical levels, geographic domain thesauruses and existing example queries. The framework allows users to know mismatches of components in queries, inappropriate queries for maps, and deriving candidates for additional components in queries.

In this paper, we will discuss circuit minimization techniques based on the multiple output capability of FPGA blocks. Since previous methods only consider two independent output functions, we will discuss a more complicated case when the two functions are mutually related. We also discuss a method to maximize flexibility of a specified cell output in the given FPGA block. If a set of possible functions for a cell which will not change the FPGA output function is large, we call that the flexibility of this cell is high. The concept of Sets of Pairs of Functions to be Distinguished (SPFDs) introduced by Yamashita et al. is a powerful tool to minimize a given FPGA circuits. In this paper, an extension of the concept, Priority based SPFDs (PSPFDs) is introduced to maximize the flexibility of output functions realized by such internal cells. By using PSPFDs for our new method, we can utilize the multiple output capability very well. Combination with the previous methods with PSPFDs is also shown to be important. We have implemented these methods and applied them to MCNC benchmarks mapped into 5-variable function blocks. To make a comparison with other methods, we have implemented methods using well-known merging algorithms utilizing the same multiple output capability. Experimental results show that our methods can reduce the number of blocks in the initial circuits by 40% on average. This reduction ratio is 16% higher than that of previous methods.

The Transduction Method is a powerful way to design logic circuits, utilizing already existing circuits. A set of permissible functions (SPF) plays an essential role in such circuit transformation/reduction, and is computed at each point (connection or gate output). Currently, two types of SPFs have been used: the maximum SPFs (MSPFs) and compatible SPFs (CSPFs). At each point, the MSPF is literally the set of all PF's, and CSPF is a subset of the MSPF. When CSPFs are calculated, priorities are first assigned to all gates in the circuit. Based on the priorities, it is decided which subset is to be selected as the CSPF. The quality of the results depends on the priorities. In this paper, the concept of super-sets of permissible functions (SSPFs) is introduced to reduce the effect of the priorities that CSPFs depend on. In order to loosen the dependency, each SSPF is computed to contain CSPFs which are candidates to be selected. The experimental results show that the SSPF-based Transduction Method has intermediate reduction capability and takes an intermediate computation time between the MSPF-based and CSPF-based ones. The capability and the time are considered as an acceptably good trade-off. In addition, without any transformations, since SSPFs are the maximum super-set, SSPFs are applicable for analyzing the maximum performance of the CSPF-based transformation, for comparison with the MSPF-based one. Theoretically, the number of connectable gate pairs detected by the MSPFs is 100%. According to the experimental results obtained using SSPFs, on average, 99% are detectable by SSPFs and 1% are detectable only by using the MSPFs. The results show that by using CSPFs, 72% of connectable gate pairs are detectable with any priority assignment and 99% (SSPFs capability) are detectable on average even when the best priorities are assigned. According to the experimental results of CSPF calculation with five priorities, 82% to 93% are practically detectable on average. This is the first quantitative analysis realized by SSPFs which compares the CSPF-based and MSPF-based Transduction Methods with respect to the coverage of PF's.

In Codd's relational data model, several dependencies have been introduced to specify the intensional properties of a relation. Fagin and independently, Zaniolo introduced the notion of a multivalued dependency (MVD). The definition of MVD's refers to an underlying set of attributes of a relation. The embedded multivalued dependency (EMVD), which is also introduced by Fagin, is an MVD that holds for a projection of an original relation on the subset of attributes of the relation. The properties of EMVD's are not well known although EMVD's play an important role in designing relation schemata by Fagin's decomposition approach. Our study in this paper is motivated from the following problems: (a) Since the validity of an MVD depends on an underlying set of attributes, it is not so easy to specify valid" MVD's for a relation with many attributes. (b) There has not been a useful tool to analyze whether or not a set of relation schemata obtained by Fagin's decomposition approach can represent the same data and the same dependencies of an initial relation schema. Our standpoint is to handle these problems by studying the properties of EMVD's. The main results of this paper are the following: (1) A basic theorem about the interaction between MVD's and EMVD's is provided. Several useful inference rules for MVD's and EMVD's are derived from this theorem. (2) A marked Hasse diagram called a dependency diagram is introduced to investigate the interections between MVD's and EMVD's. (3) We provide some conditions for an MVD or a set of MVD's to be invariant under the addition or deletion of attributes. (4) Some useful equivalence relationships between two dependency sets including MVD's and EMVD's are provided. We also provide some conditions to represent a given dependency set in a reduced form.