Graph-level anomaly detection (GLAD), which identifies rare or atypical graphs within a graph set, is crucial for applications such as image analysis, industrial defect inspection and fraud detection. However, existing GLAD approaches typically rely on the in-distribution hypothesis while lacking generalization capability for out-of-distribution (OOD) scenarios (e.g., different graph sizes), which largely limits the application in the real world. For the first time, we formulate the OOD generalization problem for GLAD, where testing graph data exhibit significant distributional shifts from training data. To tackle two common types of distributional shifts, domain generalization and subpopulation shift, we propose the Fine-Grained Subpopulation Graph-Level Anomaly Detection (FGS-GLAD). First, we propose a Graph Information Bottleneck-based Anomaly Detection Module (GIB4AD) that implements graph reverse distillation and graph information bottleneck on the graph to enhance task-relevant feature extraction for domain generalization. Second, We propose a Fine-Grained Subpoulation Inference Module (FGSI) to predict fine-grained subpopulations and focus on critical inter-subpopulation features through a supervised contrastive mechanism. Experiments on seven benchmark datasets and ten baselines demonstrate our model's superiority in handling domain generalization and subpopulation shift.

To identify the root causes of attacks, behavior abstraction (BA) converts audit logs into multiple behavior graphs and finds similar ones, which has proven effective in bridging the semantic gap and reducing manual workload. Existing works fail to achieve both interpretability and generalization, while also exhibiting limited robustness when facing adversarial attacks. In this paper, we give the first attempt at interpretable and robust behavior abstraction and propose a novel method called Environment-Disentangled Heterogeneous Graph Neural Network (EDHGNN). Motivated by Information Bottleneck (IB) principle, we propose a Heterogeneous Subgraph Disentanglement (HSD) module to disentangle label-relevant and environmental subgraphs through single optimization. We also introduce an Adapted Graph-Level Attention (AGLA) module to extract minimal sufficient representations from label-relevant subgraphs, a Label-Guided Graph Reconstructor (LGGR) to maximize environmental information coverage via reconstruction, and a Relevance Discriminator (RD) to enhance disentanglement quality. Additionally, we construct a new dataset contains ground-truth explanations and 4,160 behavior graphs. Extensive experiments demonstrate that EDHGNN outperforms the state-of-the-art methods in terms of interpretability and robustness against adversarial attacks.

Graph-Level Anomaly Detection (GLAD) seeks to identify anomalous graphs within graph datasets, which has significant applications across diverse real-world fields. Most existing GLAD methods are trained in an unsupervised manner due to high costs for labeling, resulting in sub-optimal performance when compared to supervised methods. To fill this gap, we propose a Disentangled Generation-Based Prototypical Alignment (DGPA) method that extends graph-level anomaly detection to Few-Shot Unsupervised Domain Adaptation (FUDA) setting, aiming to identify anomalous graphs from a set of unlabeled graphs (target domain) by using partially labeled graphs from a different but related domain (source domain), which fulfills the practical requirement of transferring anomaly knowledge. This is specifically achieved through a dedicated Disentangled Sample Generation module, which addresses label scarcity by generating faithful samples with disentangled representation learning grounded in Information Bottleneck principle, along with a Graph-based Prototypical Self-Supervision module, which alleviates domain shift by encoding and aligning semantic structures in the shared latent space across domains in a self-supervised manner. Extensive experiments on five benchmark datasets reveal the effectiveness of our proposed DGPA.

The serverless architecture has attracted significant attention due to its cost-effectiveness and ease of management. However, the serverless framework increases the attack surface of applications, resulting in frequent security incidents. Consequently, conducting comprehensive attack investigation and analysis in serverless applications has become critically important. Current serverless investigation methods face challenges such as dependency explosion (DE), incomplete information records, and lack of user transparency. These challenges lead to inadequate visibility of application interaction behaviors, complicating effective attack investigation and analysis. To mitigate these issues, this paper introducesErinyes, a solution that facilitates request-level attack investigation and analysis in serverless environments through the construction of provenance graph.Erinyesimproves the visibility of serverless applications via three core components. The partition enabling module effectively partitions function operations based on incoming requests; the log collection module is responsible for aggregating audit and network logs pertinent to function operations; and the provenance graph builder consolidates and parses the collected logs into a comprehensive provenance graph.Erinyeshas been evaluated on the OpenFaaS platform in 5 distinct attack scenarios, achieving an average accuracy of 99.6% in execution partition, a completeness of 100% in provenance graph, and an average runtime overhead of 7.05%.

Heterogeneous Graph Neural Networks (HGNNs) have achieved state-of-the-art performance in classifying molecular graphs, capitalizing on their ability to capture rich semantics. However, HGNNs for molecule property prediction exhibit significant susceptibility to adversarial attacks—a challenge that prior research has entirely overlooked. To fill this gap, this paper introduces the first study focused on robust graph-level representation learning tailored for heterogeneous molecular graphs. To achieve this goal, we propose a comprehensive Robust Heterogeneous Graph Classification (RHGC) framework grounded in the Information Bottleneck principle, which aims to identify the most informative and least noisy heterogeneous subgraphs to derive robust, holistic representations. This is specifically accomplished through a dedicated Node Semantic Purifier, which enhances node-level and semantic-level robustness by eliminating label-irrelevant interference using graph stochastic attention and the Hilbert-Schmidt Independence Criterion, along with a Global Graph Disentanglement method, which improves graph-level robustness by addressing information leak. Experiments on three molecular benchmarks demonstrate that RHGC enhances accuracy by an average of 5.06% under all three attack settings and meanwhile by 4.33% on clean data.

Learning Ordered Binary Decision Diagrams (OBDDs) from large-scale datasets is an important topic of explainable artificial intelligence. However, existing search-based methods are still limited in scalability regarding dataset size, since they must explicitly encode the satisfaction of all examples in a dataset. To tackle this challenge, we introduce an OBDD encoding method to parameterize a neural network. This method frees satisfaction encoding of all examples in a dataset while leveraging mini-batch training techniques to enhance learning efficiency. Our main theoretical contribution is to prove that our approach enables the simulation of OBDD inference within a continuous space. Besides, we identify faithful OBDD encoding to fulfill the properties required by OBDDs, allowing to interpret an OBDD directly from the learned parameter assignment. With faithful OBDD encoding, we present an end-to-end neural model named ØBDDNet, being capable of coping with large-scale datasets. Experimental results exhibit better scalability and competitive prediction performance of ØBDDNet compared to state-of-the-art OBDD learners. Valuable insights about faithful OBDD encoding are derived from the ablation study. The implementation is available at: https://github.com/jmq-design/OBDD-NET.

Existing graph fraud detection (GFD) methods have made remarkable progress with well-labeled training samples. However, in real applications, adequate training data may be unavailable due to the high cost of manual annotation and the scarcity of fraud samples. Therefore, we explore the one-class graph fraud detection task for the first time, which trains the model only on normal data and can detect fraud samples during inference. This task faces two main challenges: heterogeneity discrepancy in different relationships and diverse distribution of the normal data. To address the above challenges, we propose a novel one-class GFD method named OC-GFD. We design a hierarchical message propagation mechanism that learns both global features and local features under different relationships to accurately extract node representations from the GNN model. Subsequently, we integrate our model with an adaptive Gaussian mixture module to capture the diverse distribution of normal samples, enhancing the characterization of subtle differences in normal behavior and improving fraud detection accuracy. Experimental results show that OC-GFD outperforms state-of-the-art graph fraud detection and one-class classification approaches on Yelp and Amazon datasets in the one-class scenario. Code is available at https://github.com/THSS-GAD/OC-GFD.

The Intrusion Detection System (IDS) is an essential component of cybersecurity for Advanced Persistent Threat (APT) defense. A successful APT attack is a series of tactics aimed at achieving specific goals. Due to the versatility of these tactics, IDS must respond to numerous novel and previously unobserved attacks. However, traditional IDS systems are ineffective in defending against unknown attacks, as they assume that training and real data belong to the same distribution. To tackle this problem, we introduce OpenSentinel, which leverages a deep open set recognition method to effectively detect unknown attacks and pinpoint them to specific APT stages. With a specially designed log modeling approach and a neural network model, OpenSentinel generates human-readable reports to characterize attacks and facilitate further analysis for security experts. We validate the detection performance of OpenSentinel in two experimental environments with over 100 scenarios. Qualitative and quantitative results demonstrate that our method achieves an accuracy of over 90% and remains robust when facing real-world attacks. Meanwhile, we developed a benchmark APT attack dataset with well-defined stages named BeATT&CKed, which can be used for future research.

Learning-based Behavior Graph Classification (BGC) is widely used in Internet infrastructure for partitioning and identifying similar behavior graphs, yet its real-world application faces notable challenges. The challenges are: (i) fine-grained emerging behavior graphs, and (ii) incremental model adaptations. To tackle these issues, we propose to (i) mine semantics in multi-source logs using Large Language Models (LLMs) under In-Context Learning (ICL), and (ii) bridge the gap between Out-Of-Distribution (OOD) detection and class-incremental graph learning. Based on these ideas, we develop the first unified framework termed as Fine-Grained and Class-Incremental Behavior Graph Classification (FG-CIBGC ). It consists of two novel modules, i.e., gPartition and gAdapt, that are used for partitioning fine-grained graphs and performing unknown class detection and adaptation, respectively. To validate FG-CIBGC, we introduce a new benchmark, including a 4,992-graph, 32-class dataset from 8 attack scenarios and a novel Edge Intersection over Union (EIoU) metric. Extensive experiments show FG-CIBGC outperforms baselines on fine-grained class-incremental BGC task and generates behavior graphs which enhance downstream tasks.

System intrusions, particularly Advanced Persistent Threats (APTs), pose significant threats to enterprises and organizations. Provenance graph-based attack detection and investigation methods are crucial for defending against these intrusions. To detect various attacks, security systems collect comprehensive operating system event data, resulting in massive provenance graphs that increase storage costs and complicate analysis and querying. Efficiently optimizing these provenance graphs has thus become a core issue. However, existing data reduction methods often mistakenly delete critical security information, significantly impacting attack detection and investigation. This paper introduces TeRed, a novel method for reducing provenance graphs based on normal behavior patterns. Our approach employs unit tests to learn the system’s normal behavior patterns, which are then used to streamline the provenance graph. Experiments on five datasets show that our method reduces the provenance graph while preserving all attack-related information. Importantly, it does not compromise attack detection and investigation, showcasing significant advantages over other data reduction techniques.

Time-sensitive networking (TSN), essential in industrial networks for its promise of reliable and deterministic data transmission, faces deployment challenges due to the limitations of existing time-aware shaper (TAS)-based scheduling algorithms. Specifically, the size of the generated gate control lists (GCLs) is usually too large to be deployed in actual devices. To bridge the gap between theory and practice, we propose FlexTAS, a flexible and practical solution for TSN. The key insight behind FlexTAS is that relaxing gating does not introduce uncertainty, as long as nonoverlap reserved time slots are guaranteed. FlexTAS is comprised of two main components: first, a novel gating model deviates from the conventional TAS model by incorporating selective relaxation of gating at certain nodes; and second, a deep reinforcement learning-based engine to rapidly generate valid schedules. We build a real testbed and validate the effectiveness of our proposed solution. Our evaluation demonstrates that FlexTAS effectively controls the number of gate entries within the GCL capacity of devices, while simultaneously meeting the Quality of Service(QoS) requirements of time-triggered streams. It significantly reduces the number of GCL entries by 60% to 80%, and facilitates deployment in heterogeneous networks, thus offering a practical solution for TSN.

It is important to automatically discover the underlying tree-structured formulae from large amounts of data. In this paper, we examine learning linear temporal logic on finite traces (LTLf) formulae, which is a tree structure syntactically and characterizes temporal properties semantically. Its core challenge is to bridge the gap between the concise tree-structured syntax and the complex LTLf semantics. Besides, the learning quality is endangered by explosion of the search space and wrong search bias guided by imperfect data. We tackle these challenges by proposing an LTLf encoding method to parameterize a neural network so that the neural computation is able to simulate the inference of LTLf formulae. We first identify faithful LTLf encoding, a subclass of LTLf encoding, which has a one-to-one correspondence to LTLf formulae. Faithful encoding guarantees that the learned parameter assignment of the neural network can directly be interpreted to an LTLf formula. With such an encoding method, we then propose an end-to-end approach, TLTLf, to learn LTLf formulae through neural networks parameterized by our LTLf encoding method. Experimental results demonstrate that our approach achieves state-of-the-art performance with up to 7% improvement in accuracy, highlighting the benefits of introducing the faithful LTLf encoding.

Graph-based fraud detection (GFD) can be regarded as a challenging semi-supervised node binary classification task. In recent years, Graph Neural Networks (GNN) have been widely applied to GFD, characterizing the anomalous possibility of a node by aggregating neighbor information. However, fraud graphs are inherently heterophilic, thus most of GNNs perform poorly due to their assumption of homophily. In addition, due to the existence of heterophily and class imbalance problem, the existing models do not fully utilize the precious node label information. To address the above issues, this paper proposes a semi-supervised GNN-based fraud detector SEC-GFD. This detector includes a hybrid filtering module and a local environmental constraint module, the two modules are utilized to solve heterophily and label utilization problem respectively. The first module starts from the perspective of the spectral domain, and solves the heterophily problem to a certain extent. Specifically, it divides the spectrum into various mixed-frequency bands based on the correlation between spectrum energy distribution and heterophily. Then in order to make full use of the node label information, a local environmental constraint module is adaptively designed. The comprehensive experimental results on four real-world fraud detection datasets denote that SEC-GFD outperforms other competitive graph-based fraud detectors. We release our code at https://github.com/Sunxkissed/SEC-GFD.

Aspect-based sentiment analysis (ABSA) has attracted much attention due to its wide application scenarios. Most previous studies have focused solely on monolingual ABSA, posing a formidable challenge when extending ABSA applications to multilingual scenarios. In this paper, we study upgrading monolingual ABSA to cross-lingual ABSA. Existing methods usually exploit pre-trained cross-lingual language to model cross-lingual ABSA, and enhance the model with translation data. However, the low-resource languages might be under-represented during the pre-training phase, and the translation-enhanced methods heavily rely on the quality of the translation and label projection. Inspired by the observation that quantum entanglement can correlate multiple single systems, we map the monolingual expression to the quantum Hilbert space as a single quantum system, and then utilize quantum entanglement and quantum measurement to achieve cross-lingual ABSA. Specifically, we propose a novel quantum neural model named QPEN (short for quantum projection and quantum entanglement enhanced network). It is equipped with a proposed quantum projection module that projects aspects as quantum superposition on a complex-valued Hilbert space. Furthermore, a quantum entanglement module is proposed in QPEN to share language-specific features between different languages without transmission. We conducted simulation experiments on the classical computer, and experimental results on SemEval-2016 dataset demonstrate that our method achieves state-of-the-art performance in terms of F1-scores for five languages.

Document-level relation extraction (DocRE)aims to extract relations between entities in a whole document.One of the pivotal challenges of DocRE is to capture the intricate interdependencies between relations of entity pairs.Previous methods have shown that logical rules can explicitly help capture such interdependencies.These methods either learn logical rules to refine the output of a trained DocRE model, or first learn logical rules from annotated data and then inject the learnt rules into a DocRE model using an auxiliary training objective.However, these learning pipelines may suffer from the issue of error propagation.To mitigate this issue, we propose Joint Modeling Relation extraction and Logical rules or JMRL for short, a novel rule-based framework that jointly learns both a DocRE model and logical rules in an endto-end fashion.Specifically, we parameterize a rule reasoning module in JMRL to simulate the inference of logical rules, thereby explicitly modeling the reasoning process.We also introduce an auxiliary loss and a residual connection mechanism in JMRL to better reconcile the DocRE model and the rule reasoning module.Experimental results on four benchmark datasets demonstrate that our proposed JMRL framework is consistently superior to existing rule-based frameworks, improving five baseline models for DocRE by a significant margin.

Knowledge graph completion (KGC) aims to infer missing facts from existing facts. Learning logical rules plays a pivotal role in KGC, as logical rules excel in explaining why a missing fact is inferred. Most existing rule learning methods focus merely on learning chain-like rules, neglecting type constraints on entities. In practice, type constraints are crucial in expressing precise rules. Therefore, we propose a novel formalism for logical rules named TC-rules, which complements chain-like rules with both explicit and implicit type constraints on entity variables. Accordingly, we propose an end-to-end approach to effectively learn TC-rules, by parameterizing a neural model to simulate the inference of TC-rules. Considering that existing end-to-end methods learn two different sets of logical rules to respectively answer a head query (?,rnew, t) and a tail query (h,rrnew, ?), leading to confusing explanations for supporting a new fact (h,rnew, t), we propose a bi-directional learning mechanism to ensure that the TC-rules learnt for answering (?,rnew, t) are the same as the TC-rules learnt for answering (h,rnew, ?). Experimental results on eight benchmark datasets demonstrate that the proposed method outperforms state-of-the-art rule learners in both the link prediction task and the triple classification task. Furthermore, our case study confirms that expressive TC-rules can be extracted from the parameter assignment of the learnt neural model.

Many existing anomaly detection methods assume the availability of a large-scale normal dataset. But for many applications, limited by resources, removing all anomalous samples from a large un-labeled dataset is unrealistic, resulting in contaminated datasets. To detect anomalies accurately under such scenarios, from the probabilistic perspective, the key question becomes how to learn the normal-data distribution from a contaminated dataset. To this end, we propose to collect two additional small datasets that are comprised of partially-observed normal and anomaly samples, and then use them to help learn the distribution under an adversarial learning scheme. We prove that under some mild conditions, the proposed method is able to learn the correct normal-data distribution. Then, we consider the overfitting issue caused by the small size of the two additional datasets, and a correctness-guaranteed flipping mechanism is further developed to alleviate it. Theoretical results under incomplete observed anomaly types are also presented. Extensive experimental results demonstrate that our method outperforms representative baselines when detecting anomalies under contaminated datasets.

Functional code clone detection is important for software maintenance. In recent years, deep learning techniques are introduced to improve the performance of functional code clone detectors. By representing each code snippet as a vector containing its program semantics, syntactically dissimilar functional clones are detected. However, existing deep learning-based approaches attach too much importance to code feature learning, hoping to project all recognizable knowledge of a code snippet into a single vector. We argue that these deep learning-based approaches can be enhanced by considering the characteristics of syntactic code clone detection, where we need to compare the contents of the source code (e.g., intersection of tokens, similar flow graphs, and similar subtrees) to obtain code clones. In this paper, we propose a novel deep learning-based approach named DSFM, which incorporates comparisons between code snippets for detecting functional code clones. Specifically, we improve the typical deep clone detectors with deep subtree interactions that compare every two subtrees extracted abstract syntax trees (ASTs) of two code snippets, thereby introducing more fine-grained semantic similarity. By conducting extensive experiments on three widely-used datasets, GCJ, OJClone, and BigCloneBench, we demonstrate the great potential of deep subtree interactions in code clone detection task. The proposed DSFM outperforms the state-of-the-art approaches, including two traditional approaches, two unsupervised and four supervised deep learning-based baselines.

Linear temporal logic (LTL) satisfiability checking has a high complexity, i.e., PSPACE-complete. Recently, neural networks have been shown to be promising in approximately checking LTL satisfiability in polynomial time. However, there is still a lack of neural network-based approach to the problem of checking LTL satisfiability and generating traces as evidence, simply called SAT-and-GET, where a satisfiable trace is generated as evidence if the given LTL formula is detected to be satisfiable. In this paper, we tackle SAT-and-GET via bridging LTL trace checking to neural network inference. Our key theoretical contribution is to show that a well-designed neural inference process, named after neural trace checking, is able to simulate LTL trace checking. We present a neural network-based approach VSCNet. Relying on the differentiable neural trace checking, VSCNet is able to learn both to check satisfiability and to generate traces via gradient descent. Experimental results confirm the effectiveness of VSCNet, showing that it significantly outperforms the state-of-the-art (SOTA) neural network-based approaches for trace generation, on average achieving up to 41.68% improvement in semantic accuracy. Besides, compared with the SOTA logic-based approach nuXmv and Aalta, VSCNet achieves averagely 186X and 3541X speedups on large-scale datasets, respectively.

SQL injection attacks have posed a significant threat to web applications for decades. They obfuscate malicious codes into natural SQL statements so as to steal sensitive data, making them difficult to detect. Generally, malicious signals can be identified by using the contextual information of SQL statements. Such contextual information, however, is not always easily captured. Due to the fact that SQL as a formal language is highly structured, two tokens that are spatially far away may be semantically very close. An effective approach thus should take the structural feature of SQL statements into account when modeling their contextual information.

This paper focuses on the design of dynamic quantization (DQ) and coded transmission schemes for federated learning (FL). In the conventional FL system, the updates divergences typically decrease with communication rounds as training goes on. We first study both the impact of the quantization bit-width in the error-free transmission scenario and the impact of bit error rate (BER) in the practical transmission scenario on the performance of FL. Then we propose a DQ scheme based on the fixed B-bit or 1-bit quantization scheme, where each device quantizes its local updates with dynamic bit-width according to the test accuracy of the global model and device-to-server signal-to-noise ratio (SNR). Due to the quantization bit-width is dynamic, the test accuracy (as a kind of extra data) is needed for devices to determine the bit-width, and the devices need to inform the server of the resultant bit-width (as another kind of extra data). To reliably transmit these extra data without consuming extra transmission resource, we utilize the free-ride coding, where the extra data are embedded into the low-density parity-check (LDPC) coded payload data. Numerical results show that in the practical scenario, B-bit (B > 1) quantization scheme shows fast convergence speed and high final accuracy (in high SNR region) while the L-bit quantization scheme exhibits greater robustness (in low SNR region). They also show that the proposed FL by DQ and free-ride coding not only can significantly reduce the communication overhead with a negligible performance gap to the upper bound (error-free scheme) even in low SNR region but also outperforms the fixed quantization coded transmission FL scheme in terms of accuracy and convergence speed.

This paper is concerned with the wireless video surveillance systems, which were widely deployed and now augmented by edge computing. Armed with the edge computing, on-device local intelligence algorithms like machine learning (ML) can be utilized to extract specific semantics such as events classification in terms of risk levels which are vital for downstream tasks, say video retrieval. Different from the emergent semantic communications, not only these extracted semantic features (for further use) but also the raw video (by legal requirement) need to be sent to the surveillance center. This application scenario is also different from those for the conventional edge computing. The main objective of this paper is to propose a cost-effective scheme for such extra semantic data transmission in a free-ride way that has mild impact on the existing communication link and requires neither bandwidth expansion nor extra transmission power. The basic idea is to superimpose in the binary field the extra bits on the coded payload data. Numerical results show that, with the 5G low-density parity-check (LDPC) codes, simultaneously transmitting semantic features along with the payload data delivers more reliable semantic features and has a negligible effect on the quality of the payload data.

Cyberattacks have caused significant damage and losses in various domains. While existing attack investigations against cyberattacks focus on identifying compromised system entities and reconstructing attack stories, there is a lack of information that security analysts can use to locate software vulnerabilities and thus fix them. In this paper, we present AiVl, a novel software vulnerability location method to push the attack investigation further. AiVl relies on logs collected by the default built-in system auditing tool and program binaries within the system. Given a sequence of malicious log entries obtained through traditional attack investigations, AiVl can identify the functions responsible for generating these logs and trace the corresponding function call paths, namely the location of vulnerabilities in the source code. To achieve this, AiVl proposes an accurate, concise, and complete specific-domain program modeling that constructs all system call flows by static-dynamic techniques from the binary, and develops effective matching-based algorithms between the log sequences and program models. To evaluate the effectiveness of AiVl, we conduct experiments on 18 real-world attack scenarios and an APT, covering comprehensive categories of vulnerabilities and program execution classes. The results show that compared to actual vulnerability remediation reports, AiVl achieves a 100% precision and an average recall of 90%. Besides, the runtime overhead is reasonable, averaging at 7%.

Anomaly detection aims to detect instances that deviate significantly from the majority. Due to the difficulties of collecting a large amount of anomalies in practice, existing methods generally assume the availability of a clean normal dataset and leverage it to detect anomalies by characterizing the normality of normal samples. However, for many application scenarios, collecting a normal dataset that is sufficiently clean is not easy. What is often observed is that a small amount of anomalies are often falsely mixed into the normal dataset, resulting in a contaminated dataset. Obviously, the contamination in the normal dataset could significantly compromise the model's ability to detect anomalies. To alleviate this issue, two contamination-immune bidirectional generative adversarial networks (BiGAN) are developed, which can learn the probability distribution of normal samples from a contaminated dataset under some mild conditions. Rigorous proofs are provided to guarantee the theoretical correctness of the proposed models. Thanks to the removing of negative influences from the contamination samples, the proposed contamination-immune models can thus be applied to detect anomalies accurately for the scenarios with contaminated datasets. Extensive experimental results show that the proposed method outperforms the current state-of-the-art (SOTA) ones significantly under the scenarios with contaminated training datasets.

We study the problem of learning a single occurrence regular expression with interleaving (SOIRE) from a set of text strings possibly with noise. SOIRE fully supports interleaving and covers a large portion of regular expressions used in practice. Learning SOIREs is challenging because it requires heavy computation and text strings usually contain noise in practice. Most of the previous studies only learn restricted SOIREs and are not robust on noisy data. To tackle these issues, we propose a noise-tolerant differentiable learning approach SOIREDL for SOIRE. We design a neural network to simulate SOIRE matching and theoretically prove that certain assignments of the set of parameters learnt by the neural network, called faithful encodings, are one-to-one corresponding to SOIREs for a bounded size. Based on this correspondence, we interpret the target SOIRE from an assignment of the set of parameters of the neural network by exploring the nearest faithful encodings. Experimental results show that SOIREDL outperforms the state-of-the-art approaches, especially on noisy data.

With the successful application of hardware agile design methodology, it has become a big challenge to optimize the design in novelly defined intermediate representations (IR), such as FIRRTL. However, there is little work focusing on this challenge, or the optimization tasks are left to logic synthesizers by translating IRs into designs in hardware description languages (HDL).

Dealing with planning problems with both logical relations and numeric changes in real-world dynamic environments is challenging. Existing numeric planning systems for the problem often discretize numeric variables or impose convex constraints on numeric variables, which harms the performance when solving problems, especially when the problems contain obstacles and non-linear numeric effects. In this work, we propose a novel algorithm framework to solve numeric planning problems mixed with logical relations and numeric changes based on gradient descent. We cast the numeric planning with logical relations and numeric changes as an optimization problem. Specifically, we extend the syntax to allow parameters of action models to be either objects or real-valued numbers, which enhances the ability to model real-world numeric effects. Based on the extended modeling language, we propose a gradient-based framework to simultaneously optimize numeric parameters and compute appropriate actions to form candidate plans. The gradient-based framework is composed of an algorithmic heuristic module based on propositional operations to select actions and generate constraints for gradient descent, an algorithmic transition module to update states to the next ones, and a loss module to compute loss. We repeatedly minimize loss by updating numeric parameters and compute candidate plans until it converges into a valid plan for the planning problem.

With the superior learning ability of neural networks, it is promising to obtain highly confident results for linear temporal logic (LTL) satisfiability checking in polynomial time. However, existing neural approaches are limited in inductive ability and in supporting with an arbitrary number of atomic propositions. Besides, there is no mechanism to verify the results for satisfiability checking. In this paper, we propose an approach to checking the satisfiability of an LTL formula and meanwhile generating a satisfiable trace if the LTL formula is satisfiable, where the satisfiable trace verifies the satisfiability result. The core contribution is a new graph representation for LTL formulae - one-step unfolded graph (OSUG) to incorporate the syntax and semantic features of LTL. Preliminary results show that our approach is superior to the state-of-the-art neural approaches on synthetic datasets and confirms the effectiveness of OSUG.

Formal specifications are widely used in software testing approaches, while writing such specifications is a time-consuming job. Recently, a number of methods have been proposed to mine specifications from execution traces, typically in the form of linear temporal logic (LTL). However, existing works have the following disadvantages: (1) ignoring the negative impact of imperfect traces, which come from partial profiling, missing context information, or buggy programs; (2) relying on templates, resulting in limited expressiveness; (3) requesting negative traces, which are usually unavailable in practice. In this paper, we propose PURLTL, which is able to mine arbitrary LTL specifications from imperfect traces. To alleviate the search space explosion and the wrong search bias, we propose a neural-based method to search LTL formulae, which, intuitively, simulates LTL path checking through differentiable parameter operations. To solve the problem of lacking negative traces, we transform the problem into learning from positive and unlabeled samples, by means of data augmentation and applying positive and unlabeled learning to the training process. Experiments show that our approach surpasses the previous start-of-the-art (SOTA) approach by a large margin. Besides, the results suggest that our approach is not only robust with imperfect traces, but also does not rely on formula templates.

Learning rule-based systems plays a pivotal role in knowledge graph completion (KGC). Existing rule-based systems restrict the input of the system to structural knowledge only, which may omit some useful knowledge for reasoning, e.g., textual knowledge. In this paper, we propose a two-stage framework that imposes both structural and textual knowledge to learn rule-based systems. In the first stage, we compute a set of triples with confidence scores (called \emph{soft triples}) from a text corpus by distant supervision, where a textual entailment model with multi-instance learning is exploited to estimate whether a given triple is entailed by a set of sentences. In the second stage, these soft triples are used to learn a rule-based model for KGC. To mitigate the negative impact of noise from soft triples, we propose a new formalism for rules to be learnt, named \emph{text enhanced rules} or \emph{TE-rules} for short. To effectively learn TE-rules, we propose a neural model that simulates the inference of TE-rules. We theoretically show that any set of TE-rules can always be interpreted by a certain parameter assignment of the neural model. We introduce three new datasets to evaluate the effectiveness of our method. Experimental results demonstrate that the introduction of soft triples and TE-rules results in significant performance improvements in inductive link prediction.

The user interface (UI) of web applications is usually the entry point of web attacks against enterprises and organizations. Finding the UI elements utilized by the intruders is of great importance both for attack interception and web application fixing. Current attack investigation methods targeting web UI either provide rough analysis results or have poor performance in high concurrency scenarios, which leads to heavy manual analysis work. In this paper, we propose TeSec, an accurate attack investigation method for web UI applications. TeSec makes use of two kinds of correlations. The first one, built from annotated audit log partitioned by PID/TID and delimiter-logs, captures the correspondence between audit log entries and web requests. The second one, modeled by an Aho-Corasick automaton built during system testing period, captures the correspondence between requests and the UI elements/events. Leveraging these two correlations, TeSec can accurately and automatically locate the UI elements/events (i.e., the root cause of the alarm) from an alarm, even in high concurrency scenarios. Furthermore, TeSec only needs to be deployed in the server and does not need to collect logs from the client-side browsers. We evaluate TeSec on 12 web applications. The experimental results show that the matching accuracy between UI events/elements and the alarm is above 99.6%. And security analysts only need to check no more than 2 UI elements on average for each individual forensics analysis. The maximum overhead of average response time and audit log space overhead are low (4.3% and 4.6% respectively).

Graph has been widely used in various applications, while how to optimize the graph is still an open question. In this paper, we propose a framework to optimize the graph structure via structure evolution on graph manifold. We first define the graph manifold and search the best graph structure on this manifold. Concretely, associated with the data features and the prediction results of a given task, we define a graph energy to measure how the graph fits the graph manifold from an initial graph structure. The graph structure then evolves by minimizing the graph energy. In this process, the graph structure can be evolved on the graph manifold corresponding to the update of the prediction results. Alternatively iterating these two processes, both the graph structure and the prediction results can be updated until converge. It achieves the suitable structure for graph learning without searching all hyperparameters. To evaluate the performance of the proposed method, we have conducted experiments on eight datasets and compared with the recent state-of-the-art methods. Experiment results demonstrate that our method outperforms the state-of-the-art methods in both transductive and inductive settings.

Massive GPU acceleration processors have been used in high-performance computing systems. The Dennard scaling has led to power and thermal constraints limiting the performance of such systems. The demand for both increased performance and energy efficiency is highly desired. This article presents a multilayer low-power optimization method for warps and tasks parallelisms. We present a dynamic frequency regulation scheme for performance parameters in terms of load balance and load imbalance. The method monitors the energy parameters in runtime and adjusts adaptively the voltage level to ensure performance efficiency with energy reduction. The experimental results show that the multilayer low-power optimization with dynamic frequency regulation can achieve 40% energy consumption reduction with only 1.6% performance degradation, thus reducing 59% maximum energy consumption. It can further save about 30% energy consumption in comparison with the single-layer energy optimization.

Person re- identification (Re-ID) has become a hot research topic due to its widespread applications. Conducting person Re-ID in video sequences is a practical requirement, in which the crucial challenge is how to pursue a robust video representation based on spatial and temporal features. However, most of the previous methods only consider how to integrate part-level features in the spatio-temporal range, while how to model and generate the part-correlations is little exploited. In this paper, we propose a skeleton-based dynamic hypergraph framework, namely Skeletal Temporal Dynamic Hypergraph Neural Network (ST-DHGNN) for person Re-ID, which resorts to modeling the high-order correlations among various body parts based on a time series of skeletal information. Specifically, multi-shape and multi-scale patches are heuristically cropped from feature maps, constituting spatial representations in different frames. A joint-centered hypergraph and a bone-centered hypergraph are constructed in parallel from multiple body parts (i.e., head, trunk, and legs) with spatio-temporal multi-granularity in the entire video sequence, in which the graph vertices representing regional features and hyperedges denoting relationships. Dynamic hypergraph propagation containing the re- planning module and the hyperedge elimination module is proposed to better integrate features among vertices. Feature aggregation and attention mechanisms are also adopted to obtain a better video representation for person Re-ID. Experiments show that the proposed method performs significantly better than the state-of-the-art on three video-based person Re-ID datasets, including iLIDS-VID, PRID-2011, and MARS.

Tuple-generating dependencies (TGDs or existential rules) are an expressive constraint language for ontology-mediated query answering and thus query answering is of high complexity. Existing systems based on first-order rewriting methods can lead to queries too large for DBMS to handle. It is shown that datalog rewriting can result in more compact queries, yet previously proposed datalog rewriting methods are mostly inefficient for implementation. In this paper, we fill the gap by proposing an efficient datalog rewriting approach for answering conjunctive queries over TGDs, and identify and combine existing fragments of TGDs for which our rewriting method terminates. We implemented a prototype system Drewer, and experiments show that it is able to handle a wide range of benchmarks in the literature. Moreover, Drewer shows superior performance over state-of-the-art systems on both the compactness of rewriting and the efficiency of query answering.

Learning linear temporal logic on finite traces (LTLf) formulae aims to learn a target formula that characterizes the high-level behavior of a system from observation traces in planning. Existing approaches to learning LTLf formulae, however, can hardly learn accurate LTLf formulae from noisy data. It is challenging to design an efficient search mechanism in the large search space in form of arbitrary LTLf formulae while alleviating the wrong search bias resulting from noisy data. In this paper, we tackle this problem by bridging LTLf inference to GNN inference. Our key theoretical contribution is showing that GNN inference can simulate LTLf inference to distinguish traces. Based on our theoretical result, we design a GNN-based approach, GLTLf, which combines GNN inference and parameter interpretation to seek the target formula in the large search space. Thanks to the non-deterministic learning process of GNNs, GLTLf is able to cope with noise. We evaluate GLTLf on various datasets with noise. Our experimental results confirm the effectiveness of GNN inference in learning LTLf formulae and show that GLTLf is superior to the state-of-the-art approaches.

Configuration checking (CC) has been confirmed to alleviate the cycling problem in local search for combinatorial optimization problems (COPs). When using CC heuristics in local search for graph problems, a critical concept is the configuration of the vertices. All existing CC variants employ either 1- or 2-level neighborhoods of a vertex as its configuration. Inspired by the idea that neighborhoods with different levels should have different contributions to solving COPs, we propose the probabilistic configuration (PC), which introduces probabilities for neighborhoods at different levels to consider the impact of neighborhoods of different levels on the CC strategy. Based on the concept of PC, we first propose probabilistic configuration checking (PCC), which can be developed in an automated and lightweight favor. We then apply PCC to two classic COPs which have been shown to achieve good results by using CC, and our preliminary results confirm that PCC improves the existing algorithms because PCC alleviates the cycling problem.

Cross-lingual natural language inference (XNLI) is a fundamental task in cross-lingual natural language understanding.Recently this task is commonly addressed by pre-trained cross-lingual language models.Existing methods usually enhance pre-trained language models with additional data, such as annotated parallel corpora.These additional data, however, are rare in practice, especially for low-resource languages.Inspired by recent promising results achieved by prompt-learning, this paper proposes a novel prompt-learning based framework for enhancing XNLI.It reformulates the XNLI problem to a masked language modeling problem by constructing cloze-style questions through cross-lingual templates.To enforce correspondence between different languages, the framework augments a new question for every question using a sampled template in another language and then introduces a consistency loss to make the answer probability distribution obtained from the new question as similar as possible with the corresponding distribution obtained from the original question.Experimental results on two benchmark datasets demonstrate that XNLI models enhanced by our proposed framework significantly outperform original ones under both the full-shot and few-shot cross-lingual transfer settings.

Linear temporal logic over finite traces (LTLf) satisfiability checking is a fundamental and hard (PSPACE-complete) problem in the artificial intelligence community. We explore teaching end-to-end neural networks to check satisfiability in polynomial time. It is a challenge to characterize the syntactic and semantic features of LTLf via neural networks. To tackle this challenge, we propose LTLfNet, a recursive neural network that captures syntactic features of LTLf by recursively combining the embeddings of sub-formulae. LTLfNet models permutation invariance and sequentiality in the semantics of LTLf through different aggregation mechanisms of sub-formulae. Experimental results demonstrate that LTLfNet achieves good performance in synthetic datasets and generalizes across large-scale datasets. They also show that LTLfNet is competitive with state-of-the-art symbolic approaches such as nuXmv and CDLSC.

Linear temporal logic (LTL) satisfiability checking is a fundamental and hard (PSPACE-complete) problem. In this paper, we explore checking LTL satisfiability via end-to-end learning, so that we can take only polynomial time to check LTL satisfiability. Existing approaches have shown that it is possible to leverage end-to-end neural networks to predict the Boolean satisfiability problem with performance considerably higher than random guessing. Inspired by these approaches, we study two interesting questions: can end-to-end neural networks check LTL satisfiability, and can neural networks capture the semantics of LTL? To this end, we train different neural networks for keeping three logical properties of LTL, i.e., recursive property, permutation invariance, and sequentiality. We demonstrate that neural networks can indeed capture some effective biases for checking LTL satisfiability. Besides, designing a special neural network keeping the logical properties of LTL can provide a better inductive bias. We also show the competitive results of neural networks compared with state-of-the-art approaches, i.e., nuXmv and Aalta, on large scale datasets.

Although a number of studies are devoted to novel category discovery, most of them assume a static setting where both labeled and unlabeled data are given at once for finding new categories. In this work, we focus on the application scenarios where unlabeled data are continuously fed into the category discovery system. We refer to it as the {\bf Continuous Category Discovery} ({\bf CCD}) problem, which is significantly more challenging than the static setting. A common challenge faced by novel category discovery is that different sets of features are needed for classification and category discovery: class discriminative features are preferred for classification, while rich and diverse features are more suitable for new category mining. This challenge becomes more severe for dynamic setting as the system is asked to deliver good performance for known classes over time, and at the same time continuously discover new classes from unlabeled data. To address this challenge, we develop a framework of {\bf Grow and Merge} ({\bf GM}) that works by alternating between a growing phase and a merge phase: in the growing phase, it increases the diversity of features through a continuous self-supervised learning for effective category mining, and in the merging phase, it merges the grown model with a static one to ensure satisfying performance for known classes. Our extensive studies verify that the proposed GM framework is significantly more effective than the state-of-the-art approaches for continuous category discovery.

Social relation extraction (SRE for short), which aims to infer the social relation between two people in daily life, has been demonstrated to be of great value in reality. Existing methods for SRE consider extracting social relation only from unimodal information such as text or image, ignoring the high coupling of multimodal information. Moreover, previous studies overlook the serious unbalance distribution on social relations. To address these issues, this paper proposes FL-MSRE, a few-shot learning based approach to extracting social relations from both texts and face images. Considering the lack of multimodal social relation datasets, this paper also presents three multimodal datasets annotated from four classical masterpieces and corresponding TV series. Inspired by the success of BERT, we propose a strong BERT based baseline to extract social relation from text only. FL-MSRE is empirically shown to outperform the baseline significantly. This demonstrates that using face images benefits text-based SRE. Further experiments also show that using two faces from different images achieves similar performance as from the same image. This means that FL-MSRE is suitable for a wide range of SRE applications where the faces of two people can only be collected from different images.

Hai Wan, Haicheng Chen, Jianfeng Du, Weilin Luo, Rongzhen Ye. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

This paper presents a view-guided solution for the task of point cloud completion. Unlike most existing methods directly inferring the missing points using shape priors, we address this task by introducing ViPC (view-guided point cloud completion) that takes the missing crucial global structure information from an extra single-view image. By leveraging a framework that sequentially performs effective cross-modality and cross-level fusions, our method achieves significantly superior results over typical existing solutions on a new large-scale dataset we collect for the view-guided point cloud completion task.

Schedule scheme is essential for real-time Ethernet. Due to the inevitable change of network configurations, the solution requires to be incrementally scheduled in a timely manner. Solver-based methods are time-consuming, while handcrafted scheduling heuristics require domain knowledge and professional expertise, and their application scenarios are usually limited. Instead of designing heuristic strategy manually, we propose TTDeep, a deep reinforcement learning schedule framework, to incrementally schedule Time-Triggered (TT) flows and adapt to various topologies. Our novel framework includes 3 key designs: a period layer to capture the periodical transmission nature of TT flows, the graph neural network to extract and represent topology features, and a 3-step selection paradigm to alleviate the huge action search space issue. Comprehensive experiments show that TTDeep can schedule TT flows much faster than solver-based methods and schedule nearly twice more TT flows on average compared to handcrafted heuristics.

Time-sensitive networking (TSN) is a deterministic network, where failures will seriously affect the quality of the real-time data transmission service. Hence, fault localization is critical in TSN. In the application domain of TSN, an ideal link failure detection method needs to have properties including execution time deterministic, low detection traffic overhead, multi-point fault detection capability for arbitrary typologies. However, current state-of-the-art fault detection algorithms can not achieve these properties simultaneously. In this paper, we propose a Boolean network tomography-based multi-point fault detection method that leverages the deterministic transmission mechanism of TSN to guarantee that the detection time is upper bounded. The method includes an offline preparation phase and an online operation phase. In the preparation phase, we use a detection flow generation algorithm to get a set of detection flows that can identify up to$K$faults with as few paths as possible. In the operation phase, detection packets are realized as time-sensitive flows routing along the detection paths. They are sent periodically to the controller which performs a topology discovery algorithm to infer the faulty links based on the arrival status of each detection packet. Comprehensive experiments are conducted and the results show that compared with existing fault detection methods, the proposed algorithm can accurately identify multiple faulty links in deterministic time, and the generated detection paths set needs fewer paths than the prior methods.

Prime compilation aims to generate all prime implicates/implicants of a Boolean formula. Recently, prime compilation of non-clausal formulae has received great attention. Since it is hard for$\Sigma_{2}^{P}$, existing methods have performance issues. We argue that the main performance bottleneck stems from enlarging the search space using dual rail (DR) encoding, and computing a minimal clausal formula as a by-product. To deal with the issue, we propose a two-phase approach, namely CoAPI, for prime compilation of non-clausal formulae. Thanks to the two-phase framework, we construct a clausal formula without using DR encoding. In addition, to improve performance, the key in our work is a novel bounded prime extraction (BPE) method that, interleaving extracting prime implicates with extracting small implicates, enables constructing a succinct clausal formula rather than a minimal one. Following the assessment way of the state-of-the-art (SOTA) work, we show that CoAPI achieves SOTA performance. Particularly, for generating all prime implicates, CoAPI is up to about one order of magnitude faster. Moreover, we evaluate CoAPI on a benchmark sourcing from real-world industries. The results also confirm the outperformance of CoAPI11Our code and benchmarks are publicly available at https://github.com/LuoWeiLinWillam/CoAPI.

Time-triggered (TT) communication has long been studied in various industrial domains. The most challenging task of TT communication is to find a feasible schedule table. Network changes are inevitable due to the topology dynamics, varying data transmission requirements, etc. Once changes occur, the schedule table needs to be re-calculated in a timely manner. Solver-based methods and heuristic-based methods were proposed to solve this problem. However, solver-based methods employ integer linear programming (ILP) or satisfiability modulo theories (SMT) which have high computational complexity. On the other hand, heuristic-based methods are fast, but they need to be handcrafted based on the application characteristics. Thus, these methods are not general enough to work in complex scenarios especially in large networks.In this paper we propose DRLS – Deep Reinforcement Learning based TT Scheduling method. DRLS first trains an application or network specific scheduling agent offline. Then, the agent can be used for online scheduling of TT flows. However, off-the-shelf reinforcement learning techniques cannot handle the TT scheduling problem with typical complexity and scale. DRLS provides novel solutions to this challenge, including three key innovations: new representations for TT network adapted to various topologies, proper deep neural network (DNN) structures to capture network characteristics, and scalable reinforcement learning (RL) models to handle online TT scheduling. Comprehensive experiments have been conducted to compare the performance of DRLS and other methods (heuristics-based methods such as HLS, LS, HLD + LD, LS + LD, and ILP-based method). The results show that DRLS can not only adapt to specific network topologies, but also have better performance: runs much faster than ILP solver-based methods, and schedules about 23.9% more flows than traditional handcrafted heuristic-based methods.

The boundary conditions (BCs) have shown great potential in requirements engineering because a BC captures the particular combination of circumstances, i.e., divergence, in which the goals of the requirement cannot be satisfied as a whole. Existing researches have attempted to automatically identify lots of BCs. Unfortunately, a large number of identified BCs make assessing and resolving divergences expensive. Existing methods adopt a coarse-grained metric, generality, to filter out less general BCs. However, the results still retain a large number of redundant BCs since a general BC potentially captures redundant circumstances that do not lead to a divergence. Furthermore, the likelihood of BC can be misled by redundant BCs resulting in costly repeatedly assessing and resolving divergences. In this paper, we present a fine-grained metric to filter out the redundant BCs. We first introduce the concept of contrasty of BC. Intuitively, if two BCs are contrastive, they capture different divergences. We argue that a set of contrastive BCs should be recommended to engineers, rather than a set of general BCs that potentially only indicates the same divergence. Then we design a post-processing framework (PPFc) to produce a set of contrastive BCs after identifying BCs. Experimental results show that the contrasty metric dramatically reduces the number of BCs recommended to engineers. Results also demonstrate that lots of BCs identified by the state-of-the-art method are redundant in most cases. Besides, to improve efficiency, we propose a joint framework (JFc) to interleave assessing based on the contrasty metric with identifying BCs. The primary intuition behind JFc is that it considers the search bias toward contrastive BCs during identifying BCs, thereby pruning the BCs capturing the same divergence. Experiments confirm the improvements of JFc in identifying contrastive BCs.

The digital transformation of industry requires industrial control networks provide high flexibility and determinacy. Time-sensitive software-defined networking that combines time-sensitive networking and software-defined networking is a new network paradigm which provides both real-time transmission feature and network flexibility. During network updates, the transmission consistency needs to be maintained. However, previous mechanisms mostly target on the proper schedule transition, which cannot guarantee no frame loss and also introduces extra update overhead. The article proposes a novel flow schedule generation model which guarantees no frame loss during network updates even with the basic two-phase update mechanism and introduces no extra update overhead. Two algorithms are designed for the model to adapt to different application scenarios: the offline algorithm poses better schedulability, whereas the online one consumes less time with slightly decreased schedulability. The experiments on two real-world industrial networks demonstrate our mechanism achieves zero frame loss without extra update overhead compared to existing methods, and the online algorithm saves 40% execution time with at most 10% schedulability decrease when the bandwidth utilization is less than 50%.

Fault tree analysis (FTA) is a prominent reliability analysis method, which is widely used in safety-critical industries. Computing the minimal cut sets (MCSs) of a fault tree, i.e., finding all the smallest combinations of the basic events that cause system failures, is a fundamental step in FTA. Since coherent fault trees are the most common in industrial systems in practice, they are the focus of this article. Computing MCSs is a computationally hard problem. Classical methods have been proposed based on manipulation of Boolean expressions and binary decision diagrams. However, given the inherent intractability of computing MCSs in practice, there are still limitations on time and memory in these methods. Therefore, developing new methods over different paradigms remains to be an interesting research direction. In this article, motivated by recent progress on modern Boolean satisfiability problem (SAT) solvers, we present a new method for computing MCSs based on SAT, namely SATMCS. Specifically, given a fault tree, we iteratively search for a cut set based on the conflict-driven clause learning framework. By exploiting local propagation graph, which characterizes the partial failure propagation based on the cut set, we provide efficient algorithms for extracting an MCS. The new MCS is learned as a block clause for SAT solving, and the conflict clauses in iterations are incrementally recorded, which helps to prune search space and ensures completeness of the results. Moreover, we adopt a jump-chronological backtracking strategy to prepare the next iteration, which allows for reusing the same search steps in SAT solving. We compare SATMCS with state-of-the-art commercial tools on practical fault trees. Although SATMCS is only a prototype, it shows comparable performance in time consumption with one tool (XFTA), and in various cases, it outperforms the others (FaultTree+ and Commander). Besides, SATMCS exhibits much better performance on memory usage than these tools. Specifically, SATMCS consumes about one order of magnitude less memory usage in most instances.

The Maximum k-plex Problem is an important combinatorial optimization problem with increasingly wide applications. In this paper, we propose a novel strategy, named Dynamic-threshold Configuration Checking (DCC), to reduce the cycling problem of local search. Due to the complicated neighborhood relations, all the previous local search algorithms for this problem spend a large amount of time in identifying feasible neighbors in each step. To further improve the performance on dense and challenging instances, we propose Double-attributes Incremental Neighborhood Updating (DINU) scheme which reduces the worst-case time complexity per iteration from O(|V|⋅ΔG) to O(k · Δ‾G). Based on DCC strategy and DINU scheme, we develop a local search algorithm named DCCplex. According to the experiment result, DCCplex shows promising result on DIMACS and BHOSLIB benchmark as well as real-world massive graphs. Especially, DCCplex updates the lower bound of the maximum k-plex for most dense and challenging instances.

Aspect-based sentiment analysis (ABSA) aims to detect the targets (which are composed by continuous words), aspects and sentiment polarities in text. Published datasets from SemEval-2015 and SemEval-2016 reveal that a sentiment polarity depends on both the target and the aspect. However, most of the existing methods consider predicting sentiment polarities from either targets or aspects but not from both, thus they easily make wrong predictions on sentiment polarities. In particular, where the target is implicit, i.e., it does not appear in the given text, the methods predicting sentiment polarities from targets do not work. To tackle these limitations in ABSA, this paper proposes a novel method for target-aspect-sentiment joint detection. It relies on a pre-trained language model and can capture the dependence on both targets and aspects for sentiment prediction. Experimental results on the SemEval-2015 and SemEval-2016 restaurant datasets show that the proposed method achieves a high performance in detecting target-aspect-sentiment triples even for the implicit target cases; moreover, it even outperforms the state-of-the-art methods for those subtasks of target-aspect-sentiment detection that they are competent to.

Hierarchical Task Network (HTN) planning is showing its power in real-world planning. Although domain experts have partial hierarchical domain knowledge, it is time-consuming to specify all HTN methods, leaving them incomplete. On the other hand, traditional HTN learning approaches focus only on declarative goals, omitting the hierarchical domain knowledge. In this paper, we propose a novel learning framework to refine HTN methods via task insertion with completely preserving the original methods. As it is difficult to identify incomplete methods without designating declarative goals for compound tasks, we introduce the notion of prioritized preference to capture the incompleteness possibility of methods. Specifically, the framework first computes the preferred completion profile w.r.t. the prioritized preference to refine the incomplete methods. Then it finds the minimal set of refined methods via a method substitution operation. Experimental analysis demonstrates that our approach is effective, especially in solving new HTN planning instances.

In recent years, with the explosion of information on the Internet, there has been a large amount of data produced, and analyzing these data is useful and has been widely employed in real world applications. Since data labeling is costly, lots of research has focused on how to efficiently label data through semi-supervised learning. Among the methods, graph and hypergraph based label propagation algorithms have been a widely used method. However, traditional hypergraph learning methods may suffer from their high computational cost. In this paper, we propose a Hypergraph Label Propagation Network (HLPN) which combines hypergraph-based label propagation and deep neural networks in order to optimize the feature embedding for optimal hypergraph learning through an end-to-end architecture. The proposed method is more effective and also efficient for data labeling compared with traditional hypergraph learning methods. We verify the effectiveness of our proposed HLPN method on a real-world microblog dataset gathered from Sina Weibo. Experiments demonstrate that the proposed method can significantly outperform the state-of-the-art methods and alternative approaches.

In goal-oriented requirements engineering, goal conflict identification is of fundamental importance for requirements analysis. The task aims to find the feasible situations which make the goals diverge within the domain, called boundary conditions (BCs). However, the existing approaches for goal conflict identification fail to find sufficient BCs and general BCs which cover more combinations of circumstances. From the BCs found by these existing approaches, we have observed an interesting phenomenon that there are some pairs of BCs are similar in formula structure, which occurs frequently in the experimental cases. In other words, once a BC is found, a new BC may be discovered quickly by slightly changing the former. It inspires us to develop a local search algorithm named LOGION to find BCs, in which the structural similarity is captured by the neighborhood relation of formulae. Based on structural similarity, LOGION can find a lot of BCs in a short time. Moreover, due to the large number of BCs identified, it potentially selects more general BCs from them. By taking experiments on a set of cases, we show that LOG I ON effectively exploits the structural similarity of BCs. We also compare our algorithm against the two state-of-the-art approaches. The experimental results show that LOGION produces one order of magnitude more BCs than the state-of-the-art approaches and confirm that LOGION finds out more general BCs thanks to a large number of BCs.

Very Fast Decision Tree (VFDT) is one of the most widely used online decision tree induction algorithms, and it provides high classification accuracy with theoretical guarantees. In VFDT, the split-attempt operation is essential for leaf-split. It is computation-intensive since it computes the heuristic measure of all attributes of a leaf. To reduce split-attempts, VFDT tries to split at constant intervals (for example, every 200 examples). However, this mechanism introduces split-delay for split can only happen at fixed intervals, which slows down the growth of VFDT and finally lowers accuracy. To address this problem, we first devise an online incremental algorithm that computes the heuristic measure of an attribute with a much lower computational cost. Then a subset of attributes is carefully selected to find a potential split timing using this algorithm. A split-attempt will be carried out once the timing is verified. By the whole process, computational cost and split-delay are lowered significantly. Comprehensive experiments are conducted using multiple synthetic and real datasets. Compared with state-of-the-art algorithms, our method reduces split-attempts by about 5 to 10 times on average with much lower split-delay, which makes our algorithm run faster and more accurate.

Existential rules are an expressive ontology formalism for ontology-mediated query answering and thus query answering is of high complexity, while several tractable fragments have been identified. Existing systems based on first-order rewriting methods can lead to queries too large for DBMS to handle. It is shown that datalog rewriting can result in more compact queries, yet previously proposed datalog rewriting methods are mostly inefficient for implementation. In this paper, we fill the gap by proposing an efficient datalog rewriting approach for answering conjunctive queries over existential rules, and identify and combine existing fragments of existential rules for which our rewriting method terminates. We implemented a prototype system Drewer, and experiments show that it is able to handle a wide range of benchmarks in the literature. Moreover, Drewer shows superior or comparable performance over state-of-the-art systems on both the compactness of rewriting and the efficiency of query answering.

Time-sensitive networking (TSN) is a set of extended standards for the IEEE 802.3 Ethernet under development by the IEEE 802.1 TSN task group. TSN depends on two key components, scheduling and fault tolerance, to provide realtime and reliable transmission. There is a strong motivation to replace the widely used field-buses with TSNs in industrial networking applications. However, industrial network devices are typical application-specific embedded systems with limited memory resources. Time-sensitive (TS) transmission certainly prefers on-chip memory, which is even more scarce for embedded systems. As a result, it is critical for TSNs to develop memory-efficient switching techniques with scalable schedulability and elegant fault-tolerance support. This paper proposes a time-triggered switch-memory-switch (SMS) architecture for memory-efficient TSN switches. First, based on the SMS shared memory, our architecture makes it possible to statically schedule memory allocation with full utilization for TS traffic and the remaining memory for other traffic. Compared with perport memory, the shared memory achieves a ratio of (nn/n!) (≈ (en/√(2πn)), n → ∞), where n is the port number, in the feasible solution space under memory constraints and thus significantly improves scheduling memory ability and flexibility. Moreover, we develop a fault-tolerance scheme for reliable transmission. It facilitates a memory-efficient implementation of the popular multiline redundancy in industrial networks. The scheme is validated by five classes of memory conflicts and a case study on two-line redundancy.

An increasingly important trend in the design of industry-strength embedded systems is the integration of multiple services with varying criticality levels into a common computing platform. Such systems are characterized as mixed-criticality multiservice systems (MCMSs). An MCMS has to survive in rigorous environments posed by industry-level requirements. Such survival, however, is becoming continuously more challenging due to the growing system complexity and integrating more and more services. While existing works typically target reliability-driven design optimization to improve the system robustness rather than deal with the surviving problem of the system in extreme physical environments, this paper addresses the problem by enabling the service capability transitions of an MCMS to adapt to the environments. This paper proposes a service capability model to capture the importance of functional modules for the criticality of different services. A model-based service-capability transition mechanism is designed to automatically identify the maximum allowed service capability under a given physical environment. A case study of the proposed techniques was performed on an industrial Ethernet switch which is a typical MCMS, to validate the capability of adaptation to high and low temperatures. The experimental results demonstrate the significant potential of our approach to improve system survivability under extreme physical environments.

With the development of hardware virtualization and cloud computing, modern industry has a tendency to upgrade from the traditional industrial networks to virtual machine (VM) based networks. To provide firm latency guarantees for control messages in these networks, the time-sensitive network (TSN) is a promising technology due to its determinacy for real-time applications. However, TSN faces the challenge of providing a rapid response to dynamic transmission requirement changes incurred by VM migrations. In this paper, we proposed an online scheduling approach to deal with dynamic VM migrations in multicast TSN. In this approach, we devise a novel online scheduling framework [minimal distance tree (MDT) construction - heuristic breadth first search] containing an offline scheduling phase and an online rescheduling phase. While the offline phase introduces a MDT to increase reusable scheduling results, the online phase proposes a heuristic scheduling approach to reuse the results of the offline phase as much as possible to accelerate the rescheduling process. Experiments show that our framework can provide a rapid response to dynamic VM migrations compared with the existing approaches where the amount of control data does not exceed 50% of the bandwidth.

The Sentential Decision Diagram (SDD) is a compact and canonical representation of Boolean functions that generalizes the Ordered Binary Decision Diagrams (OBDDs). A variant of SDDs, namely Zero-suppressed Sentential Decision Diagrams (ZSDDs), was proposed recently by using different trimming rules. SDDs are suitable for functions where adjacent input assignments have the same outcome, while ZSDDs are more compact for spare functions. In this paper, we introduce a novel canonical SDD variant, called the Tagged Sentential Decision Diagrams (TSDDs). The key insight of TSDDs is to combine both trimming rules of SDDs and ZSDDs. With both characteristics of SDDs and ZSDDs, the TSDD representation is at least as small as the SDD or ZSDD representation for any Boolean functions. This is also shown in our experimental evaluation.

Representation learning and feature aggregation are usually the two key intermediate steps in natural language processing. Despite deep neural networks have shown strong performance in the text classification task, they are unable to learn adaptive structure features automatically and lack of a method for fully utilizing the extracted features. In this paper, we propose a novel architecture that dynamically routes hierarchical structure feature to attentive capsule, named HAC. Specifically, we first adopt intermediate information of a well-designed deep dilated CNN to form hierarchical structure features. Different levels of structure representations are corresponding to various linguistic units such as word, phrase and clause, respectively. Furthermore, we design a capsule module using dynamic routing and equip it with an attention mechanism. The attentive capsule implements an effective aggregation strategy for feature clustering and selection. Extensive results on eleven benchmark datasets demonstrate that the proposed model obtains competitive performance against several state-of-the-art baselines. Our code is available at https://github.com/zhengwsh/HAC.

The execution time of conventional incremental off-line schedule approaches for time-triggered networks increases rapidly when networks become larger. When the traffic in a network changes, they need to reschedule all influenced flows once again. Traffic changes at the cluster level involve many data flows. An incremental scheduler cannot react quickly to such changes. We propose an algorithm based on mixed integer linear programming and counterexample guided methodology. Our algorithm can generate adaptive schedule for cluster-level changes of the system. The adaptive schedule can react quickly to the changes during runtime. Our algorithm enhances the incremental schedulers. It allows schedulers to react to changing at both the flow level and the cluster level. Experiments show that our approach is effective. In the scenarios of coupling train consists, our algorithm can generate the schedule table of the train network within a few seconds.

The emerging momentum of digital transformation of industry, i.e. Industry 4.0, poses strong demands for integrating industrial control networks, and Ethernet to enable the real-time Internet of Things (RT-IoT). Time-triggered (TT) networks provide a cost-efficient integrated solution while RT-IoT arouses the reconfiguration challenges: the network has to be flexible enough to adapt to changes and yet provides deterministic transmission persistently during network reconfiguration. Software defined network benefits the flexible industrial control by configuring the rules handling frames. However, previous reconfiguration mechanisms are mostly oriented to the context of data centers and wide area networks and thus do not consider the deterministic transmission in TT networks. This paper focuses on the reconfiguration (i.e., updates) for the deterministic transmission. To minimize the overhead during updates, namely the minimum number of loss frames and the minimum duration time of updates, we first establish an update theory based on the dependence relationship derived by the conflicts during updates. In addition then the reconfiguration problem is modeled with the dependence graph built by the relationship. On such a basis, we present a reconfiguration mechanism and its implementation to solve the problem. Finally, we evaluate the proposed reconfiguration mechanism in two real industrial network topologies. The experimental results demonstrate that compared with previous methods, our mechanism significantly reduces the number of loss frames and achieves zero loss in almost all cases.

In many classification tasks, the misclassification costs of different categories usually vary significantly. Under such circumstances, it is essential to identify the importance of different categories and thus assign different misclassification losses in many applications, such as medical diagnosis, saliency detection and software defect prediction. However, we note that it is infeasible to determine the accurate cost value without great domain knowledge. In most common cases, we may just have the information that which category is more important than the other categories, i.e., the identification of defect-prone softwares is more important than that of defect-free. To tackle these issues, in this paper, we propose a hypergraph learning method with cost interval optimization, which is able to handle cost interval when data is formulated using the high-order relationships. In this way, data correlations are modeled by a hypergraph structure, which has the merit to exploit the underlying relationships behind the data. With a cost-sensitive hypergraph structure, in order to improve the performance of the classifier without precise cost value, we further introduce cost interval optimization to hypergraph learning. In this process, the optimization on cost interval achieves better performance instead of choosing uncertain fixed cost in the learning process. To evaluate the effectiveness of the proposed method, we have conducted experiments on two groups of dataset, i.e., the NASA Metrics Data Program (NASA) dataset and UCI Machine Learning Repository (UCI) dataset. Experimental results and comparisons with state-of-the-art methods have exhibited better performance of our proposed method.

This paper focuses on scene graph completion which aims at predicting new relations between two entities utilizing existing scene graphs and images. By comparing with the well-known knowledge graph, we first identify that each scene graph is associated with an image and each entity of a visual triple in a scene graph is composed of its entity type with attributes and grounded with a bounding box in its corresponding image. We then propose an end-to-end model named Representation Learning via Jointly Structural and Visual Embedding (RLSV) to take advantages of structural and visual information in scene graphs. In RLSV model, we provide a fully-convolutional module to extract the visual embeddings of a visual triple and apply hierarchical projection to combine the structural and visual embeddings of a visual triple. In experiments, we evaluate our model on two scene graph completion tasks: link prediction and visual triple classification, and further analyze by case studies. Experimental results demonstrate that our model outperforms all baselines in both tasks, which justifies the significance of combining structural and visual information for scene graph completion.

While attributes have been widely used for person re-identification (Re-ID) which aims at matching the same person images across disjoint camera views, they are used either as extra features or for performing multi-task learning to assist the image-image matching task. However, how to find a set of person images according to a given attribute description, which is very practical in many surveillance applications, remains a rarely investigated cross-modality matching problem in person Re-ID. In this work, we present this challenge and leverage adversarial learning to formulate the attribute-image cross-modality person Re-ID model. By imposing a semantic consistency constraint across modalities as a regularization, the adversarial learning enables to generate image-analogous concepts of query attributes for matching the corresponding images at both global level and semantic ID level. We conducted extensive experiments on three attribute datasets and demonstrated that the regularized adversarial modelling is so far the most effective method for the attribute-image cross-modality person Re-ID problem.

Recent years witnessed a fast growing popularity of mixed-criticality real-time applications on smart devices. Priority schedulers are typically the central component to provide differential quality of service (QoS) for mixed-criticality tasks. The increasing deployment of such applications on smart devices, however, poses new challenges for the design of effective schedulers. First, the scheduling algorithms for mixed-criticality tasks are generally NP-complete. Second, the scheduling algorithms have to be effective enough under the limited computing resource of smart devices. This paper presents a work-in-progress report on a novel technique to design efficient and effective mixed-criticality schedulers. We propose a flattened priority framework to transform a non-priority scheduler into a priority one. The framework is typically a iterative framework based on feedback loops. Given an optimal nonpriority scheduler, for P priorities, the transformed scheduler converges with P iterations in the worst case. With the proposed framework, the design of priority schedulers is simplified into the design of non-priority schedulers. Such a simplification dramatically lowers the design effort and system complexity. A case study was performed on FPGA-based Industrial Ethernet switches. The proposed method achieves a 30%~50% reduction in the usage of look-up tables (LUTs) without performance loss.

TBox abduction explains why an observation is not entailed by a TBox, by computing multiple sets of axioms, called explanations, such that each explanation does not entail the observation alone while appending an explanation to the TBox renders the observation entailed but does not introduce incoherence. Considering that practical explanations in TBox abduction are likely to mimic minimal explanations for TBox entailments, we introduce admissible explanations which are subsets of those justifications for the observation that are instantiated from a finite set of justification patterns. A justification pattern is obtained from a minimal set of axioms responsible for a certain atomic concept inclusion by replacing all concept (resp. role) names with concept (resp. role) variables. The number of admissible explanations is finite but can still be so large that computing all admissible explanations is impractical. Thus, we introduce a variant of subset-minimality, written ⊆ds-minimality, which prefers fresh (concept or role) names than existing names. We propose efficient methods for computing all admissible ⊆ds-minimal explanations and for computing all justification patterns, respectively. Experimental results demonstrate that combining the proposed methods is able to achieve a practical approach to TBox abduction.

In recent years, multi-agent epistemic planning has received attention from both dynamic logic and planning communities. Existing implementations of multi-agent epistemic planning are based on compilation into classical planning and suffer from various limitations, such as generating only linear plans, restriction to public actions, and incapability to handle disjunctive beliefs. In this paper, we propose a general representation language for multi-agent epistemic planning where the initial KB and the goal, the preconditions and effects of actions can be arbitrary multi-agent epistemic formulas, and the solution is an action tree branching on sensing results.To support efficient reasoning in the multi-agent KD45 logic, we make use of a normal form called alternative cover disjunctive formula (ACDF). We propose basic revision and update algorithms for ACDF formulas. We also handle static propositional common knowledge, which we call constraints. Based on our reasoning, revision and update algorithms, adapting the PrAO algorithm for contingent planning from the literature, we implemented a multi-agent epistemic planner called MAEP. Our experimental results show the viability of our approach.

3D object classification with multi-view representation has become very popular, thanks to the progress on computer techniques and graphic hardware, and attracted much research attention in recent years. Regarding this task, there are mainly two challenging issues, i.e., the complex correlation among multiple views and the possible imbalance data issue. In this work, we propose to employ the hypergraph structure to formulate the relationship among 3D objects, taking the advantage of hypergraph on high-order correlation modelling. However, traditional hypergraph learning method may suffer from the imbalance data issue. To this end, we propose a vertex-weighted hypergraph learning algorithm for multi-view 3D object classification, introducing an updated hypergraph structure. In our method, the correlation among different objects is formulated in a hypergraph structure and each object (vertex) is associated with a corresponding weight, weighting the importance of each sample in the learning process. The learning process is conducted on the vertex-weighted hypergraph and the estimated object relevance is employed for object classification. The proposed method has been evaluated on two public benchmarks, i.e., the NTU and the PSB datasets. Experimental results and comparison with the state-of-the-art methods and recent deep learning method demonstrate the effectiveness of our proposed method.

We extend hierarchical task network planning with task insertion (TIHTN) by introducing state constraints, called TIHTNS. We show that just as for TIHTN planning, all solutions of the TIHTNS planning problem can be obtained by acyclic decomposition and task insertion, entailing that its plan-existence problem is decidable without any restriction on decomposition methods. We also prove that the extension by state constraints does not increase the complexity of the plan-existence problem, which stays 2-NEXPTIME-complete, based on an acyclic progression operator. In addition, we show that TIHTNS planning covers not only the original TIHTN planning but also hierarchy-relaxed hierarchical goal network planning.

While trains traditionally relied on field bus to support real-time control applications, next-generation trains are moving toward Ethernet as an integrated, high-bandwidth communication infrastructure for real-time control and best-effort consumer traffic. Time-Triggered Ethernet (TT-Ethernet) is a promising technology for train networks because of its capability to achieve deterministic latencies for real-time applications based on pre-computed transmission schedules. However, the deterministic scheduling approach of TT-Ethernet faces significant challenges in handling scheduling uncertainties caused by switch failures and legacy end devices in train networks. Due to the physical constraints on trains, train networks deal with switch failures by bypassing failed switches using a short circuiting mechanism. Unfortunately, this mechanism incurs scheduling errors as frames bypassing the failed switch may arrive ahead of the pre-computed schedule, resulting in early, unexpected, and out of order arrivals. Furthermore, as trains evolve from traditional communication technologies to TT-Ethernet, the network must support legacy end devices that may generate frames at times unknown to the TT-Ethernet. We propose a novel traffic shaping approach to deal with scheduling uncertainties in TT-Ethernet. The traffic shaper of a TT-Ethernet switch buffers early frames and then releases them at their pre-scheduled arrive time. Furthermore, we devise an efficient buffer management method for the traffic shaper in face of fault scenarios. Finally, we use the traffic shaper to integrate legacy devices into TT-Ethernet. We have implemented the traffic shaping approach in a 24-port TT-Ethernet switch specifically designed for train networks. Experiments show the traffic shaping strategy can effectively deal with scheduling uncertainties incurred by switch failures and legacy devices.

Classical inconsistency-tolerant query answering relies on selecting maximal components of an ABox/database which are consistent with the ontology. However, some rules in ontologies might be unreliable if they are extracted from ontology learning or written by unskillful knowledge engineers. In this paper we present a framework of handling inconsistent existential rules under stable model semantics, which is defined by a notion called rule repairs to select maximal components of the existential rules. Surprisingly, for R-acyclic existential rules with R-stratified or guarded existential rules with stratified negations, both the data complexity and combined complexity of query answering under the rule repair semantics remain the same as that under the conventional query answering semantics. This leads us to propose several approaches to handle the rule repair semantics by calling answer set programming solvers. An experimental evaluation shows that these approaches have good scalability of query answering under rule repairs on realistic cases.

Explanatory diagnosis of an ontology stream aims to explain the changes hidden in the ontology stream by a sequence of actions. In this paper, we present a framework for explanatory diagnosis of an ontology stream, which allows the actions to be uncertain. In order to capture the semantics of actions, we introduce a new update operator and effect-guided bold-repair. By combining these operators with a query mechanism of description logicssupporting inconsistency-tolerant semantics, we present a formal definition for the explanatory diagnosis problem of ontology streams.

Lifschitz and Turner introduced the notion of the splitting set and provided a method to divide a logic program into two parts. They showed that the task of computing the answer sets of the program can be converted into the tasks of computing the answer sets of these parts. However, the empty set and the set of all atoms are the only two splitting sets for many programs, then these programs cannot be divided by the splitting method. In this paper, we extend Lifschitz and Turner's splitting set theorem to allow the program to be split by an arbitrary set of atoms, while some new atoms may be introduced in the process. To illustrate the usefulness of the result, we show that for some typical programs the splitting process is efficient and the program simplification problem can be investigated using the concept of splitting.

This paper proposes an alternative definition of elementary loops and extends the notion of proper loops for disjunctive logic programs. Different from normal logic programs, the computational complexities of recognizing elementary loops and proper loops for disjunctive programs are coNP-complete. To address this problem, we introduce weaker versions of both elementary loops and proper loops and provide polynomial time algorithms for identifying them respectively. On the other hand, based on the notion of elementary loops, the class of Head-Elementary-loop-Free (HEF) programs was presented, which can be turned into equivalent normal logic programs by shifting head atoms into bodies. However, the problem of recognizing an HEF program is coNP-complete. Then we present a subclass of HEF programs which generalizes the class of Head-Cycle-Free programs and provide a polynomial time algorithm to identify them. At last, some experiments show that both elementary loops and proper loops could be replaced by their weak versions in practice.

We study the problem of jointly embedding a knowledge base and a text corpus.The key issue is the alignment model making sure the vectors of entities, relations and words are in the same space.Wang et al. (2014a) rely on Wikipedia anchors, making the applicable scope quite limited.In this paper we propose a new alignment model based on text descriptions of entities, without dependency on anchors.We require the embedding vector of an entity not only to fit the structured constraints in KBs but also to be equal to the embedding vector computed from the text description.Extensive experiments show that, the proposed approach consistently performs comparably or even better than the method of Wang et al. (2014a), which is encouraging as we do not use any anchor information.

The notions of loops and loop formulas play an important role in answer set computation. However, there would be an exponential number of loops in the worst case. Gebser and Schaub characterized a subclass elementary loops and showed that they are sufficient for selecting answer sets from models of a logic program. This paper proposes an alternative definition of elementary loops and identify a subclass of elementary loops, called proper loops. By applying a special form of their loop formulas, proper loops are also sufficient for the SAT-based answer set computation. A polynomial algorithm to recognize a proper loop is given and shows that for certain logic programs, identifying all proper loops of a program is more efficient than that of elementary loops. Furthermore, we prove that, by considering the structure of the positive body-head dependency graph of a program, a large number of loops could be ignored for identifying proper loops. We provide another algorithm for identifying all proper loops of a program. The experiments show that, for certain programs whose dependency graphs consisting of sets of components that are densely connected inside and sparsely connected outside, the new algorithm is more efficient.

This paper focuses on computing general first-order parallel and prioritized circumscription with varying constants. We propose linear translations from general first-order circumscription to first-order theories under stable model semantics over arbitrary structures, including Tr_v for parallel circumscription and Tr^s_v for conjunction of parallel circumscriptions (further for prioritized circumscription). To improve the efficiency, we give an optimization \Gamma_{\exists} to reduce logic programs in size when eliminating existential quantifiers during the translations. Based on these results, a general first-order circumscription solver, named cfo2lp, is developed by calling answer set programming (ASP) solvers. Using circuit diagnosis problem and extended stable marriage problem as benchmarks, we compare cfo2lp with a propositional circumscription solver circ2dlp and an ASP solver with complex optimization metasp on efficiency. Experimental results demonstrate that for problems represented by first-order circumscription naturally and intuitively, cfo2lp can compute all solutions over finite structures. We also apply our approach to description logics with circumscription and repairs in inconsistent databases, which can be handled effectively.

In many reactive systems, programs run cyclically. In each cycle, they check the current status and handle the business for a single step. The business logic has to be blasted to pieces, which violates the way that people are used to. Cyclic programs are difficult to develop and their reliability is hard to guarantee. To tackle these problems, we propose a model-based formal design flow which is more rigorous and rapid than the V-model. Our method consists of three phases: modeling, verification and code synthesis. In the modeling phase, BIP (Behavior-Interaction-Priority) language, which is expressive and allows flexible modeling, is used as the modeling language. Real-time behavior, that is highly concerned in reactive systems, can be modeled as well. In the verification phase, the system model is translated to timed automata and checked by Uppaal. Verification helps to ensure the correctness of the model. In the code synthesis phase, the software part of the system model is synthesized to cyclic code. We propose an algorithm which can generate high-performance cyclic code from a model which describes the business work-flow. This feature significantly simplifies program development. A set of tools is implemented to support our design flow and they are successfully applied to an industrial case study for a PLC (Programmable Logic Controller) system which is used to control several physical devices in a huge palace.

Large-scale systems are often modeled and verified in a component-based way. BIP (Behavior, Interaction, Priority) is a flexible component-based framework which supports hierarchical design of heterogeneous systems. BIP components interact via connectors in which data can be passed among multiple components. It also support the modeling of time. Due to its expressiveness and flexibility, many real-time systems can be modeled easily in BIP. Verification, however, is not well supported in the current BIP framework. That is a major disadvantage when it is used in a model-driven design flow. To fill this gap, we propose a translation from slightly restricted BIP models to timed automata. Then model checking can be applied to the latter using Uppaal (which is a sophisticated model checker for timed automata). The correctness of translation is proven formally and the translation is implemented as a tool Bip2Uppaal. Three industrial case studies show that our approach is practical and effective.

With the rapid development of economic globalization and informationization, the Chinese e-government is still in its adolescence with a long way ahead. Based on some recent research in Guangdong province, we find that e-government affair systems play important roles therein and represent a certain kind of application called Form-centered Application Systems (FAS). After much investigation and analysis on e-government's background, daily routine and regulations, we summarize some rules and disciplines of its business process modeling, based on which we characterize requirements of FAS. Though currently many process modeling approaches or techniques have been proposed and widely used, they can not fully and easily meet the special needs. In this paper, we introduce a new business process model called Double-State Based Business Process Description Model (DSBPDM), which is composed of Business Process Model (BPM) and Dispatching Model (DM), where BPM enriches Finite State Machine (FSM) Model by three constraint checks, business logic and message passing, whereas DM delineates the dispatching and executing status of the business object in its lifetime. After presenting DSBPDM's formal definition, we discuss the essence of process forwarding by deducing its operational semantics formally. In this way, key issues such as explicit state and operation representation, rigorous constraint expression, complex authorization check, and full picture of the dispatching and executing of business objects are nicely tackled. Our practice shows that building FAS system with DSBPDM and its supporting platform fits the requirements well, provides an open and transparent view of business process, satisfies the needs of the public and officials, and helps to get a comprehensive insight into the meaning of business process forwarding.

Eliciting and describing complex business process consistently and unambiguously is important and critical for migrating complex business processes to cloud platform. Mspoa(Subject Predicate Object Adverbial complex business process description Meta-model) is proposed in this paper, which can represent the static relationship in business process description problem space. Based on Mspoa, clewed and cored by form business process, CBPM (Complex Business Process Model) is presented to describe dynamic behavior relationship. By the means of the migration steps described in this paper, incoherence and bounce in the course of business processes analysis can be overcome, assuring the correctness of the artifacts.

P2P reasoning system can answer queries from not only each peer's local theory but also some other peers related with sharing part of its vocabulary. This paper concentrates on P2P reasoning technology based on description logic, trying to provide an intelligent solution for searching network resources. A P2P reasoning algorithm suitable for description logic called DL-DeCA is proposed in this paper, as well as its communication protocol and system implementation of DL-P2PRS (description logic P2P reasoning system). Experiment results show that DL-P2PRS can work correctly and effectively.

Programmable logic controllers (PLCs) represent a typical class of embedded software systems. They are widely used in safety-critical industrial applications, such as railways, automotive applications, etc. The paper presents a novel method to specify and verify PLC software systems with the theorem proving system Coq. Dependent inductive data types are harnessed to represent the component specifications. Modular and parameterized specification and verification are proposed. An illustrative example demonstrates the effectiveness of the method.

Programable logic controllers (PLCs) are complex cyber-physical systems which are widely used in industry. This paper presents a robust approach to design and implement PLC-based embedded systems. Timed automata are used to model the controller and its environment. We validate the design model with resort to model checking techniques. We propose an algorithm to generate PLC code from timed automata and implement this algorithm with a prototype tool. This method can condense the developing process and guarantee the correctness of PLC programs. A case study demonstrates the effectiveness of our method.

Though with the rapid development of economic globalization and informationization, Chinese e-government development is still in its infancy with a long way ahead. Based on some resent research on today's e-government in Guangdong, we propose a special model to describe business process in e-government affair operations. The model extends finite state machine model by message passing, business logic and several kinds of constraint check. Using this model to represent governmental business process helps to capture the exact status of each process step, standardize service procedure, describe complex constraint in the process and bring flexibility into its customization, which eventually results in more efficient delivery of services and facilitates greater transparency in the administration of government. Furthermore, it offers new thoughts in representing business process.

Concurrency control strategy is important and necessary to Collaborative Authoring System (CAS) which allows several users to edit a document simultaneously. Locking algorithm adopted in traditional CAS can't achieve excellent concurrency with high performance. In this paper we propose an adaptive-granularity locking algorithm, which determines lock granularity by means of user's operations dynamically. The experiments we have carried out show that our algorithms achieve the concurrency of fine-granularity locking with lower cost.