In this paper we consider how Qualitative Spatial Reasoning (QSR) can be used to answer queries over large-scale knowledge graphs such as YAGO and DBPedia. We describe the challenges associated with spatially querying knowledge graphs such as point based representations, sparsity of qualitative relations, and scale. We address these challenges and present a query engine, Parallel Qualitative Reasoner-Query Engine (ParQR-QE), that uses a novel distributed qualitative spatial reasoning algorithm to provide answers to GeoSPARQL queries. An experimental evaluation using a range of different query types and the YAGO knowledge graph shows the advantages of QSR techniques in comparison to purely quantitative approaches. • Demonstration of techniques to develop enhanced large-scale knowledge graphs. • Integration of qualitative spatial reasoning into query answering. • Development of a distributed spatial query answering system for large-scale knowledge graphs. • Evaluation shows advantages of querying using qualitative spatial reasoning.

Attention-Deficit Hyperactivity Disorder (ADHD) is a mental condition characterised by a pattern of inattention, hyperactivity, and/or impulsivity that causes significant impairment across various domains. Delayed diagnosis and treatment for ADHD can be harmful to people, leading to broader mental health conditions. This paper presents a fully functional system for diagnosing ADHD using an Artificial Intelligence (AI) system called Neuro Intel. Positive results from our research has led to the development of Neuro Intel, which incorporates both expert clinician knowledge and historical clinical data using Machine Learning to assist clinicians in the diagnosis of ADHD in adults.

This paper describes work in progress about using AI technologies to support diagnostic decision making. In particular, we analyse clinical data of past cases to develop a data-driven prediction model for future cases. To do so, we use a versatile AutoML platform that applies a multitude of machine learning algorithms and their configurations. Our results show initial promise, but also point to limitations of currently available data, opening up avenues for further research.

Apart from the need for superior accuracy, healthcare applications of intelligent systems also demand the deployment of interpretable machine learning models which allow clinicians to interrogate and validate extracted medical knowledge. Fuzzy rule-based models are generally considered interpretable that are able to reflect the associations between medical conditions and associated symptoms, through the use of linguistic if-then statements. Systems built on top of fuzzy sets are of particular appealing to medical applications since they enable the tolerance of vague and imprecise concepts that are often embedded in medical entities such as symptom description and test results. They facilitate an approximate reasoning framework which mimics human reasoning and supports the linguistic delivery of medical expertise often expressed in statements such as 'weight low' or 'glucose level high' while describing symptoms. This paper proposes an approach by performing data-driven learning of accurate and interpretable fuzzy rule bases for clinical decision support. The approach starts with the generation of a crisp rule base through a decision tree learning mechanism, capable of capturing simple rule structures. The crisp rule base is then transformed into a fuzzy rule base, which forms the input to the framework of adaptive network-based fuzzy inference system (ANFIS), thereby further optimising the parameters of both rule antecedents and consequents. Experimental studies on popular medical data benchmarks demonstrate that the proposed work is able to learn compact rule bases involving simple rule antecedents, with statistically better or comparable performance to those achieved by state-of-the-art fuzzy classifiers.

Abstract Qualitative reasoning involves expressing and deriving knowledge based on qualitative terms such as natural language expressions, rather than strict mathematical quantities. Well over 40 qualitative calculi have been proposed so far, mostly in the spatial and temporal domains, with several practical applications such as naval traffic monitoring, warehouse process optimisation and robot manipulation. Even if a number of specialised qualitative reasoning tools have been developed so far, an important barrier to the wider adoption of these tools is that only qualitative reasoning is supported natively, when real-world problems most often require a combination of qualitative and other forms of reasoning. In this work, we propose to overcome this barrier by using ASP as a unifying formalism to tackle problems that require qualitative reasoning in addition to non-qualitative reasoning. A family of ASP encodings is proposed which can handle any qualitative calculus with binary relations. These encodings are experimentally evaluated using a real-world dataset based on a case study of determining optimal coverage of telecommunication antennas, and compared with the performance of two well-known dedicated reasoners. Experimental results show that the proposed encodings outperform one of the two reasoners, but fall behind the other, an acceptable trade-off given the added benefits of handling any type of reasoning as well as the interpretability of logic programs.

Abstract Recent technological advances have led to unprecedented amounts of generated data that originate from the Web, sensor networks, and social media. Analytics in terms of defeasible reasoning – for example, for decision making – could provide richer knowledge of the underlying domain. Traditionally, defeasible reasoning has focused on complex knowledge structures over small to medium amounts of data, but recent research efforts have attempted to parallelize the reasoning process over theories with large numbers of facts. Such work has shown that traditional defeasible logics come with overheads that limit scalability. In this work, we design a new logic for defeasible reasoning, thus ensuring scalability by design. We establish several properties of the logic, including its relation to existing defeasible logics. Our experimental results indicate that our approach is indeed scalable and defeasible reasoning can be applied to billions of facts.

Representation and reasoning over legal rules is an important application domain and a number of related approaches have been developed. In this work, we investigate legal reasoning in practice based on three use cases of increasing complexity. We consider three representation and reasoning approaches: (a) Answer Set Programming, (b) Argumentation and (c) Defeasible Logic. Representation and reasoning approaches are evaluated with respect to semantics, expressiveness, efficiency, complexity and support.

Abstract Spatial information is often expressed using qualitative terms such as natural language expressions instead of coordinates; reasoning over such terms has several practical applications, such as bus routes planning. Representing and reasoning on trajectories is a specific case of qualitative spatial reasoning that focuses on moving objects and their paths. In this work, we propose two versions of a trajectory calculus based on the allowed properties over trajectories, where trajectories are defined as a sequence of non-overlapping regions of a partitioned map. More specifically, if a given trajectory is allowed to start and finish at the same region, 6 base relations are defined (TC-6). If a given trajectory should have different start and finish regions but cycles are allowed within, 10 base relations are defined (TC-10). Both versions of the calculus are implemented as ASP programs; we propose several different encodings, including a generalised program capable of encoding any qualitative calculus in ASP. All proposed encodings are experimentally evaluated using a real-world dataset. Experiment results show that the best performing implementation can scale up to an input of 250 trajectories for TC-6 and 150 trajectories for TC-10 for the problem of discovering a consistent configuration, a significant improvement compared to previous ASP implementations for similar qualitative spatial and temporal calculi.

Abstract argumentation framework (AF) is a unifying framework able to encompass a variety of nonmonotonic reasoning approaches, logic programming and computational argumentation. Yet, efficient approaches for most of the decision and enumeration problems associated to AFs are missing, thus limiting the efficacy of argumentation-based approaches in real domains. In this paper, we present an algorithm for enumerating the preferred extensions of abstract argumentation frameworks which exploits parallel computation. To this purpose, the SCC-recursive semantics definition schema is adopted, where extensions are defined at the level of specific sub-frameworks. The algorithm shows significant performance improvements in large frameworks, in terms of number of solutions found and speedup.

Recent technological advances in modern healthcare have lead to the ability to collect a vast wealth of patient monitoring data. This data can be utilised for patient diagnosis but it also holds the potential for use within medical research. However, these datasets often contain errors which limit their value to medical research, with one study finding error rates ranging from 2.3%-26.9% in a selection of medical databases. Previous methods for automatically assessing data quality normally rely on threshold rules, which are often unable to correctly identify errors, as further complex domain knowledge is required. To combat this, a semantic web based framework has previously been developed to assess the quality of medical data. However, early work, based solely on traditional semantic web technologies, revealed they are either unable or inefficient at scaling to the vast volumes of medical data. In this paper we present a new method for storing and querying medical RDF datasets using Hadoop Map / Reduce. This approach exploits the inherent parallelism found within RDF datasets and queries, allowing us to scale with both dataset and system size. Unlike previous solutions, this framework uses highly optimised (SPARQL) joining strategies, intelligent data caching and the use of a super-query to enable the completion of eight distinct SPARQL lookups, comprising over eighty distinct joins, in only two Map / Reduce iterations. Results are presented comparing both the Jena and a previous Hadoop implementation demonstrating the superior performance of the new methodology. The new method is shown to be five times faster than Jena and twice as fast as the previous approach.

Academia and industry are investigating novel approaches for processing vast amounts of data coming from enterprises, the Web, social media and sensor readings in an area that has come to be known as Big Data. Logic programming has traditionally focused on complex knowledge structures/programs. The question arises whether and how it can be applied in the context of Big Data. In this paper, we study how the well-founded semantics can be computed over huge amounts of data using mass parallelization. Specifically, we propose and evaluate a parallel approach based on the X10 programming language. Our experiments demonstrate that our approach has the ability to process up to 1 billion facts within minutes.

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.

Abstract Data originating from the Web, sensor readings and social media result in increasingly huge datasets. The so called Big Data comes with new scientific and technological challenges while creating new opportunities, hence the increasing interest in academia and industry. Traditionally, logic programming has focused on complex knowledge structures/programs, so the question arises whether and how it can work in the face of Big Data. In this paper, we examine how the well-founded semantics can process huge amounts of data through mass parallelization. More specifically, we propose and evaluate a parallel approach using the MapReduce framework. Our experimental results indicate that our approach is scalable and that well-founded semantics can be applied to billions of facts. To the best of our knowledge, this is the first work that addresses large scale nonmonotonic reasoning without the restriction of stratification for predicates of arbitrary arity.

The Resource Description Framework (RDF) has become the defacto standard for representing information in the Semantic Web. Given the increasing amount of sensitive RDF data available on the Web, it becomes increasingly critical to guarantee secure access to this content. In this paper we advocate the use of an abstract access control model to ensure the selective exposure of RDF information. The model is defined by a set of abstract operators and tokens. Tokens are used to label RDF triples with access information. Abstract operators model RDF Schema inference rules and propagation of labels along the RDF Schema(RDFS) class and property hierarchies. In this way, the access label of a triple is a complex expression that involves the labels of the triples and the operators applied to obtain said label. Different applications can then adopt different concrete access policies that encode an assignment of the abstract tokens and operators to concrete (specific) values. Following this approach, changes in the interpretation of abstract tokens and operators can be easily implemented resulting in a very flexible mechanism that allows one to easily experiment with different concrete access policies (defined per context or user). To demonstrate the feasibility of the approach, we implemented our ideas on top of the MonetDB and PostgreSQL open source database systems. We conducted an initial set of experiments which showed that the overhead for using abstract expressions is roughly linear to the number of triples considered; performance is also affected by the characteristics of the dataset, such as the size and depth of class and property hierarchies as well as the considered concrete policy.

Defeasible logic is a non-monotonic formalism that deals with incomplete and conflicting information, whereas modal logic deals with the concepts of necessity and possibility. These types of logics play a significant role in the emerging Semantic Web, which enriches the available Web information with meaning, leading to better cooperation between end-users and applications. Defeasible and modal logics, in general, and, particularly, deontic logic provide means for modeling agent communities, where each agent is characterized by its cognitive profile and normative system, as well as policies, which define privacy requirements, access permissions, and individual rights. Toward this direction, this article discusses the extension of DR-DEVICE, a Semantic Web-aware defeasible reasoner, with a mechanism for expressing modal logic operators, while testing the implementation via deontic logic operators, concerned with obligations, permissions, and related concepts. The motivation behind this work is to develop a practical defeasible reasoner for the Semantic Web that takes advantage of the expressive power offered by modal logics, accompanied by the flexibility to define diverse agent behaviours. A further incentive is to study the various motivational notions of deontic logic and discuss the cognitive state of agents, as well as the interactions among them.

We present a principled framework for modular Web rule bases, called MWeb. According to this framework, each predicate defined in a rule base is characterized by its defining reasoning mode, scope, and exporting rule base list. Each predicate used in a rule base is characterized by its requesting reasoning mode and importing rule base list. For legal MWeb modular rule bases S , the MWebAS and MWebWFS semantics of each rule base s ∈ S with respect to S are defined model-theoretically. These semantics extend the answer set semantics (AS) and the well-founded semantics with explicit negation (WFSX) on ELPs, respectively, keeping all of their semantical and computational characteristics. Our framework supports: (1) local semantics and different points of view, (2) local closed-world and open-world assumptions, (3) scoped negation-as-failure, (4) restricted propagation of local inconsistencies, and (5) monotonicity of reasoning, for fully shared predicates.

The imperfect nature of context in ambient intelligence environments, and the special characteristics of the entities that possess and share the available context information render contextual reasoning a very challenging task. The accomplishment of this task requires formal models that handle the involved entities as autonomous logic-based agents, and provide methods for handling the imperfect and distributed nature of context. We propose a solution based on the multi-context systems (MCS) formalism, in which local context knowledge of ambient agents is encoded in rule theories (contexts), and information flow between agents is achieved through mapping rules, associating concepts used by different contexts. To handle the imperfect nature of context, we extend MCS with non-monotonic features-local defeasible theories, defeasible mappings, and a preference ordering on the system contexts. In this paper, we present the novel representation model, called contextual defeasible logic, describe how its elements are used to derive distributed conclusions through a proof theory, and propose an algorithm for distributed query evaluation that implements the proof theory of contextual defeasible logic. The application of the proposed approach in a scenario from the ambient intelligence domain demonstrates how its distinct features overcome the challenges imposed by the special characteristics of ambient intelligence environments.

The Extended Resource Description Framework has been proposed to equip RDF graphs with weak and strong negation, as well as derivation rules, increasing the expressiveness of ordinary RDF graphs. In parallel, the Modular Web framework enables collaborative and controlled reasoning in the Semantic Web. In this paper we show how to use the Modular Web Framework to capture the modular semantics for ERDF graphs, supporting local semantics and different points of view, local closed-world and open-world assumptions, and scoped negation-as-failure.

Ambient Intelligence environments consist of various devices that collect, process, change and share the available context information. The imperfect nature of context, the open and dynamic nature of ambient environments, and the special characteristics of the involved devices have introduced new research challenges on how to represent and reason with contextual information. Previous work presented a solution based on an extension of Multi-Context Systems through the use of defeasible reasoning to reason efficiently with conflicts. This paper reports on initial experiences gained from the deployment of contextual defeasible reasoning in real environments. We report on the architecture of an implementation on small devices, present the definition and implementation of two concrete application scenarios, and discuss the performance and issues of scalability of the approach.

The imperfect nature of context in Ambient Intelligence environments and the special characteristics of the entities that possess and share the available context information render contextual reasoning a very challenging task. The accomplishment of this task requires formal models that handle the involved entities as autonomous logic-based agents and provide methods for handling the imperfect and distributed nature of context. This paper proposes a solution based on the Multi-Context Systems paradigm in which local context knowledge of ambient agents is encoded in rule theories (contexts), and information flow between agents is achieved through mapping rules that associate concepts used by different contexts. To handle imperfect context, we extend Multi-Context Systems with nonmonotonic features: local defeasible theories, defeasible mapping rules, and a preference ordering on the system contexts. On top of this model, we have developed an argumentation framework that exploits context and preference information to resolve potential conflicts caused by the interaction of ambient agents through the mappings, and a distributed algorithm for query evaluation.

Defeasible reasoning is a computationally simple nonmonotonic reasoning approach that has attracted significant theoretical and practical attention. It comprises a family of logics that capture different intuitions, among them ambiguity propagation versus ambiguity blocking, and the adoption or rejection of team defeat. This article provides a compact presentation of the defeasible logic variants, and derives an inclusion theorem which shows that different notions of provability in defeasible logic form a chain of levels of proof.

In this work we present "AlertMe", a semantics-based, context-aware notification system that provides personalized alerts to graduate students based on their preferences. An extensive description of the system is carried out. We present the underlying ontology that models the available knowledge, as well as how higher level knowledge inference and context-based decision making is achieved through rule-based reasoning. Finally, we outline the technical aspects of the developed system, covering issues involving the integration of the various subcomponents.

Giorgos Flouris, Mathieu d'Aquin, Grigoris Antoniou, Jeff Pan, Dimitris Plexousakis; Special Issue on Ontology Dynamics, Journal of Logic and Computation,

ERDF stable model semantics is a recently proposed semantics for ERDF ontologies and a faithful extension of RDFS semantics on RDF graphs. Unfortunately, ERDF stable model semantics is in general undecidable. In this paper, we elaborate on the computability and complexity issues of the ERDF stable model semantics.

In this paper, we consider the problem of ontology evolution in the face of a change operation. We devise a general-purpose algorithm for determining the effects and side-effects of a requested elementary or complex change operation. Our work is inspired by belief revision principles (i.e., validity, success and minimal change) and allows us to handle any change operation in a provably rational and consistent manner. To the best of our knowledge, this is the first approach overcoming the limitations of existing solutions, which deal with each change operation on a per-case basis. Additionally, we rely on our general change handling algorithm to implement specialized versions of it, one per desired change operation, in order to compute the equivalent set of effects and side-effects.This work was partially supported by the EU projects CASPAR (FP6-2005-IST-033572) and KP-LAB (FP6-2004-IST-27490).

Ontologies and automated reasoning are the building blocks of the Semantic Web initiative. Derivation rules can be included in an ontology to define derived concepts, based on base concepts. For example, rules allow to define the extension of a class or property, based on a complex relation between the extensions of the same or other classes and properties. On the other hand, the inclusion of negative information both in the form of negation-as-failure and explicit negative information is also needed to enable various forms of reasoning. In this paper, we extend RDF graphs with weak and strong negation, as well as derivation rules. The ERDF stable model semantics of the extended framework (Extended RDF) is defined, extending RDF(S) semantics. A distinctive feature of our theory, which is based on Partial Logic, is that both truth and falsity extensions of properties and classes are considered, allowing for truth value gaps. Our framework supports both closed-world and open-world reasoning through the explicit representation of the particular closed-world assumptions and the ERDF ontological categories of total properties and total classes.

Logic and proofs constitute key factors in increasing the user trust towards the semantic Web. Defeasible reasoning is a useful tool towards the development of the logic layer of the semantic Web architecture. However, having a solid mathematical notation, it may be confusing to end users, who often need graphical trace and explanation mechanisms for the derived conclusions. In a previous work of ours, we outlined a methodology for representing defeasible logic rules, utilizing directed graphs that feature distinct node and connection types. However, visualizing a defeasible logic rule base also involves the placement of the multiple graph elements in an intuitive way, a non-trivial task that aims at improving user comprehensibility. This paper presents a stratification algorithm for visualizing defeasible logic rule bases that query and reason about RDF data as well as a tool that applies this algorithm.

In this paper we study the ramification problem in the setting of temporal databases. Standard solutions from the literature on reasoning about action are inadequate because they rely on the assumptions that fluents persist and actions have effects on the subsequent situation only. We provide a solution based on an extension of the situation calculus and the work of McCain and Turner. More specifically, we study the case where there are conflicting effects of concurrently executing actions and we distinguish between hard and soft integrity constraints.

Nonmonotonic rule systems are expected to play an important role in the layered development of the semantic Web. Defeasible reasoning is a direction in nonmonotonic reasoning that is based on the use of rules that may be defeated by other rules. It is a simple, but often more efficient approach than other nonmonotonic rule systems for reasoning with incomplete and inconsistent information. This paper reports on the implementation of a system for defeasible reasoning on the Web. The system 1) is syntactically compatible with RuleML, 2) features strict and defeasible rules, priorities, and two kinds of negation, 3) is based on a translation to logic programming with declarative semantics, 4) is flexible and adaptable to different intuitions within defeasible reasoning, and 5) can reason with rules, RDF, RDF Schema, and (parts of) OWL ontologies

In this article, we discuss some issues related to the intuitions of defeasible reasoning, in particular floating conclusions, reinstatement, and zombie paths. Defeasible logic serves as the formal basis for our analysis. We also make some comments on the comparison between defeasible logics and the well-founded semantics of extended logic programs with priorities. © 2006 Wiley Periodicals, Inc. Int J Int Syst 21: 545–558, 2006.

Defeasible reasoning is a rule-based approach for efficient reasoning with incomplete and inconsistent information. Such reasoning is, among others, useful for ontology integration, where conflicting information arises naturally; and for the modeling of business rules and policies, where rules with exceptions are often used. This paper describes these scenarios and reports on the implementation of a system for defeasible reasoning on the Web. The system, DR-DEVICE, is capable of reasoning about RDF metadata over multiple Web sources using defeasible logic rules. It is implemented on top of CLIPS production rule system and builds upon R-DEVICE, an earlier deductive rule system over RDF metadata that also supports derived attribute and aggregate attribute rules. Rules can be expressed either in a native CLIPS-like language, or in an extension of the OO-RuleML syntax. The operational semantics of defeasible logic are implemented through compilation into the generic rule language of R-DEVICE. The paper also presents a full semantic Web broker example for apartment renting.

Defeasible reasoning is a simple but efficient approach to nonmonotonic reasoning that has recently attracted considerable interest and that has found various applications. Defeasible logic and its variants are an important family of defeasible reasoning methods. So far no relationship has been established between defeasible logic and mainstream nonmonotonic reasoning approaches. In this paper we establish close links to known semantics of logic programs. In particular, we give a translation of a defeasible theory , instead.

Defeasible reasoning is a rule-based approach for efficient reasoning with incomplete and inconsistent information. Such reasoning is, among others, useful for ontology integration, where conflicting information arises naturally; and for the modeling of business rules and policies, where rules with exceptions are often used. This work describes these scenarios in more detail, and reports on the implementation of a system for defeasible reasoning on the Web. The system (a) is syntactically compatible with RuleML; (b) features strict and defeasible rules and priorities; (c) is based on a translation to logic programming with declarative semantics; and (d) is flexible and adaptable to different intuitions within defeasible reasoning.

This paper discusses the approach taken by the Rule Markup Language (RuleML) Initiative towards a general Web rule language framework and relates it to the MDA and UML by the Object Management Group (OMG). It also presents the abstract syntax of RuleML 0.85 as a MOF/UML model and considers the possibility to integrate RuleML with OCL and Action Semantics.

Defeasible logic is a nonmonotonic reasoning approach based on rules and priorities. Its design supports efficient implementation, and it shows promise to be deployed successfully in applications. So far, only static priorities have been used, provided by an external superiority relation. In this article we show how dynamic priorities can be integrated, where priority information is obtained from the deductive process itself. Dynamic priorities have been studied for other related reasoning systems such as default logic and argumentation. We define a proof theory, study its formal properties, and provide an argumentation semantics. © 2004 Wiley Periodicals, Inc.

Defeasible reasoning is a simple but efficient rule-based approach to nonmonotonic reasoning. It has powerful implementations and shows promise to be applied in the areas of legal reasoning and the modelling of business rules. This paper establishes significant links between defeasible reasoning and argumentation. In particular, Dung-like argumentation semantics is provided for two key defeasible logics, of which one is ambiguity propagating and the other ambiguity blocking. There are several reasons for the significance of this work: (a) establishing links between formal systems leads to a better understanding and cross-fertilization, in particular our work sheds light on the argumentation-theoretic features of defeasible logic; (b) we provide the first ambiguity blocking Dung-like argumentation system; (c) defeasible reasoning may provide an efficient implementation platform for systems of argumentation; and (d) argumentation-based semantics support a deeper understanding of defeasible reasoning, especially in the context of the intended applications.

Default logic is a prominent rigorous method for reasoning with incomplete information based on assumptions. It is a static reasoning approach, in the sense that it doesn't reason about changes and their consequences. On the other hand, its nonmonotonic behavior appears when changes to a default theory are made. This paper studies the dynamic behavior of default logic in the face of changes. We consider the operations of contraction and revision, present several solutions to these problems, and study their properties. © 2002 Wiley Periodicals, Inc.

The importance of transformations and normal forms in logic programming, and generally in computer science, is well documented. This paper investigates transformations and normal forms in the context of Defeasible Logic, a simple but efficient formalism for nonmonotonic reasoning based on rules and priorities. The transformations described in this paper have two main benefits: on one hand they can be used as a theoretical tool that leads to a deeper understanding of the formalism, and on the other hand they have been used in the development of an efficient implementation of defeasible logic.

For many years, the non-monotonic reasoning community has focussed on highly expressive logics. Such logics have turned out to be computationally expensive, and have given little support to the practical use of non-monotonic reasoning. In this work we discuss defeasible logic, a less-expressive but more efficient non-monotonic logic. We report on two new implemented systems for defeasible logic: a query answering system employing a backward chaining approach, and a forward-chaining implementation that computes all conclusions. Our experimental evaluation demonstrates that the systems can deal with large theories (up to hundreds of thousands of rules). We show that defeasible logic has linear complexity, which contrasts markedly with most other non-monotonic logics and helps to explain the impressive experimental results. We believe that defeasible logic, with its efficiency and simplicity is a good candidate to be used as a modelling language for practical applications, including modelling of regulations and business rules.

Ontologies have emerged as one of the key issues in information integration and interoperability and in their application to knowledge management and electronic commerce. A trend towards formal methods for ontology management is obvious. This paper discusses a concept which can be expected to be of great importance to formal ontology management, and which is well-known in traditional software development: refinement. We define and discuss ontology refinement, give illustrating examples, and highlight its advantages as compared to other forms of ontology revision. © 2000 John Wiley & Sons, Inc.

Conservative extensions of logical theories play an important role in software engineering. They provide a formal basis for program refinement and guarantee the integrity and transparency of modules and objects. This paper provides a detailed analysis of conservative extension concepts in the context of nonmonotonic knowledge bases, in particular default theories. Since there are different approaches to nonmonotonic reasoning based on different strategies for dealing with multiple extensions, we define several alternative refinement concepts and study their interrelationships. We also show that refinement is well behaved with respect to strong stratification, a technique for reducing computational effort in default reasoning. © 2000 John Wiley & Sons, Inc.

Default logic is a prominent rigorous method of reasoning with incomplete information based on assumptions. It is a static reasoning approach, in the sense that it doesn't reason about changes and their consequences. On the other hand, its nonmonotonic behaviour appears when a change to a default theory is made. This paper studies the dynamic behaviour of default logic in the face of changes, a concept that we motivate by a reference to requirements engineering. The paper defines a contraction and a revision operator, and studies their properties. This work is part of an ongoing project whose aim is to build an integrated, domain-independent toolkit of logical methods for reasoning with changing and incomplete information. The techniques described in this paper will be implemented as part of the toolkit.

A production system (PS) is a forward chaining rule based system used to build large expert systems. Testing a PS must involve the construction of a covering set of test data but it is not clear what the meaning of covering a PS is and how a test data set can be measured according to coverage. We propose a test data coverage measure for a subset for PS with well defined semantics. We use a correspondence between PS and function free first order Horn logic programs to define the declarative coverage notion and measure. We found that the coverage measure can be used to determine the coverage of the program logic of a PS as well as to automate test data generation. Unification theory is utilised to measure test data coverage and constrained inductive generation is used for test data construction.

Default reasoning is computationally expensive. One of the most promising ways of easing this problem and developing powerful implementations is to split a default theory into smaller parts and compute extensions in a modular, “local” way. Up to now this idea was only followed for Reiter's default logic, yet it is also relevant to other variants of default logic which have found increasing recognition in the past years. This paper shows how it can be modified to work for several popular, alternative approaches of default reasoning: justified, constrained and rational default logic. This work defines the formal basis for a Web-based default reasoning system which is under development at our institution. © 1998 John Wiley & Sons, Inc.

This paper discusses the significance of nonmonotonic reasoning, a method from the knowledge representation area, to mainstream software engineering. In particular, we discuss why the use of defaults in specifications is an adequate way of addressing some of the most important problems in requirements engineering, such as: The problem of identifying and dealing with inconsistencies; evolving system requirements; requirements prioritization; and the quality of specifications with respect to naturalness and compactness. We argue that these problems need to be addressed in a principled, formal way, and that default reasoning provides adequate mechanisms to deal with them.

Cumulativity is an important property of nonmonotonic inference relations because it allows for the safe use of lemmas. This note shows that Justified Default Logic, Lukaszewicz variant of default logic, is cumulative for prerequisite-free default theories, a question that has been open in the literature. The proof is very simple and makes use of an operational interpretation of extensions.

The study of different variants of default logic reveals not only differences but also properties they share. For example, there seems to be a close relationship between semi-monotonicity and the guaranteed existence of extensions. Likewise, formula-manipulating default logics tend to violate the property of cumulativity. The problem is that currently such properties must be established separately for each approach. This paper describes some steps towards the study of properties of classes of default logics by giving a rather general definition of what a default logic is. Essentially our approach is operational and restricts attention to purely formula-manipulating logics. We motivate our definition and demonstrate that it includes a variety of well-known default logics. Furthermore, we derive general results regarding the concepts of semi-monotonicity and cumulativity. As a benefit of the discussion we uncover that some design decisions of concrete default logics were not accidental as they may seem, but rather they were due to objective necessities.

Default reasoning is computationally expensive. One of the most promising ways of easing this problem and developing powerful implementations is to split a default theory into smaller parts and compute extensions in a modular, "local" way. Up to now, this idea has only been followed for Reiter's (1980) default logic, yet it is also relevant to other variants of default logic which have found increasing recognition in the past few years. This paper shows how it can be modified to work for several popular, alternative approaches of default reasoning: justified, constrained and rational default logic. This work defines the formal basis for a Web-based default reasoning system which is under development at our institution.

Anomalies such as redundant, contradictory, or deficient knowledge in a knowledge base indicate possible errors. Various methods for detecting such anomalies have been introduced, analyzed, and applied in the past years, but they usually deal with rule-based systems. So far, little attention has been paid to the verification and validation of more complex representations, such as nonmonotonic knowledge bases, although there are good reasons to expect that these technologies will be increasingly used in practical applications. This article does a step towards the verification of knowledge bases which include defaults by providing a theoretical foundation of correctness concepts and a classification of possible anomalies. It also points out how existing verification methods may be applied to detect some anomalies in nonmonotonic knowledge bases, and discusses methods of avoiding potential inconsistencies (in the context of default reasoning inconsistency means nonexistence of extensions). © 1997 John Wiley & Sons, Inc.

Abstract We present a module concept with algebraic interfaces and imperative implementation. It is shown that under some natural conditions, module correctness may be expressed in Hoare logic as a partial correctness assertion. Also, we discuss questions of practical verification of modules using Hoare's calculus.

A modularity concept for structuring and developing large logic programs and logical knowledge bases is presented. The concept is motivated from work in the field of algebraic specification, and enforces an extreme modularity discipline that goes beyond the one found in imperative or logic programming languages. As concrete programming languages (respectively knowledge representation formalisms), we consider Horn logic and equational logic programming. We give formal semantics for single modules and discuss correctness and verification issues. Large systems are constructed as interconnections of single modules. We introduce the so-called module operations of composition, actualization, and union, and give results concerning compositionality of semantics and correctness preservation.

The author argues that modularity is essential for the design, verification, and maintenance of large-scale knowledge based systems. Motivated by work on software modules and algebraic specification, he introduces a module concept with formal interfaces, and gives semantics and correctness notions for such modules based on logic programming. Single modules communicate with their environment by their interfaces. He discusses how modular systems can be built from single modules by means of so-called module operations, and derive for the composition operation results concerning compositionality of semantics and correctness preservation.>