Abstract:Bisimulation is adopted in the π-calculus as the criterion to identify processes. For finite-state processes, bisimulation equivalence is decidable. In this paper, an optimization technique for a bisimulation checking algorithm is presented. It works by instantiating input names only to those free names which are used in subsequent matches. The technique can significantly reduce the required time and space, as illustrated by several benchmark examples. The correctness of the optimization is also proven.

Abstract:Hypertext is a kind of unstructured document. It is impossible to realize the search based on content and topic for hypertext documents. However, hypertext is one of the most important ways of information storage and organization in the Internet. Therefore, in order to realize the effective management and the search of hypertext documents, a new and practical method named HtoDB for converting unstructured hypertext to database is presented. In the paper, the requirements and functions for converting hypertext to database are analyzed, the converting model and algorithm are also put forward according to the graph theory. The algorithm and model presented in this paper are verified in the project of “LU XUN digital library system”.

Abstract:The object possesses inherent parallelity. Combination of object-oriented programming with distributed-parallel processing will bring about object-oriented distributed parallel system, not only having object-oriented property but also making better use of system resources and shortening user's computing time as well. In this paper, a novel C++ object distributed-parallel mechanism is proposed based on PVM (parallel virtual machine). The object distributed-parallel mechanism is supported by the PVM system whose protocol and pvmlib have been made backward compatible extension. It uses preprocessor to separate the parallel-classes from user's job program and dispatches them to host computers in PVM to compile and run there. Through mapping parallel-class to PVM task, request object message to request PVM task message, the mechanism implements object distributed-parallelism of the parallel-class. The results of the experiment show that (when the size of question is big enough) the mechanism may make better use of the system resource, run user program efficiently, and simplify the PVM application programming.

Abstract:An object-oriented distributed programming language NC++ which is based on NOW (network of workstations) environment is introduced in this paper. It is an extension of DC++. NC++ gives a rather complete programming environment, including NC++ pre-compiler, visual-programming interface, multicast communicating facility and a test system. It improves the process group management and inter-process communication facilities, and puts forth a DSM (distributed shared memory) subsystem based on belief network, which is used to manipulate C++ global variables. In practice, NC++ offers simplicity for distributed program design without sacrificing the performance.

Abstract:Multi-Table join is a common operation for evaluating OLAP queries posed to a data warehouse. The performance of this multi-table join is one of the key problems in the research of data warehouses. Based on the Star Schema for a data warehouse, this paper introduces a new algorithm M-Join for the multi-table join. Compared with the traditional multi-table join processing by the Relational Database Management System, this new algorithm, taking adequate considerations on the characteristics of the data in a data warehouse environment, completes the join by scanning every table only once, thus greatly improves the performance of OLAP query processing. The paper presents and analyzes the experimental results of this comparison.

Abstract:Converting quantitative attributes into Boolean attributes is the general way for mining quantitative association rules. So how to reasonably partition domain values is very important. Traditional method can not get the easy to understand knowledge because it can not reflect the actual data distribution or the partition is too sharp. In this paper, a new method——cloud transform, which uses many concepts represented by cloud model to fit the real distribution of data——is introduced. This method can reflect the distribution of data in that domain while keeping the soft boundaries. Therefore, the discovered association rules are also easy to understand.

Abstract:It is an efficient way to use SDG (system dependence graph) in slicing object-oriented program. But SDG is too complicated, so it may produce mistakes during constructing SDG, which will lead to inaccurate result. In this paper, the SSDG (simplified system dependence graph) is presented, which ignores nodes and edges representing parameter-in or parameter-out and summary edges. Meanwhile, the concept of coarse-grained slice for object-oriented program is defined, its properties are discussed, the relationships between coarse-grained slice and fine-grained slice are analyzed, the object-oriented coarse-grained program slice is computed based on simplified system dependence graph, and the implementation is also discussed.

Abstract:Image segmentation can be regarded as the problem of two-class pattern classification. How to apply the maximum likelihood clustering algorithm to image segmentation is discussed in this paper. Simulated annealing technology is used to solve the problem of maximum likelihood clustering, which avoids the local optimal solution of iterative method. It shows better image segmentation effect than the famous Otsu algorithm and iterative method with less classification error than iterative method.

Abstract:Parallel execution of the multi-join query is one of the research emphases of the parallel database. The traditional parallel query processing algorithm can not capture the intrinsic characteristic of object-oriented database and its query, and the efficiency of the traditional algorithm is low. Hence, the semi-join-based optimization method of query processing in the distributed database is utilized, a semi-join-based parallel query processing algorithm is proposed, and the performance evaluation results show that the semi-join-based parallel query processing algorithm is an efficient practical algorithm.

Abstract:The DIDAPPER (distributed intrusion detector with apperception) system presented in this paper is a distributed intrusion detector with apperception. The distributed architecture, the apperception ability and the sharing of knowledge are evident characteristics of the DIDAPPER. This paper focuses on the apperception ability of DIDAPPER. Traffic specimens and IP traps are DIDAPPER's new concepts, which can capture and recognize abnormal traffics and are suitable for monitoring the large scale network attacks. The other aspect of DIDAPPER's apperception ability comes from the neural network algorithm. The BP neural network with learning ability has been applied to traffic analysis, and shows good effect on the recognition of traffic patterns.

Abstract:A connected component and transitive closure parallel algorithm using pointer jumping technique is presented in this paper, which runs on n×n wormhole routed 2D mesh in time O(log²n). A minimum spanning tree (MST) parallel algorithm running on the same model in time O(log³n) is also presented. These improve the lower time bound O(n) on n×n store-and-forward routed 2D mesh. Compared with other known algorithms running on various non-bus-connected parallel machines with distributed memory, the time complexity of the connected component and transitive closure parallel algorithm is optimal.

Abstract:In this paper, a scheme for extending traditional system dependence graph based on object orientation is presented, i.e., an object-oriented system dependence graph (OOSDG) suitable for object-oriented program is constructed by combining SDG with ClDS (class dependence subgraph) and CHS (class hierarchy subgraph). The extension of syntax and semantics and function of SDG are discussed. Meanwhile, the algorithm for constructing OOSDG is provided, and application aspect is also analyzed.

Abstract:Surface reconstruction from dense scattered points is of great importance in a variety of situations such as reverse engineering for mechanical products, computer vision and of biomedical images from two-dimensional contours. In this paper, the authors present an algorithm to automatically reconstruct triangular grid representation of a surface from scattered points. The source data may include no additional information other than coordinates of the measured points. In the algorithm, tangent plane of the surface at each point is first calculated according to the point and its neighbor points. In an optimized sequence, normal vectors of the tangent planes are oriented to the outside of the surface. Finally, marching cube method is used to output the triangular representation of the surface. The method put forward to calculate the tangent plane not only promotes the efficiency but also improves the reconstruction effect, especially in the boundary areas and/or sharp arrises. The problem of ‘isolated island’ probably encountered in normal vector propagation is settled. The spatial partitioning scheme put forward in the paper greatly improves the efficiency of the algorithm. Results of the examples show that the algorithm is satisfying.

Abstract:Knowledge is the precondition for an agent to compute. In dynamic and non-deterministic multi-agent systems, agent should be able to acquire the knowledge timely and effectively so as to solve the problems. The existing knowledge-acquiring models can't meet the knowledge-acquiring requirements in dynamic and non-deterministic multi-agent system and the agent's capability of acquiring knowledge is limited. The systematic knowledge-acquired cooperation models (KACM) is presented for agent to effectively acquire knowledge in multi-agent systems, including passive model, active terminating model and active non-terminating model. Based on the speech act theory and a formal framework of branch temporal logic, the communication acts in KACM are discussed, how agent responses to the communication acts is investigated, the rigorous semantics of the speech acts and the KACM are defined, and lastly the significance of the research is presented.

Abstract:In this paper, from the functional point of view, a statistics-based approach for rule extraction from trained neural networks is proposed. This approach introduces statistical technique to evaluate extracted rules so that the rule set could well cover the instance space. It deals with continuous attributes in a unique way so that the subjectivity and complexity of discretization are lowered. It adopts ordered rule representation so that not only the rules have concise appearance but also the consistency process could be released when the rules are used. Moreover, this approach is independent of the architecture and training algorithm so that it could be easily applied to diversified neural classifiers. Experimental results show that the symbolic rules extracted via this approach are comprehensible, compact, and with high fidelity.

Abstract:The disadvantage of the traditional mutation operator of GAs was analyzed in this paper, and a DMO (dyadic mutation operator) was presented to take the place of the traditional one. The function of DMO to prevent premature convergence was also discussed. Meanwhile, according to the features of binary-based GAs, an implicit implementation for decoding the chromosomes for GAs was presented so that the run time of the improved program for GAs was shortened by 6～50 times compared with the original one. The performance of the genetic algorithm is tested based on the DMO (GADMO) in several aspects. The experimental results show that the GADMO can converge quickly and its robustness of parameters is strong. The GADMO can prevent the premature convergence effectively. By improving the mutation operator and the decoding algorithm, the optimization speed of GA is speeded up greatly.

Abstract:Termination reflects desirable behavior property of active database systems. At present, termination analysis is based on triggering and activation graphs, the result of which is conservative. In this paper, “deactivation graph” is introduced to express the fact that one rule's action may falsify another rule's condition. In combination with triggering and activation graphs, a more generalized “relationship graph” is defined, based on which a new algorithm for termination analysis of active rule set is proposed, which improves the accuracy of termination analysis for active rule set.

Abstract:This paper addressed the features of dynamic-alphabet model for arithmetic coding and problems pertaining to model building. Both theory and experiments show that without loss of time performance, the dynamic-alphabet model provides more accurate prediction and consequently has better coding efficiency. Dynamic alphabet is a fresh but key concept to the building of statistical model of text compression for any natural language of large alphabet set, such as Chinese.

Abstract:Discovering maximum frequent itemsets is a key problem in many data mining applications. In this paper,the DMFI (discovery maximum frequent itemsets) algorithm which combines the bottom-up and top-down searches is proposed to solve this problem. Using the unique ordering method and efficient pruning strategy, the number of candidete itemsets is greatly decrcased, therefore CPU time is reduced remarkably.

Abstract:The holistic theory is a useful approach for assessing the schedulability of hard real-time distributed systems. In this paper, an improvement on the holistic algorithm is proposed. Original holistic analysis has been extended to make it more generalized. Some real-time applications are also tested and analyzed based on research background of an hard real-time distributed information processing system. The experimental result illustrates that the worst-case response time of each task generated by new algorithm is more accurate and valid.

Abstract:In this paper, cloth is modeled as a collection of particles that conceptually represents the crossing points of wrap and weft threads in a plain weave. Based on this model, the deformation of cloth is decomposed into stretch and repel, bend, and shear. And energy functions of the three kind of deformation are deduced by physical rules. Finally, dynamic realistic cloth graphs are obtained by integrating D'Alembert-Lagrange equation.

Abstract:To overcome the imperfections of the Function Points (FP), the Extended Function Points (EFP) is presented, which complies with the FSM (functional size method), an international standard of ISO/IEC 14143. So EFP can be used to all kinds of software applications and has excellent practical operability.