Abstract:Pattern matching with gap constraints has important applications in many fields such as information retrieval, computational biology, and sequential pattern mining etc. This paper proposes a pattern matching problem named Strict Pattern Matching with General Gaps and Length Constraints (SPANGLO) which has four characteristics: It is strict exact pattern matching; Any position in the given sequence can be used more than once; The pattern can have more than one general gap constraint; Each matching substring has length constraints. An instance of SPANGLO can be transformed into an exponential number of matching instances with non-negative gaps in the worst case. In order to solve the problem effectively, an algorithm named SubnettreeSpanglo (SETS) is proposed based on Subnettree and its special concepts and properties. The correctness and completeness of the algorithm are given, and the space and time complexities of the algorithm are O(m×MaxLen×W) and O(MaxLen×W×m²×n) respectively, where n, m, MaxLen and W are the sequence length, the pattern length, the maximum length of the occurrence and the maximum gap of the pattern respectively. Experimental results validate the correctness of the transforming method of SPANGLO and the efficientiveness and correctness of SETS.

Abstract:First, the definition of quantum weakest liberal precondition (termed wlp) wlp (A,B,C)-commutativity is proposed, some necessary, and sufficient conditions of wlp (A,B,C)-commutativity are presented. Secondly, it has been shown that wlp is not a healthy predicate transformer: it is verified that wlp is a weaker predicate transformer than the quantum weakest precondition (termed wp). The essential differences of wlp and wp are disclosed. Finally, the properties for sequential composition, parallel composition and block structure of wlp are investigated.

Abstract:Component-Based software construction is a widely used approach in software development, to reduce the engineering effort and speed up the development cycle. Component-Based software systems consist of various components such as third-party components and in-house built components. Due to software changes, a component-based system is usually affected at both the component level and system level. Thus, a change impact analysis is needed to ensure the software quality and support maintenance. Existing research seldom addresses the issue of change impact analysis on component-based software, especially at a system level. This paper proposes a systematic approach to change impact analysis from the components to the system. Firstly, the change impact analysis models are proposed, and the change types are classified. Then, a change identification and an impact analysis are performed using a firewall approach based on the proposed models at both levels. The paper reports the case studies are based on a realistic component-based system. The study results show that the approach is feasible and effective.

Abstract:This paper aims at deriving software specification descriptions from elicited user requirements and domain descriptions. It provides an approach to transforming user requirements into software specifications in a smooth and logical way. Based on previous in-depth research on Problem Frames, the study adopts Hoare's Communicating Sequential Processes (CSP) and Lai's weakest-environment calculus to transform an entire problem diagram. The derived software specifications are abstract models resembling program code, whose correctness can be verified by the model checker FDR. This paper provides foundational work for embedded software development, i.e., deriving software code from requirements descriptions, automating document transformation and validation, etc. The theory presented in this paper, together with the FDR model checker tool, may help to improve the efficiency and accuracy in embedded software development.

Abstract:A commonly-used software fault localization technique mainly utilizes testing coverage information to calculate the suspiciousness of each program statement to find the faulty statement. However, this technique does not fully take dependences of the program into account; thus, its capacity for precisely locating faults is limited. This paper proposes a more effective hierarchical slicing spectrum-based software fault localization (HSS-SFL) technique for object-oriented programs. HSS-SFL first analyzes the dependence among the elements at different granularity levels including package level, class level, method level and statement level, and deletes some elements which are unrelated to the failed testing outputs. Next, the technique builds the hierarchical slicing spectrum model for these hierarchical slices obtained from the previous step, and further defines a suspiciousness method for each slice element. Finally, the faulty statement is located according to the suspiciousness results. Experimental results on real application programs show that HSS-SFL is more effective to locate the fault than program spectrum-based Tarantula technique, Union technique and Intersection technique.

Abstract:The reduction technique is an important analysis method for business process models. Existing informal reduction methods suffer from the infirm completeness because of their lack of formal fundamental. Also, Petri-net-based reduction methods available cannot guarantee the soundness due to their unspecific applications for process models. A sound and complete set of reduction rules is presented for free choice WF-nets. The soundness determines that the behavioral correctness of such a model is preserved during the reduction, and the completeness ensures that every such a correct WF-net can be finally reduced to its simplest form. Based on this, a sound and complete set of synthesis rules are given, which facilitates the design and refinement of process models.

Abstract:This paper introduces an Internet-based dynamic multi-document summarization system to support natural language processing and computational linguistics-related technical. This paper focuses on the description of the relevant content of dynamic multi-document summarization system framework and introduces dynamic evolutionary modeling using the matrix sub-space method, the information filtering model that uses the similarity and centroid integer selection method, and weighted sentence sorting, using the dynamic manifold method to generate the dynamic multi-document summarization system. This paper fuses the three innovation modeling methods to complement and to improve the performance of the system in accordance with the division of generated step of multi-document summarization. In a network environment, the framework ensures the dynamic evolutionary multi-document summarization with high novel information and evolutionary historical information.

Abstract:As a critical sub-task in discourse structure analysis, implicit discourse relation recognition (iDRR) is a challenging natural language processing task. Traditional approaches focus on exploring concepts and sense in discourse, which result in poor performance. This paper first systematically explores the efficiency of shallow semantic and attitude prosody-driven sentence-level sentiment information in discourse. Next, the paper proposes a simple but effective tree structure and finally investigates the efficiency of a composite kernel. Evaluation on Penn Discourse Treebank (PDTB) 2.0 shows the importance of shallow semantic and sentiment information across the discourse, and the appropriateness of the composite kernel in iDRR. It also shows that this system significantly outperforms other ones currently in the research field.

Abstract:In this paper, aiming to automatically distinguish subjective words from objective ones in Chinese, the study performs a subjectivity ranking test on Chinese adjectives and verbs. The paper exploits subjectivity clues and the subjectivity of Chinese characters. The subjectivity clues are further divided into gradability clues and subject clues. The study then uses graph-based algorithms to calculate the subjectivity originated from subjectivity clues. The subject clues and subjectivity of Chinese characters are novel ideas in such tasks. Five annotators are asked to label subjectivity of 500 words, from which the gold standard is built upon and evaluates rankings in various settings. It is shown that when words to be ranked occur frequently, this approach can outperform or match some human annotators. Furthermore, although the study only an unlabeled corpus, more prior knowledge can be incorporated into the graph-based approach.

Abstract:Open domain new word detection is vital for Chinese natural language processing research. This paper proposes a novel detection algorithm based condition random field (CRF), which treats the new word detection problem as a classification problem. In this algorithm, the study tries to separate boundaries of new words from existing words with both the CRF method and a serial of statistical features extracted from large scale corpus. The effectiveness of three different discretization strategies are also compared including K-means, equal-frequency, and information gain. Experimental results on a large-scale Web corpus named SogouT show the effectiveness of the proposed algorithms.

Abstract:With the development of automated planning, the size of problems is getting bigger and bigger, and one can predict that it will become very large in the future. Some existing research work begins to use secondary memories to extend the search space, and it is believed databases are finally used. Besides, many problems that belong to the same domain often have common constants, so there might be a plenty of reusable information to speed up the solution process. To store this information permanently, databases are also needed. Inspired by the above two reasons, this paper first proposes ER (entity relationship) models for PDDL (planning domain description languages) and then develops a stored procedure based automated planner (stored procedure planner, SPP) for the first time. This planner is an optimal one which runs totally inside a database. It stores and accesses data efficiently and takes fully advantages of database features. Experiments on benchmark problems from the Int'l planning competition (IPC) show that this planner can solve problems which cannot be solved by some classical optimal planners in a limited machine configuration. The work in this paper takes the first step for solving planning problems totally in a database so that it is helpful to solve huge-size problems finally.

Abstract:The control and data planes are decoupled in software-defined networking, which provide a new solution for research on new network applications and future Internet technologies. The development status of OpenFlow-based SDN technologies is surveyed in this paper. The research background of decoupled architecture of network control and data transmission in OpenFlow network is summarized first, and the key components and research progress including OpenFlow switch, controller, and SDN technologies are introduced. Moreover, current problems and solutions of OpenFlow-based SDN technologies are analyzed in four aspects. Combined with the development status in recent years, the applications used in campus, data center, network management and network security are summarized. Finally, future research trends are discussed.

Abstract:The features of mobile ad hoc network such as self-organization, mobility bring the convenience of network, but also increase the difficulty of routing management. To solve the limits of the existing reliable route protocol and its inefficient access to link information, according to DSR (dynamic source routing) protocol, a reliable routing protocol based on local trust system (TR-DSR) is proposed. TR-DSR completely considers and uses the reliability of each node and each link to find reliable routes. Moreover, the system also reduces overhead routing during this process. Meanwhile, to reduce the impact of selfish nodes to improve the correctness of the trust system, the DFR (decide forwarding recommendation) algorithm based on GTFT (generous tit for tat) strategy which motivates response to recommendation requests, is provided. Simulation results indicate that in more challenging situations of high mobility and selfish nodes, TR-DSR can improve the performance significantly and prove the reliability of TR-DSR.

Abstract:Stream cipher salsa20 is one of the seven finally victor algorithms of Estream stream cipher project. An algebraic truncated differential cryptanalysis of 5-round Salsa20 based on solving nonlinear equations and two higher differential characteristics for 3-round Salsa20 is shown, with the computational complexity of O(2¹⁰⁵), the date complexity of O(2¹¹), the space complexity of O(2¹¹). It also has a success rate of 97.72%, and holds the best result of analysis of 5-round Salsa20 by now.

Abstract:In model-driven approaches, user interface description languages (UIDL) often existed as the model and played an important role in the user interface development process. With the increase of the scale of software and the appearance novel devices and interaction techniques, user interface have changed greatly. Former UIDLs did not perform well in the support of new interaction paradigm. Because of this, the study proposes an extensible UIDL: E-UIDL. This UIDL follows several roles such as hierarchy and modularity. It can support the description of pen based user interfaces and multi-device user interfaces. This paper describes the features of E-UIDL in depth.

Abstract:In order to recover the linear spatial invariant blurred image blindly, a multi-regularization constraint-method for blind image resoration, which is based on the sparsity and the smoothing of the motion blur point spread function (MPSF), is proposed. First, according to the sparsity of the edges in the natural image, a weighted total variation norm (WTV-norm) is applied to the restoration image. Next, inspired from the characteristics of the MPSF, multi-regularization constraints that handle a wide variety of blurring degradations, it is applied to the blur kernel. Finally, a modified variable splitting (MVS) method is proposed to restore the image and simultaneously estimate exactly the blur function. A large number of experimental results indicate that the proposed method can also undo a wide variety of blurring degradations (e.g. motion blur, Gaussian blur, uniform blur, disk blur). In comparison with several recent representative image blind restoration methods, the subjective vision is not only more effective, but the ISNR also improved between 1.20dB and 4.22dB.

Abstract:Conventional locality preserving projection aims to minimize recognition error rate, implicitly assuming the losses of different misclassifications are the same. However, this may not hold in many real world face recognition applications. Face recognition is a multiclass cost sensitive and class imbalance task. For example, it will be troublesome if a gallery person is misclassified as an impostor, but it will be much more costly if an impostor is misclassified as a gallery person. Consequently, different kinds of mistakes will lead to different losses. Moreover, the examples of gallery person from any class are fewer than examples of the impostor, which is referred to as class imbalance. For that, this paper integrates the misclassification costs into an objective function of the locality preserving projection and proposes a cost sensitive locality preserving projection that minimizes the misclassification costs. Simultaneously, a weight strategy is used to balance the contribution of each class to the projection. Experimental results on AR, PIE, Extended Yale B datasets demonstrate the superiority of the proposed method.