This paper investigates the use of deep reinforcement learning (DRL) for the control of mobile robot teams within the context of navigation and task-based collaborative scenarios. We apply a DRL policy with a tailored neural network architecture as a solution to control, path planning, and higher-level guidance tasks. Our network architecture was trained using a unique multi-stage curriculum that progresses from single-agent navigation, to multi-agent pathfinding with obstacles, and finally to a complex collaborative firefighting scenario. This structured approach accelerates training convergence by systematically building sophisticated collaborative behaviours upon foundational skills, which enhances training stability and guides the agents towards learning effective and coordinated strategies The policy evaluation was conducted in both simulation and hybrid simulation-physical demonstrations utilising a real unmanned ground vehicle (UGV). The policy presented is capable of achieving multi-agent navigation tasks with a 95.83% accuracy in our testing environments, and has demonstrated emergent multi-agent behaviours. In more complex collaborative firefighting scenarios, the policy also demonstrated superior performance than baselines in reaching goals, e.g., navigating and extinguishing two fires with a 99.67% success rate, suggesting its strong potential for real-world deployment.

The connections between symbolic rules and neural networks have been explored in various directions, including rule mining through neural networks and rule-based explanation for neural networks. These approaches allow symbolic rules to be extracted from neural network models, which offers explainability to the models. However, the plausibility of the extracted rules is rarely analysed. In this paper, we show that the confidence degrees of extracted rules are generally not high, and we propose a new family of Graph Neural Networks that can be trained with the guidance of rules. Hence, the inference of our model simulates the rule reasoning. Moreover, rules with high confidence degrees can be extracted from the trained model that aligns with the inference of the model, which verifies the effectiveness of the rule guidance. Experimental evaluation of knowledge graph reasoning tasks further demonstrates the effectiveness of our model.

Complex Query Answering over incomplete knowledge graphs is a fundamental yet challenging task. Existing methods based on a pretrained knowledge graph embedding model have achieved good performance. However, they ignore logical rules. Logical rules, as part of the conceptual layer in knowledge graphs, contain rich background information that enhances logical reasoning and improves the performance of models. To address this problem, we propose a model that incorporates logical rules for complex query answering over knowledge graphs called R-CQA (Complex Query Answering with Rules). This model introduces implicit and explicit rule injection modules to the existing CQA models. The implicit rule injection module models logical rules as additional data for training and incorporates rule information into knowledge graph embedding model, which enhances inference. The explicit rule injection module uses logical rules to rewrite queries and constructs a query set for each original query, which avoids missing answers for inference. However, implicit rule injection does not really use logical rules for reasoning which decreases the interpretability and accuracy of logical rules. Explicit rule injection is influenced by the quantity and quality of logical rules. Therefore, we combine both methods to take advantage of their respective strengths. Experiments on 3 datasets demonstrate our model obtains state-of-the-art performance on complex query answering.

Learning effective representations for Continuous-Time Dynamic Graphs (CTDGs) has garnered significant research interest, largely due to its powerful capabilities in modeling complex interactions between nodes. A fundamental and crucial requirement for representation learning in CTDGs is the appropriate estimation and preservation of proximity. However, due to the sparse and evolving characteristics of CTDGs, the spatial-temporal properties inherent in high-order proximity remain largely unexplored. Despite its importance, this property presents significant challenges due to the computationally intensive nature of personalized interaction intensity estimation and the dynamic attributes of CTDGs. To this end, we propose a novel Correlated Spatial-Temporal Positional encoding that incorporates a parameter-free personalized interaction intensity estimation under the weak assumption of the Poisson Point Process. Building on this, we introduce the Dynamic Graph Transformer with Correlated Spatial-Temporal Positional Encoding (CorDGT), which efficiently retains the evolving spatial-temporal high-order proximity for effective node representation learning in CTDGs. Extensive experiments on seven small and two large-scale datasets demonstrate the superior performance and scalability of the proposed CorDGT. The code is available at: https://github.com/wangz3066/CorDGT.

Logical rules have been widely used for expressing schema knowledge in various practical applications. It is infeasible to handcraft rules from large knowledge graphs (KGs) and thus many methods have been proposed for learning rules automatically from KGs. However, it is largely ignored how to extract rules in a (target) KG from rules that already exist in some other (source) KGs. In this paper, we propose a framework for KG rule learning based on transfer learning. A major challenge for establishing such a framework is that a suitable alignment mechanism is required for mapping certain subgraph structures between predicates in the source KG and the target KG. Hence, our framework provides a new method for predicate mapping based on graph-structural similarity. The proposed framework can be used as a standalone rule learner but more importantly, it paves a new way for enhancing the state-of-the-art rule learners for large KGs. Extensive experiments are conducted to evaluate the new approach to rule learning, which shows that rules in smaller KGs can be effectively transferred to a large KG.

Multiple-choice question answering (MCQA) becomes particularly challenging when all choices are relevant to the question and are semantically similar. Yet this setting of MCQA can potentially provide valuable clues for choosing the right answer. Existing models often rank each choice separately, overlooking the context provided by other choices. Specifically, they fail to leverage the semantic commonalities and nuances among the choices for reasoning. In this paper, we propose a novel MCQA model by differentiating choices through identifying and eliminating their commonality, called DCQA. Our model captures token-level attention of each choice to the question, and separates tokens of the question attended to by all the choices (i.e., commonalities) from those by individual choices (i.e., nuances). Using the nuances as refined contexts for the choices, our model can effectively differentiate choices with subtle differences and provide justifications for choosing the correct answer. We conduct comprehensive experiments across five commonly used MCQA benchmarks, demonstrating that DCQA consistently outperforms baseline models. Furthermore, our case study illustrates the effectiveness of the approach in directing the attention of the model to more differentiating features.

In commonsense question answering (CSQA), pre-trained language models are often used to generate background knowledge that provides clues to improve the interpretability and performance of CSQA models. However, these methods are often ineffective for generating clues to distinguish similar options, and they also have limitations in using generative capabilities to solve CSQA tasks. In this paper, we propose a new model for CSQA that can differentiate the options for a question more effectively. This model leverages the generative capabilities of the pre-trained model to better understand the relationship between question and candidate options, creating clues that aid in effectively distinguishing choices for the question. Moreover, a mechanism is introduced to encourage the model to discern distinctions among options. Our proposed model demonstrates superior performance on four CSQA datasets, outperforming comparable models.

Temporal Knowledge Graphs (TKG) reasoning has emerged as a powerful methodology for prediction in various domains. Unlike traditional Knowledge Graphs(KG), TKGs introduce a critical time dimension to the graph structure. Existing TKG reasoning methods expose two important limitations. The first is they are primarily designed to predict the immediate next time step. When applied to multi-step predictions, this leads to an iterative process that compromises prediction efficiency. The second limitation is their performance often depends on short-term memory and overlook long-term global information. To overcome these limitations, we introduce the Echo State Temporal Knowledge Graph Network (ESTN), an innovative approach leveraging the Echo State Networks (ESN) for TKG reasoning. Specifically, the ESTN contains a Graph Embedder (GE) which integrates both short-term and long-term information within the TKG, enhancing the depth and accuracy of the data representation in graph latent space (embeddings). A Time Module (TM) is designed to facilitate direct prediction over multiple time steps, significantly improved the prediction efficiency. Extensive experiments demonstrate that our method not only show robust performance, but also offers an alternative approach to TKG reasoning, emphasizing how the distinct features of ESN can be effectively harnessed in TKG reasoning tasks.

Existing models for commonsense question answering (CQA) usually focus on combining pre-trained language models (PLMs) and structured knowledge graphs (KGs) for joint reasoning. However, such approaches encode a QA context (i.e., a pair of the question and a choice) separately from other choices, ineffective for explicitly capturing useful subtle differences among the choices, which results in incorrect answers in some cases. This paper proposes a novel model LNC (Learning Nuance among Choices) for addressing this problem and thus provides an improved approach to multiple-choice question answering. Specifically, LNC explicitly interacts between the text knowledge corresponding to each choice and the external KG knowledge corresponding to each choice, and removes the commonalities among similar choices, allowing the model to focus on different relevant knowledge based on the choices, thereby distinguishing semantically similar choices. Experimental results on major benchmark datasets show that LNC is competitive comparing to the baseline models.

Named entity recognition (NER) is the task of identifying and classifying named entities from texts. NER can benefit from linguistic dependency information, yet existing NER models can only utilize such information on datasets where dependency annotations are readily available. Dependency parsing (DP) models can be used to generate annotations, which are trained independent of the NER task and can cause error propagation to NER. In this paper, we propose a joint NER and DP model through multi-task learning, which allows the NER and DP modules to benefit from the joint training and provides an end-to-end solution to dependency-guided NER. Our model JOINDER uses a shared contextualized embedder, a word encoder, a biaffine dependency classifier, and a multi-hop dependency-guided NER. Experiments on several standard datasets in four languages show the effectiveness of joint learning and the outstanding performance of JOINDER compared to existing models. Moreover, our model can transfer dependency knowledge to other datasets with no dependency annotat.

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.

Recently proposed knowledge distillation approaches based on feature-map transfer validate that intermediate layers of a teacher model can serve as effective targets for training a student model to obtain better generalization ability. Existing studies mainly focus on particular representation forms for knowledge transfer between manually specified pairs of teacher-student intermediate layers. However, semantics of intermediate layers may vary in different networks and manual association of layers might lead to negative regularization caused by semantic mismatch between certain teacher-student layer pairs. To address this problem, we propose Semantic Calibration for Cross-layer Knowledge Distillation (SemCKD), which automatically assigns proper target layers of the teacher model for each student layer with an attention mechanism. With a learned attention distribution, each student layer distills knowledge contained in multiple layers rather than a single fixed intermediate layer from the teacher model for appropriate cross-layer supervision in training. Consistent improvements over state-of-the-art approaches are observed in extensive experiments with various network architectures for teacher and student models, demonstrating the effectiveness and flexibility of the proposed attention based soft layer association mechanism for cross-layer distillation.

It is natural and effective to use rules for representing explicit knowledge in knowledge graphs. However, it is challenging to learn rules automatically from very large knowledge graphs such as Freebase and YAGO. This paper presents a new approach, RLvLR (Rule Learning via Learning Representations), to learning rules from large knowledge graphs by using the technique of embedding in representation learning together with a new sampling method. Based on RLvLR, a new method RLvLR-Stream is developed for learning rules from streams of knowledge graphs. Both RLvLR and RLvLR-Stream have been implemented and experiments conducted to validate the proposed methods regarding the tasks of rule learning and link prediction. Experimental results show that our systems are able to handle the task of rule learning from large knowledge graphs with high accuracy and outperform some state-of-the-art systems. Specifically, for massive knowledge graphs with hundreds of predicates and over 10M facts, RLvLR is much faster and can learn much more quality rules than major systems for rule learning in knowledge graphs such as AMIE+. In the setting of knowledge graph streams, RLvLR-Stream significantly improved RLvLR for both rule learning and link prediction.

In the last two decades, several studies have been carried out to translate Behavior Trees (BTs) into other formal languages. However, as BTs are usually drawn directly from natural languages, there is no formal grammar to define what is a valid BT. In this research, we first propose a normal form for requirement BT as a building block for a valid BT, and then design a context-free grammar that can generate and verify all valid BTs. This work provides a solid foundation for BT research and will improve the quality of requirements modeling by identifying some common requirement defects.

In this paper, we study an information exchange process in which a network of individuals exchanges a binary opinion.In the process, the individuals change their opinions only if a majority of their neighbours have the opposite opinion and they do it synchronously.Motivated by applications in multiagent systems, distributed computing, and social science, our goal is to derive graphtheoretic features of the network that guarantee whenever a majority of individuals initially have the same opinion, they will eventually spread the opinion to all individuals.We tackle the problem by first introducing a graph-theoretic notion called controlling set which is capable of characterising the information exchange process and, by exploiting the notion, we obtain a series of lower and upper bounds on the in-degree of vertices as well as lower bound on the size of certain neighbourhoods for guaranteeing the majority to unanimity behaviour.

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.

Modal logics are primary formalisms for multi-agent systems but major reasoning tasks in such logics are intractable, which impedes applications of multi-agent modal logics such as automatic planning. One technique of tackling the intractability is to identify a fragment called a normal form of multiagent logics such that it is expressive but tractable for reasoning tasks such as entailment checking, bounded conjunction transformation and forgetting. For instance, DNF of propositional logic is tractable for these reasoning tasks. In this paper, we first introduce a notion of logical separability and then define a novel disjunctive normal form SDNF for the multiagent logic Kn, which overcomes some shortcomings of existing approaches. In particular, we show that every modal formula in Kn can be equivalently casted as a formula in SDNF, major reasoning tasks tractable in propositional DNF are also tractable in SDNF, and moreover, formulas in SDNF enjoy the property of logical separability. To demonstrate the usefulness of our approach, we apply SDNF in multi-agent epistemic planning. Finally, we extend these results to three more complex multi-agent logics Dn, K45n and KD45n.

Requirement Change is one of the most challenging tasks in software development lifecycle, particularly in the complex context of Global Software Development (GSD). During the last decade, many studies are carried out to address these problems, however, careful examination of these works suggests that there's a potential research gap. This paper has performed a Systematic Literature Review (SLR) to identify the most significant/commonly studied challenges of requirement change management process and furthermore this process under GSD context. We identified ten challenges such as impact analysis, cost estimation, artifacts documents management, requirement traceability, requirements dependency, conflicts with existing requirements, time estimation, change prioritization, user involvement, and system destabilizing. Furthermore, three challenges such as communication and coordination, knowledge sharing, management, and Change Control Board (CCB) management are identified for globally distributed projects. We also mapped these identified challenges to Requirement Change Management Process (RCMP) outcomes proposed in our previous study. We believe that mapping between RCM challenges and RCMP outcomes will enhance the practical significance of this study results. Considering the systematic literature review results, we suggest that there is a need to develop a framework for requirement change management for quality software systems development.

AGM contraction and revision assume an underlying logic that contains propositional logic. Consequently, this assumption excludes many useful logics such as the Horn fragment of propositional logic and most description logics. Our goal in this paper is to generalise AGM contraction and revision to (near-)arbitrary fragments of classical first-order logic. To this end, we first define a very general logic that captures these fragments. In so doing, we make the modest assumptions that a logic contains conjunction and that information is expressed by closed formulas or sentences. The resulting logic is called first-order conjunctive logic or FC logic for short. We then take as the point of departure the AGM approach of constructing contraction functions through epistemic entrenchment, that is the entrenchment-based contraction. We redefine entrenchment-based contraction in ways that apply to any FC logic, which we call FC contraction. We prove a representation theorem showing its compliance with all the AGM contraction postulates except for the controversial recovery postulate. We also give methods for constructing revision functions through epistemic entrenchment which we call FC revision; which also apply to any FC logic. We show that if the underlying FC logic contains tautologies then FC revision complies with all the AGM revision postulates. Finally, in the context of FC logic, we provide three methods for generating revision functions via a variant of the Levi Identity, which we call contraction, withdrawal and cut generated revision, and explore the notion of revision equivalence. We show that withdrawal and cut generated revision coincide with FC revision and so does contraction generated revision under a finiteness condition.

Existential rules, a family of expressive ontology languages, inherit desired expressive and reasoning properties from both description logics and logic programming. On the other hand, forgetting is a well studied operation for ontology reuse, obfuscation and analysis. Yet it is challenging to establish a theory of forgetting for existential rules. In this paper, we lay the foundation for a theory of forgetting for existential rules by developing a novel notion of unfolding. In particular, we introduce a definition of forgetting for existential rules in terms of query answering and provide a characterisation of forgetting by the unfolding. A result of forgetting may not be expressible in existential rules, and we then capture the expressibility of forgetting by a variant of boundedness. While the expressibility is undecidable in general, we identify a decidable fragment. Finally, we provide an algorithm for forgetting in this fragment.

The pattern satisfiability is a fundamental problem for SPARQL. This paper provides a complete analysis of decidability/undecidability of satisfiability problems for SPARQL 1.1 patterns. A surprising result is the undecidability of satisfiability for SPARQL 1.1 patterns when only AND and MINUS are expressible. Also, it is shown that any fragment of SPARQL 1.1 without expressing both AND and MINUS is decidable. These results provide a guideline for future SPARQL query language design and implementation.

We study the problem of learning first-order rules from large Knowledge Graphs (KGs). With recent advancement in information extraction, vast data repositories in the KG format have been obtained such as Freebase and YAGO. However, traditional techniques for rule learning are not scalable for KGs. This paper presents a new approach RLvLR to learning rules from KGs by using the technique of embedding in representation learning together with a new sampling method. Experimental results show that our system outperforms some state-of-the-art systems. Specifically, for massive KGs with hundreds of predicates and over 10M facts, RLvLR is much faster and can learn much more quality rules than major systems for rule learning in KGs such as AMIE+. We also used the RLvLR-mined rules in an inference module to carry out the link prediction task. In this task, RLvLR outperformed Neural LP, a state-of-the-art link prediction system, in both runtime and accuracy.

We consider the problem of finding map regions that best match query keywords. This region search problem can be applied in many practical scenarios such as shopping recommendation, searching for tourist attractions, and collision region detection for wireless sensor networks. While conventional map search retrieves isolate locations in a map, users frequently attempt to find regions of interest instead, e.g., detecting regions having too many wireless sensors to avoid collision, or finding shopping areas featuring various merchandise or tourist attractions of different styles. Finding regions of interest in a map is a non-trivial problem and retrieving regions of arbitrary shapes poses particular challenges. In this paper, we present a novel region search algorithm, dense region search (DRS), and its extensions, to find regions of interest by estimating the density of locations containing the query keywords in the region. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of our algorithm.

Two essential tasks in managing description logic knowledge bases are eliminating problematic axioms and incorporating newly formed ones. Such elimination and incorporation are formalised as the operations of contraction and revision in belief change. In this paper, we deal with contraction and revision for the DL-Lite family through a model-theoretic approach. Standard description logic semantics yields an infinite number of models for DL-Lite knowledge bases, thus it is difficult to develop algorithms for contraction and revision that involve DL models. The key to our approach is the introduction of an alternative semantics called type semantics which can replace the standard semantics in characterising the standard inference tasks of DL-Lite. Type semantics has several advantages over the standard one. It is more succinct and importantly, with a finite signature, the semantics always yields a finite number of models. We then define model-based contraction and revision functions for DL-Lite knowledge bases under type semantics and provide representation theorems for them. Finally, the finiteness and succinctness of type semantics allow us to develop tractable algorithms for instantiating the functions.

Model-based approaches provide a semantically well justified way to revise ontologies. However, in general, model-based revision operators are limited due to lack of efficient algorithms and inexpressibility of the revision results. In this paper, we make both theoretical and practical contribution to efficient computation of model-based revisions in DL-Lite. Specifically, we show that maximal approximations of two well-known model-based revisions for DL-Lite_R can be computed using a syntactic algorithm. However, such a coincidence of model-based and syntactic approaches does not hold when role functionality axioms are allowed. As a result, we identify conditions that guarantee such a coincidence for DL-Lite_FR. Our result shows that both model-based and syntactic revisions can co-exist seamlessly and the advantages of both approaches can be taken in one revision operator. Based on our theoretical results, we develop a graph-based algorithm for the revision operat

The theory of (variable) forgetting has received significant attention in nonmonotonic reasoning, especially, in answer set programming. However, the problem of establishing a theory of forgetting for some expressive nonmonotonic logics such as McCarthy's circumscription is rarely explored.In this paper a theory of forgetting for propositional circumscription is proposed, which is not a straightforward adaption of existing approaches. In particular, some properties that are essential for existing proposals do not hold any longer or have to be reformulated. Several useful properties of the new forgetting are proved, which demonstrate suitability of the forgetting for circumscription. A sound and complete algorithm for the forgetting is developed and an analysis of computational complexity is given.

The development and maintenance of large and complex ontologies are often time-consuming and error-prone. Thus, automated ontology learning and evolution have attracted intensive research interest. In data-centric applications where ontologies are designed from the data or automatically learnt from it, when new data instances are added that contradict the ontology, it is often desirable to incrementally revise the ontology according to the added data. In description logics, this problem can be intuitively formulated as the operation of TBox contraction, i.e., rational elimination of certain axioms from the logical consequences of a TBox, and it is w.r.t. an ABox. In this paper we introduce a model-theoretic approach to such a contraction problem by using an alternative semantic characterisation of DL-Lite TBoxes. We show that entailment checking (without necessarily first computing the contraction result) is in coNP, which does not shift the corresponding complexity in propositional logic, and the problem is tractable when the size of the new data is bounded.

Ontology-mediated data access and management systems are rapidly emerging. Besides standard query answering, there is also a need for such systems to be coupled with explanation facilities, in particular to explain missing query answers (i.e. desired answers of a query which are not derivable from the given ontology and data). This support is highly demanded for debugging and maintenance of big data, and both theoretical results and algorithms proposed. However, existing query explanation algorithms either cannot scale over relative large data sets or are not guaranteed to compute all desired explanations. To the best of our knowledge, no existing algorithm can efficiently and completely explain conjunctive queries (CQs) w.r.t. ELH1 ontologies. In this paper, we present a hybrid approach to achieve this. An implementation of the proposed query explanation algorithm has been developed using an off-the-shelf Prolog engine and a datalog engine. Finally, the system is evaluated over practical ontologies. Experimental results show that our system scales over large data sets.

DL-Lite is an important family of description logics. Recently, there is an increasing interest in handling inconsistency in DL-Lite as the constraint imposed by a TBox can be easily violated by assertions in ABox in DL-Lite. In this paper, we present a distance-based paraconsistent semantics based on the notion of feature in DL-Lite, which provides a novel way to rationally draw meaningful conclusions even from an inconsistent knowledge base. Finally, we investigate several important logical properties of this entailment relation based on the new semantics and show its promising advantages in non-monotonic reasoning for DL-Lite.

Ontology engineering and maintenance require (semi-)automated ontology change operations. Intensive research has been conducted on TBox and ABox changes in description logics (DLs), and various change operators have been proposed in the literature. Existing operators largely fall into two categories: syntax-based and model-based. While each approach has its advantages and disadvantages, an important topic that has rarely been explored is how to achieve a balance between syntax-based and model-based approaches. Also, most existing operators are specially designed for either TBox change or ABox change, and cannot handle the general ontology revision task—given a DL knowledge base (KB, a pair consisting of a TBox and an ABox), how to revise it by a set of TBox and ABox axioms ( i.e. , a new DL KB). In this article, we introduce an alternative structure for DL-Lite, called a featured interpretation, and show that featured models provide a finite and tight characterization to the classical semantics of DL-Lite. A key issue for defining a change operator is the so-called expressibility, that is, whether a set of models (or featured models here) is axiomatizable in DLs. It is indeed much easier to obtain expressibility results for featured models than for classical DL models. As a result, the new semantics determined by featured models provides a method for defining and studying various changes of DL-Lite KBs that involve both TBoxes and ABoxes. To demonstrate the usefulness of the new semantic characterization in ontology change, we define two revision operators for DL-Lite KBs using featured models and study their properties. In particular, we show that our two operators both satisfy AGM postulates. We show that the complexity of our revisions is Π P 2 -complete, that is, on the same level as major revision operators in propositional logic, which further justifies the feasibility of our revision approach for DL-Lite. Also, we develop algorithms for these DL-Lite revisions.

Two essential tasks in managing Description Logic (DL) ontologies are eliminating problematic axioms and incorporating newly formed axioms. Such elimination and incorporation are formalised as the operations of contraction and revision in belief change.In this paper, we deal with contraction and revision for the DL-Lite family through a model-theoretic approach.Standard DL semantics yields infinite numbers of models for DL-Lite TBoxes, thus it is not practical to develop algorithms for contraction and revision that involve DL models. The key to our approach is the introduction of an alternative semantics called type semantics which is more succinct than DL semantics. More importantly, with a finite signature, type semantics always yields finite humber of models.We then define model-based contraction and revision for DL-Lite TBoxesunder type semantics and provide representation theorems for them.Finally, the succinctness of type semantics allows us to develop tractable algorithms for both operations.

Forgetting is an important tool for reducing ontologies by eliminating some redundant concepts and roles while preserving sound and complete reasoning. Attempts have previously been made to address the problem of forgetting in relatively simple description logics (DLs), such as DL‐Lite and extended . However, the issue of forgetting for ontologies in more expressive DLs, such as and OWL DL, is largely unexplored. In particular, the problem of characterizing and computing forgetting for such logics is still open. In this paper, we first define semantic forgetting about concepts and roles in ontologies and state several important properties of forgetting in this setting. We then define the result of forgetting for concept descriptions in , state the properties of forgetting for concept descriptions, and present algorithms for computing the result of forgetting for concept descriptions. Unlike the case of DL‐Lite, the result of forgetting for an ontology does not exist in general, even for the special case of forgetting in TBoxes. This makes the problem of computing the result of forgetting in more challenging. We address this problem by defining a series of approximations to the result of forgetting for ontologies and studying their properties. Our algorithms for computing approximations can be directly implemented as a plug‐in of an ontology editor to enhance its ability of managing and reasoning in (large) ontologies.

Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that MFA and MSA generalise most of these notions. Existential rules are closely related to the Horn fragments of the OWL 2 ontology language; furthermore, several prominent OWL 2 reasoners implement CQ answering by using the chase to materialise all relevant facts. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any termination guarantees. In this paper we also investigate whether various acyclicity notions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 ontologies are MSA, and that the number of facts obtained by materialisation is not too large. Our results thus suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.

Revising knowledge bases (KBs) in description logics (DLs) in a syntax-independent manner is an important, nontrivial problem for the ontology management and DL communities. Several attempts have been made to adapt classical model-based belief revision and update techniques to DLs, but they are restricted in several ways. In particular, they do not provide operators or algorithms for general DL KB revision. The key difficulty is that, unlike propositional logic, a DL KB may have infinitely many models with complex (and possibly infinite) structures, making it difficult to define and compute revisions in terms of models. In this paper, we study general KBs in a specific DL in the DL-Lite family. We introduce the concept of features for such KBs, develop an alternative semantic characterization of KBs using features (instead of models), define two specific revision operators for KBs, and present the first algorithm for computing best approximations for syntax-independent revisions of KBs.