An efficient critical path tracing algorithm for sequential circuits

Several timing verification algorithms for combinational circuits have been proposed in the last few years. However, similar algorithms do not exist for sequential circuits. Existing algorithms have difficulty in performing timing verification even for combinational circuits due to the excessive computation time and memory requirement for identifying the critical path. This paper presents a critical path analysis algorithm for sequential circuits. The algorithm can be used to identify the critical path of a sequential circuit while considering exact operation of the circuit without assuming the use of scan techniques. The input sequence which sensitizes the critical path is determined as well.     

HGA*, an efficient algorithm for path planning in a plane

Existing and prospective approaches and methods are considered for path planning in a plane. The existing planning algorithms are analyzed and qualitatively assessed. A new efficient path-planning algorithm, HGA*, is described, which enables searching for a plan under conditions of limited time and computational resources and under additional constraints (such as the dynamic changes and partial observability of the planning terrain). The results are presented, which show the experimentally proven advantages of HGA* over the available analogues.     

An efficient entropy of sum approach for measuring diversity and interdisciplinarity

Rousseau and Mutz argued that the existing researches on diversity measure methods, such as the Rao-Stirling index, DIV, etc., have shortcomings, and urged colleagues to find a better framework for diversity measure. Based on Shannon entropy and entropy of degree vector sum, in this contribution a new diversity measure EDVS (Entropy of Degree Vectors Sum) is proposed, which meets all requirements of variety, balance and disparity, and can directly calculate the value of diversity from the observed sample data without calculating the joint probability distribution of two random variables, or mutual information. The empirical results show that: (1) the ranking of the EDVS measure has a higher Spearman correlation coefficient with DIV and DIV* than with Shannon entropy. (2) The EDVS ranking is more relevant with DIV* than with DIV. (3) The diversity of soft science journals is higher than that of hard science journals, which indicates that the interdisciplinary research of social sciences and humanities is more common than that of hard sciences such as sciences and engineering sciences. (4) Rao-Stirling index and DIV index are more sensitive to sample size. The computational complexity of the Rao-Stirling index and DIV index is $O\left(n^3\right)$, while the computational complexity of the EDVS index is $O\left(n^2\right)$. This provides the feasibility for analyzing high-dimension networks and large data sets. Results of verification on different types of data sets show that EDVS can not only effectively measure the diversity of disciplines in interdisciplinary research, but also effectively measure the diversity of other entities.     

An effective and efficient results merging strategy for multilingual information retrieval in federated search environments

Multilingual information retrieval is generally understood to mean the retrieval of relevant information in multiple target languages in response to a user query in a single source language. In a multilingual federated search environment, different information sources contain documents in different languages. A general search strategy in multilingual federated search environments is to translate the user query to each language of the information sources and run a monolingual search in each information source. It is then necessary to obtain a single ranked document list by merging the individual ranked lists from the information sources that are in different languages. This is known as the results merging problem for multilingual information retrieval. Previous research has shown that the simple approach of normalizing source-specific document scores is not effective. On the other side, a more effective merging method was proposed to download and translate all retrieved documents into the source language and generate the final ranked list by running a monolingual search in the search client. The latter method is more effective but is associated with a large amount of online communication and computation costs. This paper proposes an effective and efficient approach for the results merging task of multilingual ranked lists. Particularly, it downloads only a small number of documents from the individual ranked lists of each user query to calculate comparable document scores by utilizing both the query-based translation method and the document-based translation method. Then, query-specific and source-specific transformation models can be trained for individual ranked lists by using the information of these downloaded documents. These transformation models are used to estimate comparable document scores for all retrieved documents and thus the documents can be sorted into a final ranked list. This merging approach is efficient as only a subset of the retrieved documents are downloaded and translated online. Furthermore, an extensive set of experiments on the Cross-Language Evaluation Forum (CLEF) () data has demonstrated the effectiveness of the query-specific and source-specific results merging algorithm against other alternatives. The new research in this paper proposes different variants of the query-specific and source-specific results merging algorithm with different transformation models. This paper also provides thorough experimental results as well as detailed analysis. All of the work substantially extends the preliminary research in (Si and Callan, in: Peters (ed.) Results of the cross-language evaluation forum-CLEF 2005, 2005).

An improved algorithm for evaluation of the product of an exponential function with an error function complement

Some mathematical CAD packages are inadequate in computing the composite functions involving the product of an exponential function and an error function complement. These functions arise in physical applications, such as problems in diffusion. Their importance warrants a composite treatment. If their component factors are computed individually, discontinuities in the evaluations arises, as shown in some CAD packages. An improved algorithm is presented which overcomes this deficiency, and provides a fast evaluation. Such evaluation is successful even using floating point numbers with single precision. The potential for numerical overflow associated with large arguments has been overcome.