Narrow Results

The purpose of this short note is to show that the problem of reconstructing a directed forest from a collection of leaf-to-root paths can be done efficiently in parallel by reducing the problem to integer sorting. Specifically, given M the total length of the paths in the collection, and n the number of distinct node labels, our algorithm reconstructs the corresponding forest (if such a forest exists) in O(M/p) time using p ≤ M/n processors or time using M/n < p < M processors, and O(M) space on the EREW-PRAM.

Refactoring for locks is widely used to improve the scalability and performance of concurrent programs. However, when refactoring from coarse-grained locks to fine-grained locks, the behavior of concurrent programs may be changed. To this end, we present LockCheck, a consistency-checking approach based on the parallel extended finite automaton for fine-grained locks. First, we model the critical sections of concurrent programs through control flow analysis and dependency analysis. Second, we sequentialize the concurrent programs to get all the possible transition paths. Furthermore, it reduces the exploration of the redundant paths using partial order theory to obtain the compared transition paths. Finally, we combine consistency rules to check the consistency of the program before and after refactoring. We evaluated LockCheck in five open-source projects. A total of 1528 refactoring operations have been evaluated and 93 inconsistent refactoring operations have been detected. The results show that LockCheck can effectively detect inconsistent behavior when coarse-grained locks are refactored into fine-grained locks.

Efficient algorithms for checking consistency of a set of spatial constraints among spatiotemporal objects are crucial for many practical application systems needing real-time response. This paper is focused on the consistency for directional spatial constraints in a two-dimensional Euclidean space, which is critical in application domains such as geographic information systems, battlefield visualization, transportation, etc. We propose a dimension graph representation to maintain the Euclidean spatial constraints among 2D objects (points, intervals, regions). The basic idea is to project the spatial constraints on both X and Y dimensions, and then to construct a dimension graph on each dimension. The dimension graph representation transforms the problem of consistency checking into the problem of graph cycle detection. Consistency checking for conjunctive constraints can then be achieved in linear time complexity. This approach is much more efficient than competing approaches when there are few disjunctions in the spatial constraints, which are often true in above applications. We also demonstrate that the proposed algorithm can guarantee global consistency.

The train control system is a typical safety-critical system, the consistency of the state of the system process is an important prerequisite of the reliable decision-making for the train control system. This paper explores the properties of the decision-making of safety-critical system, then a process of safety-critical decision is proposed, with the definition of the critical component and cognate variables being presented. The formulations of consistency checking based computation tree logic is developed. A case of re-designed routing decision process of the train is modelled by MCMAS, the consistency verification shows that the new decision logical model ensures the confirmation of state consistency of the critical components, which can provide the enlightenment for the development of intelligent train control system.

Interaction among expressive modeling constructs in different parts of complex diagrams may lead to implicit consequences that are not readily recognized, and may cause various forms of redundancies and inconsistencies. It is desirable to equip existing CASE tools with automated reasoning capabilities that facilitate analysis of relevant properties of models. This article presents two knowledge-based approaches to detection of inconsistencies in UML models. The first approach is based on Description Logics. It is typically suitable for formalizing the structural part of a model and analyzing the semantic consistency thereof; however, its application to other parts of the model is limited due to the restricted ability of these logics to handle queries and rules. The second approach complements the first by providing extensive rule-oriented facilities, based on the XML Declarative Description theory, for reasoning with model elements of all kinds that are encoded in the XML Metadata Interchange format, a standard text-based format for UML. Since most tools supporting UML export models in this format, this approach works directly with existing available information sources and can thus be regarded as a lightweight formal method.

This paper proposed a novel multiresolution image fusion approach, which is based on bidimensional empirical mode decomposition (BEMD). The BEMD image is different from the former multi-scale image fusion algorithms which need predetermined filters or wavelet functions. This letter made research on several key issues relevant to the 2D image decomposition and proposed a BEMD image fusion rule to 2D Intrinsic Mode Functions (2D IMF) and residue image of BEMD. The experiments showed the improved performance of this novel algorithm compared with the discrete wavelet transform (DWT).

In this paper, we propose a comprehensive data integration and quality assurance model, called CHARIOT, for agro-meteorological data. This model comprised of two modules: an intermediary module and a data quality control module. The intermediary provides users with reliable and continuous access to heterogeneous weather databases from various sources; it also solves various compatibility issues in meteorological time series data. The data quality control tool consists of a multi-layer system spanning internal, temporal and spatial data checks. These two modules combined together provide users with clean and error-free inputs for weather-driven agricultural management decisions. When applying CHARIOT to weather data for a real-life agricultural application, CHARIOT is shown to be effective in controlling and improving data quality, which in turn leads to better and more accurate agricultural management decisions.