Abstract:Since the first quantum programming language came about in 1996, many scientists and researchers are interested and involved in this field. After talking about several representative quantum programming languages, this paper gives an overview of the quantum programming language NDQJava designed by the authors, including design criteria, language paradigm, hardware platform, basic components and examples. Besides, the related works have also been mentioned.

Abstract:This paper describes one of the processing systems for the quantum programming language NDQJava. Its main feature lies that the classical parts of NDQJava programs are processed by the Java processing system, so this effort emphasizes on the processing of program's quantum parts. This processing system follows the compilation-interpretation approach, and it includes lexical analyzer, syntactic analyzer, code transformer, quantum assembler and quantum interpreter. By the end of this paper, some examples are given. The system was implemented by simulation in June 2006 on the classical computer.

Abstract:The abstract interpretation theory was proposed by P. Cousot and R. Cousot in 1977, and is widely used in the program’s static analysis domain to construct and approximate the program’s fixpoint semantics. This paper describes the abstract interpretation framework of the program semantics based on the Galois connection, and then discusses three typical applications of the abstract interpretation theory: The program transformation, the program verification techniques about the safety property and the program verification techniques about the liveness property. Finally, it points out the main directions of the program verification techniques based on the abstract interpretation theory.

Abstract:With the growing increase in software/hardware system scale and function, the further development and application of model checking has been greatly limited by state space explosion, which becomes the bottleneck of verifying large industrial designs. Predicate abstraction, as one of the most effective ways to address state explosion, has been fueled over the recent years. This paper presents a survey of the latest developments in predicate abstraction. A basic algorithm for predicate abstraction is introduced first, followed by comparison among several solvers. Emphases are put on counterexample-guided abstraction refinement and interpolation-based abstraction refinement, including the principles and improvements. The qualities of the new predicate generation methods are also analyzed. Finally, the major challenges in making this technology more pervasive in industrial design verification domain are noted.

Abstract:This paper presents a framework combining variable abstraction with bounded model checking, in order to prove the counterexamples' absence or establish the counterexamples' existence. A mathematical definition of variable minimal unsatisfiability (VMU) is introduced to drive this abstraction refinement process. The set of variables of VMU formula is a minimal one guaranteeing its unsatisfiability. Furthermore, the authors prove that VMU-driven refinement is valid and minimal by mathematical reasoning. Although the determining problem of VMU is as hard as the well-known problem called minimal unsatisfiability (MU), i.e. D^P-complete, the case study has shown that VMU could be more effective than MU in variable abstraction refinement process.

Abstract:The research actuality and new progress in clustering algorithm in recent years are summarized in this paper. First, the analysis and induction of some representative clustering algorithms have been made from several aspects, such as the ideas of algorithm, key technology, advantage and disadvantage. On the other hand, several typical clustering algorithms and known data sets are selected, simulation experiments are implemented from both sides of accuracy and running efficiency, and clustering condition of one algorithm with different data sets is analyzed by comparing with the same clustering of the data set under different algorithms. Finally, the research hotspot, difficulty, shortage of the data clustering and some pending problems are addressed by the integration of the aforementioned two aspects information. The above work can give a valuable reference for data clustering and data mining.

Abstract:A fundamental and difficult problem in cluster analysis is the determination of the "true" number of clusters in a dataset. The common trail-and-error method generally depends on certain clustering algorithms and is inefficient when processing large datasets. In this paper, a hierarchical method is proposed to get rid of repeatedly clustering on large datasets. The method firstly obtains the CF (clustering feature) via scanning the dataset and agglomerative generates the hierarchical partitions of dataset, then a curve of the clustering quality w.r.t the varying partitions is incrementally constructed. The partitions corresponding to the extremum of the curve is used to estimate the number of clusters finally. A new validity index is also presented to quantify the clustering quality, which is independent of clustering algorithm and emphasis on the geometric features of clusters, handling efficiently the noisy data and arbitrary shaped clusters. Experimental results on both real world and synthesis datasets demonstrate that the new method outperforms the recently published approaches, while the efficiency is significantly improved.

Abstract:Existing relational learning approaches usually work on complete relational data. However, in real-world applications, data are often incomplete. This paper proposes the MLTEC (maximum likelihood tree and evolutionary computing method) method to learn structures of the probabilistic relational models (PRMs) from incomplete relational data. The incomplete relational data are filled randomly at first, and a maximum likelihood tree (MLT) is generated from each completed data sample. This population of MLTs is then evolved through an evolutionary computing process, and the incomplete data are modified by using the best evolved structure in each generation. As a result, the probabilistic structure is learned. Experimental results show that the MLTEC method can learn good structures from incomplete relational data.

Abstract:One of the most important issues in Text Categorization (TC) is Feature Selection (FS). Many FS methods have been put forward and widely used in TC field, such as Information Gain (IG), Document Frequency (DF) thresholding, Mutual Information (MI) and so on. Empirical studies show that IG is one of the most effective methods, DF performs similarly, in contrast, and MI had relatively poor performance. One basic research question is why these FS methods cause different performance. Many existing work answers this question based on empirical studies. This paper presents a formal study of FS based on category resolve power. First, two desirable constraints that any reasonable FS function should satisfy are defined, then a universal method for developing FS functions is presented, and a new FS function KG using this method is developed. Analysis shows that IG and KG (knowledge gain) satisfy this universal method. Experiments on Reuters-21578 collection, NewsGroup collection and OHSUMED collection show that KG and IG get the best performance, even KG performs better than the IG method in two collections. These experiments imply that the universal method is very effective and gives a formal evaluation criterion for FS method.

Abstract:Recently, the QoS architecture in the beyond 3rd generation mobile communication system is becoming a hot topic in the area of computer networks and telecommunications. In this paper, the state-of-the-art QoS architectures are presented. By analyzing and comparing the key projects and papers published abroad, it is concluded that QoS architecture in B3G (beyond 3rd generation) system should be an all-IP, hierarchical and end-to-end framework. The main characteristics include scalability, controllable, self-adaptation and dynamic resource management. Finally, the design principals are proposed, and future works are summarized as well.

Abstract:Information brokerage in wireless sensor networks involves producers (such as sensor nodes) storing in storage positions a large amount of data that they have collected and consumers (e.g. base stations, users, and nodes) retrieving that information. In this paper, first, the data storage problem is formalized into a one-to-one (one producer and one consumer) model, a many-to-one (m producers and one consumer) model, and a many-to-many (m producers and n consumers) model with the goal of minimizing the total energy consum