Recent advancements in 3D Gaussian Splatting have achieved high-quality and real-time novel view synthesis for 3D scenes. However, this method primarily focuses on appearance and geometric modeling, lacks the ability to comprehend scenes with fine granularity at the object level. Some techniques enhance Gaussian Splatting, empowering it with the capability to perform unified 3D reconstruction and segmentation on real-world 3D scenes. Despite its improvements, these methods still face challenges in segmentation accuracy and reconstruction quality using 3D Gaussian representation. Additionally, the use of 16-bit identity codes to distinguish different Gaussian groups significantly increases memory overhead. To address these issues, we propose Identity-Encoding Half-Gaussian (ID-HGS) kernels. Our approach introduces a plane to split each Gaussian into two parts with distinct opacity values, enabling precise reconstruction of details and object boundaries. We replace the adaptive density control (ADC) used in Gaussian Grouping with localized half—gaussian point management (LHPM), which performs finer densification in under-reconstructed regions. LHPM resets pathological Gaussians and optimizes Gaussian density, reducing their impact on segmentation accuracy. Furthermore, we assign a global contribution score to each Gaussian and prune low-contribution Gaussians during training, saving memory and accelerating training. Compared to Gaussian Grouping, our method improves both reconstruction quality and segmentation accuracy while effectively controlling memory usage. Extensive experiments demonstrate that HGS-3D outperforms prior Gaussian Grouping on both reconstruction and segmentation: it achieves higher mask accuracy on the LERF-Localization benchmark and reduces peak memory usage while improving render quality on the mipnerf360 dataset.

Two analogous tasks have emerged in multimodal dialogue research: multimodal dialogue response generation and multimodal task-oriented dialogue. Both tasks share the goal of response multi-round, interactive content based on the multimodal dialogue history, but the latter focuses on accomplishing specific objectives which can be viewed as the former fine-tuned. The fine-tuning strategy may cause catastrophic forgetting and overfitting on few well-annotated data. Despite considerable progress in both areas, many existing works rely on retrieval-based approaches and additional auxiliary knowledge bases. To address these issues, we propose a Hierarchical Fusion Framework (HFF) for multimodal dialogue response generation. HFF blends these two tasks to learn a generation model from a data-driven perspective by introducing multi-dataset learning scheme, achieving a balance between generalization and expertise. In this work, multi-dataset learning is cast as a multi-objective optimization problem due to potential conflicts between datasets, necessitating a trade-off based on data distribution during training. Hierarchical fusion is performed sequentially between modalities and datasets, which could efficiently establish clear cross-modal relationships and integrate knowledge from multi-dataset. Specifically, HFF aligns extracted unimodal features (image and text) before fusing them through cross-modal attention and integrates them into multimodal encoder-decoder for generating responses. By optimizing the fusion between corpora from multi-dataset as conflicting objectives to satisfy Pareto optimality, our approach effectively facilitates both multimodal task-oriented and task-unoriented dialogues. Experimental results demonstrate the effectiveness of HFF and its comparable performance with all baselines.

In recent years, the transfer learning method of replacing acoustic features with phonetic features has become a new paradigm for end-to-end spoken language recognition. However, these larger transfer learning models always encode too much redundant information. In this paper, we propose a lightweight language recognition decoder based on a phonetic learnable dictionary encoding (PLDE) layer, which is more suitable for phonetic features and achieves better recognition performances while significantly reducing the number of parameters. The lightweight decoder consists of three main parts: (1) a phonetic learnable dictionary with ghost clusters, which improves the traditional LDE pooling layer and enhances the model’s ability to model noise with ghost clusters; (2) coarse-grained chunk-level pooling, which can highlight the phone sequence and suppress noise around ghost clusters, and hence reduce their influence to the subsequent network; (3) fine-grained chunk-level projection, which enables the discriminative network to obtain more linguistic information and hence improve the model’s modelling ability. These three parts simplify the language recognition decoder into a PLDE pooling layer, reducing the parameter size of the decoder by at least one order of magnitude while achieving better recognition performances. In experiments on the OLR2020 dataset, the C a v g of the proposed method exceeds that of the current state-of-the-art language recognition system, achieving 24.68% and 42.24% improvements on the cross-channel test set and unknown noise test set, respectively. Furthermore, experimental results on the OLR2021 dataset also demonstrate the effectiveness of PLDE.

Pointer analysis or points-to analysis (PTA) is a static program analysis for variables in a program, which determines a set of heap objects that individual variables may refer to at run time. In the literature, various types of context-sensitive analyses have been applied to improve the precision of PTA. In this article, we propose a framework that unifies existing context-sensitive PTA methods, under which we further explore more efficient ways for points-to calculation. In particular, we propose a call-graph-based context generation algorithm that combines the object-sensitive PTA and parameter-sensitive PTA approaches, and we implement the algorithm in the Soot compiler framework. Our new algorithm generates contexts for methods in a more complete and effective way, and it has been shown to achieve better precision with fewer generated contexts and less execution time than some of the known state-of-the-art context-sensitive approaches for PTA when tested with a selection of benchmarks from the DaCapo suite.

Thanks to Network Function Virtualization (NFV), Internet Service Providers (ISPs) can improve network resource utilization with significantly reduced capital and operational expenditures. To dig deeper into the potential of NFV, an important challenge is the resource allocation problem in NFV (NFV-RA), which can be divided into three stages: VNFs chain composition, VNF forwarding graph embedding, and VNFs scheduling. The key to the NFV-RA problem is to design an effective and coordinated resource allocation algorithm for the three stages. Besides, the NFV-RA problem has been proved to be NP-Hard, and thus most existing approaches focus on heuristic and meta-heuristic algorithms. In this paper, we propose an NFV online coordinated resource allocation framework (OCRA) that completes the three stages simultaneously in a coordinated manner by combining parallel Multi-Agent Deep Reinforcement Learning with novel neural networks and RL training techniques. The extensive experimental results show that compared with the state-of-the-art solutions, OCRA is highly-efficient in terms of time, with up to 50% and 10.8% improvement on resource overhead and acceptance ratio, respectively.

Similarity representation plays a central role in increasingly popular anomaly detection techniques, which have been successfully applied in various realistic scenes. Until now, many low-rank representation techniques have been introduced to measure the similarity relations of data; yet, they only concern to minimize reconstruction errors, without involving the structural information of data. Besides, the traditional low-rank representation methods often take nuclear norm as their low-rank constraints, easily yielding a suboptimal solution. To address the problems above, in this article, we propose a novel anomaly detection method, which exploits kernel preserving embedding, as well as the double nuclear norm, to explore the similarity relations of data. Based on the similarity relations, a kind of probability transition matrix is derived, and a tailored random walk is further adopted to reveal anomalies. The proposed method can not only preserve the manifold structural properties of the data, but also alleviate the suboptimal problem. To validate the superiority of our method, extensive experiments with eight popular anomaly detection algorithms were conducted on 12 widely used datasets. The experimental results show that our detection method outperformed the state-of-the-art anomaly detection algorithms in most cases.

Abstract Dropout has been proven to be an effective technique for regularizing and preventing the co-adaptation of neurons in deep neural networks (DNN). It randomly drops units with a probability of p during the training stage of DNN to avoid overfitting. The working mechanism of dropout can be interpreted as approximately and exponentially combining many different neural network architectures efficiently, leading to a powerful ensemble. In this work, we propose a novel diversification strategy for dropout, which aims at generating more different neural network architectures in less numbers of iterations. The dropped units in the last forward propagation will be marked. Then the selected units for dropping in the current forward propagation will be retained if they have been marked in the last forward propagation, i.e., we only mark the units from the last forward propagation. We call this new regularization scheme Tabu dropout, whose significance lies in that it does not have extra parameters compared with the standard dropout strategy and is computationally efficient as well. Experiments conducted on four public datasets show that Tabu dropout improves the performance of the standard dropout, yielding better generalization capability.

The task of single‐channel speech enhancement is to restore clean speech from noisy speech. Recently, speech enhancement has been greatly improved with the introduction of deep learning. Previous work proved that using ideal ratio mask or phase‐sensitive mask as intermediation to recover clean speech can yield better performance. In this case, the mean square error is usually selected as the loss function. However, after conducting experiments, the authors find that the mean square error has a problem. It considers absolute error values, meaning that the gradients of the network depend on absolute differences between estimated values and true values, so the points in magnitude spectra with smaller values contribute little to the gradients. To solve this problem, they propose relative loss, which pays more attention to relative differences between magnitude spectra, rather than the absolute differences, and is more in accordance with human sensory characteristics. The perceptual evaluation of speech quality, the short‐time objective intelligibility, the signal‐to‐distortion ratio, and the segmental signal‐to‐noise ratio are used to evaluate the performance of the relative loss. Experimental results show that it can greatly improve speech enhancement by focusing on smaller values.

In the context of Automatic Speech Recognition (ASR), improving the noise robustness remains an intractable task. Speech enhancement, combined with Generative Adversarial Networks (GAN), such as SEGAN, has effective performance in denoising raw waveform speech signals. Instead of waveforms, using Mel filterbank spectra in GAN is proposed, which has better performance in the task of ASR. However, these techniques will still miss useful information when GAN is used in them. In this paper, we investigate to protect the useful information in GAN, and propose a novel model, called Discriminator Generator Classifier-GAN (DGC-GAN). While normal GAN combining just two networks will lead the model to denoising rather than recognition, DGC-GAN has another network called classifier, which is an ASR system that will tune GAN to be recognized easier. By adding a classifier into previous GAN to get DGC-GAN, we achieve 29.1% Phone Error Rate (PER) relative improvement in a tiny dataset and 47.4% PER relative improvement in a large dataset.

We present a new two-stage fine-grained air Particulate Matter (PM) prediction system using a variety of deep memory networks. Our model is significantly simpler than traditional weather report systems, which rely heavily on the atmospheric reaction equations and pollutant emissions inventories. Pollutant inventories are notoriously difficult to obtain and are often packed with declination for multiple reasons, while reaction equations are impossible to exhaust. These traditional models also tend to perform poorly when affected by strong convective weather. In contrast, our model does not need precise hand collected inventories of pollution sources. It can utilize the potential of Deep-Neural-Networks (DNN) to reveal the relationship among different locations and even find relations between known social events and air quality. Both potentially provide a valid path to air pollution control. The key to our approach is a well-tuned sophisticated attention based network that uses multiple GPUs, allowing us to transform a traditional sparse prediction problem into a sequence-to-sequence learning problem and train it end-to-end. By evaluating the model on over 1,625 instances of data of Northern China collected by our team, we show that it is not only computationally efficient but also accurately feasible compared with other optional models.

An unrealistic assumption in classical extensive game theory is that the complete game tree is fully perceivable by all players. To weaken this assumption, a class of games (called games with short sight) was proposed in literature, modelling the game scenarios where players have only limited fores ight of the game tree due to bounded resources and limited computational ability. As a consequence, the notions of equilibria in classical game theory were refined to fit games with short sight. A crucial issue that thus arises is to determine whether a strategy profile is a solution to a game. To study this issue and address the underlying idea and theory on players’ decisions in such games, we adopt a logical way. Specifically, we develop a logic called DLS through which features of these games are demonstrated. More importantly, it enables us to characterize the solutions to these games via formulas of this logic. Moreover, we study the algorithm for model checking DLS, which is shown to be PTIME-complete in the size of the model. This work not only provides an insight into a more realistic model in game theory, but also enriches the possible applications of logic.

Dynamic Epistemic Logic (DEL) can model complex information scenarios in a way that appeals to logicians. However, existing DEL implementations are ad-hoc, so we do not know how the framework really performs. For this purpose, we want to hook up with the best available model checking and SAT techniques in computational logic. We do this by first providing a bridge: a new faithful representation of DEL models as so-called knowledge structures that allow for symbolic model checking. For more complex epistemic change we introduce knowledge transformers analogous to action models. Next, we show that we can now solve well-known benchmark problems in epistemic scenarios much faster than with existing methods for DEL. We also compare our approach to model checking for temporal logics. Finally, we show that our method is not just a matter of implementation, but that it raises significant issues about logical representation and update.

In this paper, we develop a local search algorithm to solve the Maximum Weight Clique (MWC) problem. Firstly we design a novel scoring function to measure the benefits of a local move. Then we develop a Cycle Estimation based ReStart (CERS) strategy to resolve the cycling issue in the local search process. Experimental results show that our solver achieves state-of-the-art performances on the large sparse graphs as well as large dense graphs. Also we present a theorem which shows the necessity of the restart strategies in current state-of-the-art local search algorithms.

The Maximum Vertex Weight Clique (MVWC) problem is NP-hard and also important in real-world applications. In this paper we propose to use the restart and the random walk strategies to improve local search for MVWC. If a solution is revisited in some particular situation, the search will restart. In addition, when the local search has no other options except dropping vertices, it will use random walk. Experimental results show that our solver outperforms state-of-the-art solvers in DIMACS and finds a new best-known solution. Also it is the unique solver which is comparable with state-of-the-art methods on both BHOSLIB and large crafted graphs. Furthermore we evaluated our solver in clustering aggregation. Experimental results on a number of real data sets demonstrate that our solver outperforms the state-of-the-art for solving the derived MVWC problem and helps improve the final clustering results.

The graph coloring problem (GCP) is one of the most studied NP hard problems and has numerous applications. Despite the practical importance of GCP, there are limited works in solving GCP for very large graphs. This paper explores techniques for solving GCP on very large real world graphs.We first propose a reduction rule for GCP, which is based on a novel concept called degree bounded independent set.The rule is iteratively executed by interleaving between lower bound computation and graph reduction. Based on this rule, we develop a novel method called FastColor, which also exploits fast clique and coloring heuristics. We carry out experiments to compare our method FastColor with two best algorithms for coloring large graphs we could find. Experiments on a broad range of real world large graphs show the superiority of our method. Additionally, our method maintains both upper bound and lower bound on the optimal solution, and thus it proves an optimal solution when the upper bound meets the lower bound. In our experiments, it proves the optimal solution for 97 out of 142 instances.

Weighted partial maximum satisfiability (WPMS) is a significant generalization of maximum satisfiability (MAX-SAT), with many important applications. Recently, breakthroughs have been made on stochastic local search (SLS) for weighted MAX-SAT and (unweighted) partial MAX-SAT (PMS). However, the performance of SLS for WPMS lags far behind. In this work, we present a new SLS algorithm named CCEHC for WPMS. CCEHC is mainly based on a heuristic emphasizing hard clauses, which has three components: a variable selection mechanism focusing on configuration checking based only on hard clauses, a weighting scheme for hard clauses, and a biased random walk component. Experiments show that CCEHC significantly outperforms its state-of-the-art SLS competitors. Experiments comparing CCEHC with a state-of-the-art complete solver indicate the effectiveness of CCEHC on a number of application WPMS instances.

Symbolic reasoning is difficult for neural networks. Especially, reasoning with variables can be a challenging task for them. In this paper, a symbolic reasoning method based on deep neural networks is proposed, and this method is applied to axiom discovery. This method makes use of the concept of “symbolic manipulation”. Specifically, it relies on the learning ability of the deep neural networks and the reasoning ability of a logical system: The logical system generates training examples, which indicate how to manipulate symbols, from given data, and then the deep neural networks try to learn these examples, score them and abstract possible axioms from them. In particular, this method enables the deep neural networks to realise simple reasoning with variables in predicate logic. In experiments, we demonstrate that the deep neural networks are able to learn to copy and generate symbols from a certain form of rules produced by the logical system. Moreover, we find that the more hidden layers usually mean the stronger learning ability of symbolic manipulation: An increasing number of hidden layers usually bring about a higher rule acceptance rate. Also, we find that the more hidden layers can bring about better results on axiom discovery tasks, and we show that the deep neural networks can discover some useful axioms in mathematics.

Recently, bottleneck features as effective representations have been successfully used in Speaker Recognition (SR) and Language Recognition (LR), but little work has focused on bottleneck features for Bird Species Verification (BSV). In SR, LR and BSR tasks, using short-time spectra features may be insufficient, so it need some more abstract and discriminative representations as complementation to conventional spectra features. Some SR and LR work shows that bottleneck features can form a low-dimension representation of the original inputs with a powerful descriptive and discriminative capability. Due to the general audio representation principles of speakers, language and birds being similar, we propose a hypothesis: the bottleneck features are also useful for BSV. Therefore, in this paper, we use the bottleneck feature framework based on the standard i-vector framework to deal with crucial problems in conventional methods of BSV, such as the session variability and insufficient features. Moreover, we make no distinction between bird calls and bird songs in the evaluation phase. Experimental results show that the standard i-vector system and the bottleneck feature system gain 3.39% and 0.85% Equal Error Rate (EER) respectively. The bottleneck feature system obtains 75% relative improvement over the standard i-vector system, meaning that the bottleneck features as a complementation to spectra features are significantly useful for BSV. The deep feature system, which is an another state-of-the-art framework based on deep features used in SR, however, only results in 18.64% EER, which is much worse than the other two systems, and a brief explanation is provided in this paper.

The problem of finding a minimum vertex cover (MinVC) in a graph is a prominent NP-hard problem of great importance in both theory and application. During recent decades, there has been much interest in finding optimal or near-optimal solutions to this problem. Many existing heuristic algorithms for MinVC are based on local search strategies. Recently, an algorithm called FastVC takes a first step towards solving the MinVC problem for large real-world graphs. However, FastVC may be trapped by local minima during the local search stage due to the lack of suitable diversification mechanisms. In this work, we design a new random walk strategy to help FastVC escape from local minima. Experiments conducted on a broad range of large real-world graphs show that our algorithm outperforms state-of-the-art algorithms on most classes of the benchmark and finds smaller vertex covers on a considerable portion of the graphs.

Abstract Writing in language tests is regarded as an important indicator for assessing language skills of test takers. As Chinese language tests become popular, scoring a large number of essays becomes a heavy and expensive task for the organizers of these tests. In the past several years, some efforts have been made to develop automated simplified Chinese essay scoring systems, reducing both costs and evaluation time. In this paper, we introduce a system called SCESS (automated Simplified Chinese Essay Scoring System) based on Weighted Finite State Automata (WFSA) and using Incremental Latent Semantic Analysis (ILSA) to deal with a large number of essays. First, SCESS uses ann-gram language model to construct a WFSA to perform text pre-processing. At this stage, the system integrates a Confusing-Character Table, a Part-Of-Speech Table, beam search and heuristic search to perform automated word segmentation and correction of essays. Experimental results show that this pre-processing procedure is effective, with a Recall Rate of 88.50%, a Detection Precision of 92.31% and a Correction Precision of 88.46%. After text pre-processing, SCESS uses ILSA to perform automated essay scoring. We have carried out experiments to compare the ILSA method with the traditional LSA method on the corpora of essays from the MHK test (the Chinese proficiency test for minorities). Experimental results indicate that ILSA has a significant advantage over LSA, in terms of both running time and memory usage. Furthermore, experimental results also show that SCESS is quite effective with a scoring performance of 89.50%.

Minimum Vertex Cover (MinVC) is a well known NP-hard combinatorial optimization problem, and local search has been shown to be one of the most effective approaches to this problem. State-of-the-art MinVC local search algorithms employ edge weighting techniques and prefer to select vertices with higher weighted score. These algorithms are not robust and especially have poor performance on instances with structures which defeat greedy heuristics. In this paper, we propose a vertex weighting scheme to address this shortcoming, and combine it within the current best MinVC local search algorithm NuMVC, leading to a new algorithm called TwMVC. Our experiments show that TwMVC outperforms NuMVC on the standard benchmarks namely DIMACS and BHOSLIB. To the best of our knowledge, TwMVC is the first MinVC algorithm that attains the best known solution for all instances in both benchmarks. Further, TwMVC shows superiority on a benchmark of real-world networks.

In this paper, we propose Multi-state Activation Functions (MSAFs) for Deep Neural Networks (DNNs). These multi-state functions do extra classification based on the 2-state Logistic function. Discussions on the MSAFs reveal that these activation functions have potentials for altering the parameter distribution of the DNN models, improving model performances and reducing model sizes. Meanwhile, an extension of the XOR problem indicates how neural networks with the multistate functions facilitate classifying patterns. Furthermore, basing on running average mean-normalisation rules, we actualise a combination of mean-normalised optimisation with the MSAFs as well as Singular Value Decomposition (SVD). Experimental results on TIMIT reveal that acoustic models based on DNNs can be improved by applying the MSAFs. The models obtain better phone error rates when the Logistic function is replaced with the multi-state functions. Further experiments on large vocabulary continuous speech recognition tasks reveal that the MSAFs and mean-normalised Stochastic Gradient Descent (MN-SGD) bring better recognition performances for DNNs in comparison with the conventional Logistic function and SGD learning method. Beyond this, the combination of the MSAFs, the SVD method and MN-SGD shrinks the parameter scales of DNNs to 44% approximately, leading to considerable increasing on decoding speed and decreasing on model sizes without any loss of recognition performances.

Traditional automatic speech recognition (ASR) systems usually get a sharp performance drop when noise presents in speech. To make a robust ASR, we introduce a new model using the multi-task learning deep neural networks (MTL-DNN) to solve the speech denoising task in feature level. In this model, the networks are initialized by pre-training restricted Boltzmann machines (RBM) and fine-tuned by jointly learning multiple interactive tasks using a shared representation. In multi-task learning, we choose a noisy-clean speech pair fitting task as the primary task and separately explore two constraints as the secondary tasks: phone label and phone cluster. In experiments, the denoised speech is reconstructed by the MTL-DNN using the noisy speech as input and it is respectively evaluated by the DNN-hidden Markov model (HMM) based and the Gaussian Mixture Model (GMM)-HMM based ASR systems. Results show that, using the denoised speech, the word error rate (WER) is respectively reduced by 53.14% and 34.84% compared with baselines. The MTL-DNN model also outperforms the general single-task learning deep neural networks (STL-DNN) model with a performance improvement of 4.93% and 3.88% respectively.

Covering arrays (CAs) are often used as test suites for combinatorial interaction testing to discover interaction faults of real-world systems. Most real-world systems involve constraints, so improving algorithms for covering array generation (CAG) with constraints is beneficial. Two popular methods for constrained CAG are greedy construction and meta-heuristic search. Recently, a meta-heuristic framework called two-mode local search has shown great success in solving classic NPhard problems. We are interested whether this method is also powerful in solving the constrained CAG problem. This work proposes a two-mode meta-heuristic framework for constrained CAG efficiently and presents a new meta-heuristic algorithm called TCA. Experiments show that TCA significantly outperforms state-of-the-art solvers on 3-way constrained CAG. Further experiments demonstrate that TCA also performs much better than its competitors on 2-way constrained CAG.

Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of random instances of the Boolean satisfiability (SAT) problem. One of the most famous SLS algorithms for SAT is WalkSAT, which is an initial algorithm that has wide influence and performs very well on random 3-SAT instances. However, the performance of WalkSAT on random k-SAT instances with k > 3 lags far behind. Indeed, there are limited works on improving SLS algorithms for such instances. This work takes a good step toward this direction. We propose a novel concept namely multilevel make. Based on this concept, we design a scoring function called linear make, which is utilized to break ties in WalkSAT, leading to a new algorithm called WalkSATlm. Our experimental results show that WalkSATlm improves WalkSAT by orders of magnitude on random k-SAT instances with k > 3 near the phase transition. Additionally, we propose an efficient implementation for WalkSATlm, which leads to a speedup of 100%. We also give some insights on different forms of linear make functions, and show the limitation of the linear make function on random 3-SAT through theoretical analysis.

The maximum satisfiability (MAX-SAT) problem, especially the weighted version, has extensive applications. Weighted MAX-SAT instances encoded from real-world applications may be very large, which calls for efficient approximate methods, mainly stochastic local search (SLS) ones. However, few works exist on SLS algorithms for weighted MAX-SAT. In this paper, we propose a new heuristic called CCM for weighted MAX-SAT. The CCM heuristic prefers to select a CCMP variable. By combining CCM with random walk, we design a simple SLS algorithm dubbed CCLS for weighted MAX-SAT. The CCLS algorithm is evaluated against a state-of-the-art SLS solver IRoTS and two state-of-the-art complete solvers namely akmaxsat_ls and New WPM2, on a broad range of weighted MAX-SAT instances. Experimental results illustrate that the quality of solution found by CCLS is much better than that found by IRoTS, akmaxsat_ls and New WPM2 on most industrial, crafted and random instances, indicating the efficiency and the robustness of the CCLS algorithm. Furthermore, CCLS is evaluated in the weighted and unweighted MAX-SAT tracks of incomplete solvers in the Eighth Max-SAT Evaluation (Max-SAT 2013), and wins four tracks in this evaluation, illustrating that the performance of CCLS exceeds the current state-of-the-art performance of SLS algorithms on solving MAX-SAT instances.

Two-mode stochastic local search (SLS) and focused random walk (FRW) are the two most influential paradigms of SLS algorithms for the propositional satisfiability (SAT) problem. Recently, an interesting idea called configuration checking (CC) was proposed to handle the cycling problem in SLS. The CC idea has been successfully used to improve SLS algorithms for SAT, resulting in state-of-the-art solvers. Previous CC strategies for SAT are based on neighboring variables, and prove successful in two-mode SLS algorithms. However, this kind of neighboring variables based CC strategy is not suitable for improving FRW algorithms. In this paper, we propose a new CC strategy which is based on clause states. We apply this clause states based CC (CSCC) strategy to both two-mode SLS and FRW paradigms. Our experiments show that the CSCC strategy is effective on both paradigms. Furthermore, our developed FRW algorithms based on CSCC achieve state-of-the-art performance on a broad range of random SAT benchmarks.

Existing algorithms for I/O Linear Temporal Logic (LTL) model checking usually output a single counterexample for a system which violates the property. However, in real-world applications, such as diagnosis and debugging in software and hardware system designs, people often need to have a set of counterexamples or even all counterexamples. For this purpose, we propose an I/O efficient approach for detecting all accepting cycles, called Detecting All Accepting Cycles (DAAC), where the properties to be verified are in LTL. Different from other algorithms for finding all cycles, DAAC first searches for the accepting strongly connected components (ASCCs), and then finds all accepting cycles of every ASCC, which can avoid searching for a great many paths that are impossible to be extended to accepting cycles. In order to further lower DAAC's I/O complexity and improve its performance, we propose an intersection computation technique and a dynamic path management technique, and exploit a minimal perfect hash function (MPHF). We carry out both complexity and experimental comparisons with the state-of-the-art algorithms including Detect Accepting Cycle (DAC), Maximal Accepting Predecessors (MAP) and Iterative-Deepening Depth-First Search (IDDFS). The comparative results show that our approach is better on the whole in terms of I/O complexity and practical performance, despite the fact that it finds all counterexamples.

Model checking is a powerful approach for the formal verification of hardware and software systems. However, this approach suffers from the state space explosion problem, which limits its application to large-scale systems due to space shortage. To overcome this drawback, one of the most effective solutions is to use external memory algorithms. In this paper, we propose an I/O efficient model checking algorithm for large-scale systems. To lower I/O complexity and improve time efficiency, we combine three new techniques: 1) a linear hash-sorting technique; 2) a cached duplicate detection technique; and 3) a dynamic path management technique. We show that the new algorithm has a lower I/O complexity than state-of-the-art I/O efficient model checking algorithms, including detect accepting cycle, maximal accepting predecessors, and iterative-deepening depth-first search. In addition, the experiments show that our algorithm obviously outperforms these three algorithms on the selected representative benchmarks in terms of performance.

Partial MaxSAT (PMS) is a generalization to SAT and MaxSAT. Many real world problems can be encoded into PMS in a more natural and compact way than SAT and MaxSAT. In this paper, we propose new ideas for local search for PMS, which mainly rely on the distinction between hard and soft clauses. We use these ideas to develop a local search PMS algorithm called {\it Dist}. Experimental results on PMS benchmarks from MaxSAT Evaluation 2013 show that {\it Dist} significantly outperforms state-of-the-art PMS algorithms, including both local search algorithms and complete ones, on random and crafted benchmarks. For the industrial benchmark, {\it Dist} dramatically outperforms previous local search algorithms and is comparable with complete algorithms.

Stochastic local search (SLS) algorithms have shown effectiveness on satisfiable instances of the Boolean satisfiability (SAT) problem. However, their performance is still unsatisfactory on random k-SAT at the phase transition, which is of significance and is one of the empirically hardest distributions of SAT instances. In this paper, we propose a new heuristic called DCCA, which combines two configuration checking (CC) strategies with different definitions of configuration in a novel way. We use the DCCA heuristic to design an efficient SLS solver for SAT dubbed DCCASat. The experiments show that the DCCASat solver significantly outperforms a number of state-of-the-art solvers on extensive random k-SAT benchmarks at the phase transition. Moreover, DCCASat shows good performance on structured benchmarks, and a combination of DCCASat with a complete solver achieves state-of-the-art performance on structured benchmarks.

Finding out an effective way to score Chinese written essays automatically remains challenging for researchers. Several methods have been proposed and developed but limited in the character and word usage levels. As one of the scoring standards, however, content or topic perspective is also an important and necessary indicator to assess an essay. Therefore, in this paper, we propose a novel perspective -- topic, and a new method integrating topic modeling strategy called Regularized Latent Semantic Indexing to recognize the latent topics and Support Vector Machines to train the scoring model. Experimental results show that automated Chinese essay scoring from topic perspective is effective which can improve the rating agreement to 89%.

It is widely acknowledged that stochastic local search (SLS) algorithms can efficiently find models for satisfiable instances of the satisfiability (SAT) problem, especially for random k-SAT instances. However, compared to random 3-SAT instances where SLS algorithms have shown great success, random k-SAT instances with long clauses remain very difficult. Recently, the notion of second level score, denoted as "score_2", was proposed for improving SLS algorithms on long-clause SAT instances, and was first used in the powerful CCASat solver as a tie breaker. In this paper, we propose three new scoring functions based on score_2. Despite their simplicity, these functions are very effective for solving random k-SAT with long clauses. The first function combines score and score_2, and the second one additionally integrates the diversification property "age". These two functions are used in developing a new SLS algorithm called CScoreSAT. Experimental results on large random 5-SAT and 7-SAT instances near phase transition show that CScoreSAT significantly outperforms previous SLS solvers. However, CScoreSAT cannot rival its competitors on random k-SAT instances at phase transition. We improve CScoreSAT for such instances by another scoring function which combines score_2 with age. The resulting algorithm HScoreSAT exhibits state-of-the-art performance on random k-SAT (k>3) instances at phase transition. We also study the computation of score_2, including its implementation and computational complexity.

Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of random instances of the Boolean satisfiablity (SAT) problem. One of the most famous SLS algorithms for SAT is WalkSAT, which is an initial algorithm that has wide influence among modern SLS algorithms. Recently, there has been increasing interest in WalkSAT, due to the discovery of its great power on large random 3-SAT instances. However, the performance of WalkSAT on random $k$-SAT instances with $k>3$ lags far behind. Indeed, there have been few works in improving SLS algorithms for such instances. This work takes a large step towards this direction. We propose a novel concept namely $multilevel$ $make$. Based on this concept, we design a scoring function called $linear$ $make$, which is utilized to break ties in WalkSAT, leading to a new algorithm called WalkSAT$lm$. Our experimental results on random 5-SAT and 7-SAT instances show that WalkSAT$lm$ improves WalkSAT by orders of magnitudes. Moreover, WalkSAT$lm$ significantly outperforms state-of-the-art SLS solvers on random 5-SAT instances, while competes well on random 7-SAT ones. Additionally, WalkSAT$lm$ performs very well on random instances from SAT Challenge 2012, indicating its robustness.

Chinese text error detection and correction is widely applicable, but the methods so far are not robust enough for industrial use. In this paper, a new method is proposed based on Tri-gram modeled-Weighted Finite-State Transducer (WFST). By integrating confusing-character table, beam search and A* search, we evaluate the performance on real test essays. Various experiments have been conducted to prove that the proposed method is effective with the recall rate of 85.68%, the detection accuracy of 91.22% and the correction accuracy of 87.30%.

This paper presents and analyzes two new efficient local search strategies for the Boolean Satisfiability (SAT) problem. We start by proposing a local search strategy called configuration checking (CC) for SAT. The CC strategy results in a simple local search algorithm for SAT called Swcc, which shows promising experimental results on random 3-SAT instances, and outperforms TNM, the winner of SAT Competition 2009. However, the CC strategy for SAT is still in a nascent stage, and Swcc cannot yet compete with Sparrow2011, which won SAT Competition 2011 just after Swcc had been designed. The CC strategy seems too strict in that it forbids flipping those variables even with great scores, if they do not satisfy the CC criterion. We improve the CC strategy by adopting an aspiration mechanism, and get a new variable selection heuristic called configuration checking with aspiration (CCA). The CCA heuristic leads to an improved algorithm called Swcca, which exhibits state-of-the-art performance on random 3-SAT instances and crafted ones. The third contribution concerns improving local search algorithms for random k-SAT instances with k>3. Although the SAT community has made great achievements in solving random 3-SAT instances, the progress lags far behind on random k-SAT instances with k>3. This work proposes a new variable property called subscore, which is utilized to break ties in the CCA heuristic when candidate variables for flipping have the same score. The resulting algorithm CCAsubscore is very efficient for solving random k-SAT instances with k>3, and significantly outperforms other state-of-the-art ones. Combining Swcca and CCAsubscore, we obtain a local search SAT solver called CCASat, which was ranked first in the random track of SAT Challenge 2012. Additionally, we perform theoretical analyses on the CC strategy and the subscore property, and show interesting results on these two heuristics. Particularly, our analysis indicates that the CC strategy is more effective for k-SAT with smaller k, while the subscore notion is not suitable for solving random 3-SAT.

The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem of great importance in both theory and application. Local search has proved successful for this problem. However, there are two main drawbacks in state-of-the-art MVC local search algorithms. First, they select a pair of vertices to exchange simultaneously, which is time-consuming. Secondly, although using edge weighting techniques to diversify the search, these algorithms lack mechanisms for decreasing the weights. To address these issues, we propose two new strategies: two-stage exchange and edge weighting with forgetting. The two-stage exchange strategy selects two vertices to exchange separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. These two strategies are used in designing a new MVC local search algorithm, which is referred to as NuMVC. We conduct extensive experimental studies on the standard benchmarks, namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art heuristic algorithms show that NuMVC is at least competitive with the nearest competitor namely PLS on the DIMACS benchmark, and clearly dominates all competitors on the BHOSLIB benchmark. Also, experimental results indicate that NuMVC finds an optimal solution much faster than the current best exact algorithm for Maximum Clique on random instances as well as some structured ones. Moreover, we study the effectiveness of the two strategies and the run-time behaviour through experimental analysis.

An interesting strategy called configuration checking (CC) was recently proposed to handle the cycling problem in local search for Minimum Vertex Cover. A natural question is whether this CC strategy also works for SAT. The direct application of CC did not result in stochastic local search (SLS) algorithms that can compete with the current best SLS algorithms for SAT. In this paper, we propose a new heuristic based on CC for SLS algorithms for SAT, which is called configuration checking with aspiration (CCA). It is used to develop a new SLS algorithm called Swcca. The experiments on random 3-SAT instances show that Swcca significantly outperforms Sparrow2011, the winner of the random satisfiable category of the SAT Competition 2011, which is considered to be the best local search solver for random 3-SAT instances. Moreover, the experiments on structured instances show that Swcca is competitive with Sattime, the best local search solver for the crafted benchmark in the SAT Competition 2011.

In this paper, we propose two new strategies to design efficient local search algorithms for the minimum vertex cover (MVC) problem. There are two main drawbacks in state-of-the-art MVC local search algorithms: First, they select a pair of vertices to be exchanged simultaneously, which is time consuming; Second, although they use edge weighting techniques, they do not have a strategy to decrease the weights. To address these drawbacks, we propose two new strategies: two stage exchange and edge weighting with forgetting. The two stage exchange strategy selects two vertices to be exchanged separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. We utilize these two strategies to design a new algorithm dubbed NuMVC. The experimental results show that NuMVC significantly outperforms existing state-of-the-art heuristic algorithms on most of the hard DIMACS instances and all instances in the hard random BHOSLIB benchmark.

A probabilistic variant of ATL* logic is proposed to work with multi-player games of incomplete information and synchronous perfect recall. The semantics of the logic is settled over probabilistic interpreted system and partially observed probabilistic concurrent game structure. While unexpectedly, the model checking problem is in general undecidable even for single-group fragment, we find a fragment whose complexity is in 2-EXPTIME. The usefulness of this fragment is shown over a land search scenario.

As a data structure for representing and manipulating Boolean functions, BDDs (Binary Decision Diagrams) are commonly used in many fields such as model-checking, system verification and so on. For saving space and improving operation speed, all the existing packages limit the number of variables to 216. However, such a limitation also restrains its applicability. In this paper, we present TiniBDD, an efficient implementation of a 232BDD package incorporating sub-allocation of memory and lightweight Garbage Collection as well as a new operator named as Satisfiable Assignment Operator. Compared with the well-known CUDD which is one of the best 216BDD packages that can be attained publicly, the experiments show TiniBDD has comparable performance.

Local Search is an appealing method for solving the Boolean Satisfiability problem (SAT). However, this method suffers from the cycling problem which severely limits its power. Recently, a new strategy called configuration checking (CC) was proposed, for handling the cycling problem in local search. The CC strategy was used to improve a state-of the-art local search algorithm for Minimum Vertex Cover. In this paper, we propose a novel local search strategy for the satisfiability problem, i.e., the CC strategy for SAT. The CC strategy for SAT takes into account the circumstances of the variables when selecting a variable to flip, where the circumstance of a variable refers to truth values of all its neighboring variables. We then apply it to design a local search algorithm for SAT called SWcc (Smoothed Weighting with Configuration Checking). Experimental results show that the CC strategy for SAT is more efficient than the previous strategy for handling the cycling problem called tabu. Moreover, SWcc significantly outperforms the best local search SAT solver in SAT Competition 2009 called TNM on large random 3-SAT instances.

The Minimum Vertex Cover (MVC) problem is a well-known combinatorial optimization problem of great importance in theory and applications. In recent years, local search has been shown to be an effective and promising approach to solve hard problems, such as MVC. In this paper, we introduce two new local search algorithms for MVC, called EWLS (Edge Weighting Local Search) and EWCC (Edge Weighting Configuration Checking). The first algorithm EWLS is an iterated local search algorithm that works with a partial vertex cover, and utilizes an edge weighting scheme which updates edge weights when getting stuck in local optima. Nevertheless, EWLS has an instance-dependent parameter. Further, we propose a strategy called Configuration Checking for handling the cycling problem in local search. This is used in designing a more efficient algorithm that has no instance-dependent parameters, which is referred to as EWCC. Unlike previous vertex-based heuristics, the configuration checking strategy considers the induced subgraph configurations when selecting a vertex to add into the current candidate solution. A detailed experimental study is carried out using the well-known DIMACS and BHOSLIB benchmarks. The experimental results conclude that EWLS and EWCC are largely competitive on DIMACS benchmarks, where they outperform other current best heuristic algorithms on most hard instances, and dominate on the hard random BHOSLIB benchmarks. Moreover, EWCC makes a significant improvement over EWLS, while both EWLS and EWCC set a new record on a twenty-year challenge instance. Further, EWCC performs quite well even on structured instances in comparison to the best exact algorithm we know. We also study the run-time behavior of EWLS and EWCC which shows interesting properties of both algorithms.

A number of algorithms have been proposed for the Minimum Vertex Cover problem. However, they are far from satisfactory, especially on hard instances. In this paper, we introduce Edge Weighting Local Search (EWLS), a new local search algorithm for the Minimum Vertex Cover problem. EWLS is based on the idea of extending a partial vertex cover into a vertex cover. A key point of EWLS is to find a vertex set that provides a tight upper bound on the size of the minimum vertex cover. To this purpose, EWLS employs an iterated local search procedure, using an edge weighting scheme which updates edge weights when stuck in local optima. Moreover, some sophisticated search strategies have been taken to improve the quality of local optima. Experimental results on the broadly used DIMACS benchmark show that EWLS is competitive with the current best heuristic algorithms, and outperforms them on hard instances. Furthermore, on a suite of difficult benchmarks, EWLS delivers the best results and sets a new record on the largest instance.

Web service protocols are designed in XML formats so the message structures within are quite different from the conventional protocols. Therefore, the traditional formal verification techniques which have gain substantial achievements in practice, cannot be applied directly to them because their underlying models are written in Alice\Bob-style descriptions using high-level message formats instead of XML tags. In this paper, we propose a justification-oriented and automatic formal approach to verify, in the standard Dolev-Yao model, security properties expressed as epistemic notions for a Web service protocol, based on a fault-preserving mapping tool called SuD (SOAP under Dolev-Yao). Our approach can shed more light on Web service protocols in another perspective because the concerned properties to be verified are some inherent features of protocols.

In this paper, we investigate knowledge reasoning within a simple framework called knowledge structure. We use variable forgetting as a basic operation for one agent to reason about its own or other agents\' knowledge. In our framework, two notions namely agents\' observable variables and the weakest sufficient condition play important roles in knowledge reasoning. Given a background knowledge base and a set of observable variables for each agent, we show that the notion of an agent knowing a formula can be defined as a weakest sufficient condition of the formula under background knowledge base. Moreover, we show how to capture the notion of common knowledge by using a generalized notion of weakest sufficient condition. Also, we show that public announcement operator can be conveniently dealt with via our notion of knowledge structure. Further, we explore the computational complexity of the problem whether an epistemic formula is realized in a knowledge structure. In the general case, this problem is PSPACE-hard; however, for some interesting subcases, it can be reduced to co-NP. Finally, we discuss possible applications of our framework in some interesting domains such as the automated analysis of the well-known muddy children puzzle and the verification of the revised Needham-Schroeder protocol. We believe that there are many scenarios where the natural presentation of the available information about knowledge is under the form of a knowledge structure. What makes it valuable compared with the corresponding multi-agent S5 Kripke structure is that it can be much more succinct.

Bounded model checking (BMC) has played an important role in verification of software, embedded systems and protocols. The idea of BMC is to encode finite state machine (FSM) and linear temporal logic (LTL) verification specification into satisfiability (SAT) instances, and then to search for a counterexample via various SAT tools. Improving encoding technology of BMC can generate a SAT instance easy to solve, and therefore is essential to improve the efficiency of BMC. In this paper, we improve the encoding of BMC by combining the characteristic of FSM state transition and semantics of LTL, get a simple and efficient recursion formula which is useful to efficiently generate SAT instances. We present an efficient algorithm to encode the modal operator (safety formula) in BMC. The experiments for comparative analysis shows that this encoding algorithm is more powerful than the existing two mainstream encoding algorithms in both the scale of generated SAT instances and the solving efficiency. The methodology presented in this paper is also valuable for optimization of other modal operator encodings in BMC.

Model checking is a promising approach to automatic verification, which has concentrated on specification expressed in temporal logics. Comparatively little attention has been given to temporal logics of knowledge, although such logics have been proven to be very useful in the specifications of protocols for distributed systems. In this paper, we addressed the model checking problem for a temporal logic of knowledge (Halpern and Vardi's logic of CKLn). Based on the semantics of interpreted systems with local propositions, we developed an approach to symbolic CKLn model checking via Ordered Binary decision diagrams and implemented the corresponding symbolic model checker MCTK. In our approach to model checking specifications involving agents' knowledge, the knowledge modalities are eliminated via quantifiers over agents' non-observable variables. We then modelled the Dining Cryptographers protocol and the five-hands protocol for Russian Cards problem in MCTK. Via these two examples, we compare MCTK's empirical performance with two different state-of-the-art epistemic model checkers, MCK and MCMAS.

The standard Kripke semantics of epistemic logics has been applied successfully to reasoning communication protocols under the assumption that the network is not hostile. This paper introduces a natural semantics of Kripke semantics called knowledge structure and, by this kind of Kripke semantics, analyzes communication protocols over hostile networks, especially on authentication protocols. Compared with BAN-like logics, the method is automatically implementable because it operates on the actual definitions of the protocols, not on some difficult-to-establish justifications of them. What is more, the corresponding tool called SPV (Security Protocol Verifier) has been developed. Another salient point of this approach is that it is justification-oriented instead of falsificationoriented, i.e. finding bugs in protocols.

In this paper we give two alternative notions of possibility that satisfy Halpern's two conditions. One of the two notions, for the logic S4n, seems to behave in the same way as Halpern's original one; and the other has quite different properties from those of Halpern's. They exemplify that the answers are negative to the two questions proposed by Halpern, that is, whether his two conditions are sufficient to determine the notion of 'possibility' uniquely for a given logic and whether the results he proved for his three notions of possibility hold for any of those satisfying the two conditions.

In Reiter's default logic, the operator in the fixed-point definition of extension is not appropriate to compute extensions by its iterated applications. This paper presents a class of alternative operators, called compatible ones, such that, at least for normal default theories and so-called well-founded, ordered default theories, we can get extensions by iterated applications of them. In addition, we completely answer Etherington's conjectures about both his procedure for generating extensions and a modified version of it. In particular, we give an example of a finite, ordered default theory, for which the original procedure fails to converge, and show that the computation of the modified one is essentially the iteration of a compatible operator and converges for finite, ordered theories.