Non-monotonic reasoning is essential for drawing plausible conclusions from incomplete information. Many approaches model changing belief states using Ordinal Conditional Functions (OCFs), which assign degrees of surprise to possible worlds. This paper demonstrates how OCFs are ideally suited for the knowledge compilation paradigm, particularly with Binary Decision Diagrams (BDDs). We introduce a compilation pipeline for System Z, a prominent ranking-based semantics, which pre-compiles a conditional knowledge base into a set of materialized theories represented by BDDs. This compilation enables polynomial-time conditional entailment and efficient, incremental updates, avoiding costly re-computation. We further extend this approach using Algebraic Decision Diagrams (ADDs) to directly compile the entire ranking function, facilitating direct and efficient implementation of complex belief revision operations such as Spohn conditioning.

Description Logics (DLs) are widely applied in AI and database systems. However, like other classical logics, they cannot adequately handle defeasible information. Building on the notion of rational closure - a form of defeasible reasoning originally developed for the propositional setting and later adapted to DLs - we extend this approach by incorporating two further forms of defeasible reasoning: System W and lexicographic closure. Both are well-established entailment relations in the propositional case and are known to satisfy several desirable properties. In this paper, we provide model-theoretic definitions of these extensions for DLs, analyze their behaviour by relating them to their propositional counterparts, and present algorithms for their computation.

Inductive inference is a well-studied form of nonmonotonic reasoning in which various inference is based on conditional belief bases rather than belief bases consisting of classical logic statements. Given its nonmonotonic nature, many important logical properties that are taken for granted in the classical case do not necessarily carry over to inference involving conditionals. In this paper we consider two such properties---equivalence and language-independence. More specifically, we provide different notions of equivalence in the conditional case, and show which of these are satisfied by which forms of conditional inference. Similarly, we consider different versions of language independence, and test various forms of conditional inference against these. As its main overall contribution, the paper provides deeper theoretical insights into the field of inductive inference.

Syntax splitting is a property of inductive inference operators that ensures we can restrict our attention to parts of the conditional belief base that share atoms with a given query. To apply syntax splitting, a conditional belief base needs to consist of syntactically disjoint conditionals. This requirement is often too strong in practice, as conditionals might share atoms. In this paper we introduce the concept of conditional syntax splitting, inspired by the notion of conditional independence as known from probability theory. We show that lexicographic inference and system W satisfy conditional syntax splitting, and connect conditional syntax splitting to several known properties from the literature on non-monotonic reasoning, including the drowning effect.

Propositional Typicality Logic (PTL) extends propositional logic with a connective • expressing the most typical (alias normal or conventional) situations in which a given sentence holds. As such, it generalises e.g.~preferential logics that formalise reasoning with conditionals such as ``birds typically fly''. In this paper, we study revision of sets of PTL-sentences. We first show why it is necessary to extend the PTL-language with a possibility operator, and then define the revision of PTL-sentences syntactically and characterise it semantically. We show that this allows us to represent a wide variety of existing revision methods, such as propositional revision and revision of epistemic states. Furthermore, we provide several examples showing why our approach is innovative. In more detail, we study revision of a set of conditionals under preferential closure, and the addition and contraction of possible worlds from an epistemic state.

Lexicographic inference is a well-known and popular approach to reasoning with non-monotonic conditionals. It is a logic of very high-quality, as it extends rational closure and avoids the so-called drowning problem. It seems, however, this high quality comes at a cost, as reasoning on the basis of lexicographic inference is of high computational complexity. In this paper, we show that lexicographic inference satisfies syntax splitting, which means that we can restrict our attention to parts of the belief base that share atoms with a given query, thus seriously restricting the computational costs for many concrete queries. Furthermore, we make some observations on the relationship between c-representations and lexicographic inference, and reflect on the relation between syntax splitting and the drowning problem.

We extend the expressivity of classical conditional reasoning by introducing context as a new parameter. The enriched conditional logic generalises the defeasible setting in the style of Kraus, Lehmann and Magidor, and allows for a more refined representation of an agent’s epistemic state, distinguishing, for example, between expectations and counterfactuals. In this paper we introduce the language for the enriched logic, and define an appropriate semantic framework for it. We analyse which properties generally associated with conditional reasoning are still satisfied by the new semantic framework, provide an appropriate representation result, and define an entailment relation based on Lehmann and Magidor’s notion of Rational Closure.

The past 25 years have seen many attempts to introduce defeasible-reasoning capabilities into a description logic setting. Many, if not most, of these attempts are based on preferential extensions of description logics, with a significant number of these, in turn, following the so-called KLM approach to defeasible reasoning initially advocated for propositional logic by Kraus, Lehmann, and Magidor. Each of these attempts has its own aim of investigating particular constructions and variants of the (KLM-style) preferential approach. Here our aim is to provide a comprehensive study of the formal foundations of preferential defeasible reasoning for description logics in the KLM tradition. We start by investigating a notion ofdefeasible subsumptionin the spirit of defeasible conditionals as studied by Kraus, Lehmann, and Magidor in the propositional case. In particular, we consider a natural and intuitive semantics for defeasible subsumption, and we investigate KLM-style syntactic properties for bothpreferentialandrationalsubsumption. Our contribution includes two representation results linking our semantic constructions to the set of preferential and rational properties considered. Besides showing that our semantics is appropriate, these results pave the way for more effective decision procedures for defeasible reasoning in description logics. Indeed, we also analyse the problem of non-monotonic reasoning in description logics at the level ofentailmentand present an algorithm for the computation ofrational closureof a defeasible knowledge base. Importantly, our algorithm relies completely on classical entailment and shows that the computational complexity of reasoning over defeasible knowledge bases is no worse than that of reasoning in the underlying classical DLALC.

Abstract Description logics (DLs) are well-known knowledge representation formalisms focused on the representation of terminological knowledge. Due to their first-order semantics, these languages (in their classical form) are not suitable for representing and handling uncertainty. A probabilistic extension of a light-weight DL was recently proposed for dealing with certain knowledge occurring in uncertain contexts. In this paper, we continue that line of research by introducing the Bayesian extension of the propositionally closed DL . We present a tableau-based procedure for deciding consistency and adapt it to solve other probabilistic, contextual, and general inferences in this logic. We also show that all these problems remain ExpTime-complete, the same as reasoning in the underlying classical .

We present a formal framework for modelling belief change within a nonmonotonic reasoning system. Belief change and non-monotonic reasoning are two areas that are formally closely related, with recent attention being paid towards the analysis of belief change within a non-monotonic environment. In this paper we consider the classical AGM belief change operators, contraction and revision, applied to a defeasible setting in the style of Kraus, Lehmann, and Magidor. The investigation leads us to the consideration of the problem of iterated change, generalising the classical work of Darwiche and Pearl. We characterise a family of operators for iterated revision, followed by an analogous characterisation of operators for iterated contraction. We start considering belief change operators aimed at preserving logical consistency, and then characterise analogous operators aimed at the preservation of coherence—an important notion within the field of logic-based ontologies.

In this paper we introduce and investigate a very basic semantics for conditionals that can be used to define a broad class of conditional reasoning. We show that it encompasses the most popular kinds of conditional reasoning developed in logic-based KR. It turns out that the semantics we propose is appropriate for a structural analysis of those conditionals that do not satisfy the property of Right Weakening. We show that it can be used for the further development of an analysis of the notion of relevance in conditional reasoning.

Belief change and non-monotonic reasoning are usually viewed as two sides of the same coin, with results showing that one can formally be defined in terms of the other. In this paper we show that it also makes sense to analyse belief change within a (preferential) non-monotonic framework. We consider belief change operators in a non-monotonic propositional setting with a view towards preserving consistency. We show that the results obtained can also be applied to the preservation of coherence— an important notion within the field of logic-based ontologies. We adopt the AGM approach to belief change and show that standard AGM can be adapted to a preferential non-monotonic framework, with the definition of expansion, contraction, and revision operators, and corresponding representation results.

We propose a method for an agent to revise its incomplete probabilistic beliefs when a new piece of propositional information is observed. In this work, an agent's beliefs are represented by a set of probabilistic formulae – a belief base. The method involves determining a representative set of ‘boundary’ probability distributions consistent with the current belief base, revising each of these probability distributions and then translating the revised information into a new belief base. We use a version of Lewis Imaging as the revision operation. The correctness of the approach is proved. An analysis of the approach is done against six rationality postulates. The expressivity of the belief bases under consideration are rather restricted, but has some applications. We also discuss methods of belief base revision employing the notion of optimum entropy, and point out some of the benefits and difficulties in those methods. Both the boundary distribution method and the optimum entropy methods are reasonable, yet yield different results.

Like other real-world problems, reasoning in clinical depression presents cognitive challenges for clinicians. This is due to the presence of co-occuring diseases, incomplete data, uncertain knowledge, and the vast amount of data to be analysed. Current approaches rely heavily on the experience, knowledge, and subjective opinions of clinicians, creating scalability issues. Automating this process requires a good knowledge representation technique to capture the knowledge of the domain experts, and multidimensional inferential reasoning approaches that can utilise a few bits and pieces of information for efficient reasoning. This study presents knowledge-based system with variants of Bayesian network models for efficient inferential reasoning, translating from available fragmented depression data to the desired information in a visually interpretable and transparent manner. Mutual information, a Conditional independence test-based method was used to learn the classifiers.

We show that Booth et al.'s Horn contraction based on infra-remainder sets corresponds exactly to kernel contraction for belief sets. This result is obtained via a detour through Horn contraction for belief bases, which supports the conjecture that Horn belief change is best viewed as a “hybrid” version of belief set change and belief base change. Moreover, the link with base contraction gives us a more elegant representation result for Horn contraction for belief sets in which a version of the Core-retainment postulate features.

This special issue of the Expert Systems journal addresses research issues on ontology, an area that is receiving increased attention from researchers on the semantic web. According to Gruber (1993), an ontology is an explicit specification of a conceptualization, i.e. an abstract, simplified view of the world that includes the objects, concepts and the relationships between them in a domain of interest. The use of formal ontologies in knowledge systems has many advantages. It allows an unambiguous specification of the structure of knowledge in a domain, enables knowledge sharing and reuse and, consequently, makes automated reasoning about ontologies possible. In recent years, there has been a worldwide increase in the use of ontologies, both in industry and in research laboratories. This special issue presents the recent advances, both in theory and practical applications, of ontologies to a general audience and provides an opportunity for the broader expert systems community to become aware of current ontology research. There was an overwhelming interest in the general call for papers for the special issue. We received 24 high quality submissions from researchers in Argentina, Australia, Brazil, France, Iran, Japan, Spain, Taiwan, Republic of China, Turkey and the USA. Each submission was sent to at least two reviewers who are experts in ontology research and closely related areas. Although we judged many more submissions to be publishable, we could only include eight papers in the special issue due to time and space limitations. A few high quality papers that we could not accommodate in the special issue were referred to regular issues of Expert Systems. The submissions also included the revised and extended versions of a number of papers selected from among those presented at the Australasian Ontology Workshop (AOW 2006) (Orgun & Meyer, 2006). AOW 2006 was held on 5 December 2006 in conjunction with the 19th Australian Joint Conference on Artificial Intelligence in Hobart, Tasmania, Australia. The purpose of the AOW workshop series is to bring together ontology researchers from academia and industry in the Australasian region for interaction, discussion, sharing of results and initiation of new projects, and also to raise the awareness of the Australasian artificial intelligence community to state-of-the-art ontology research conducted in the region. This special issue is further testament to the vibrant ontology research conducted within the Australasian region, and its strong connections with the international ontology community. We trust that the breadth and diversity of the papers published in this special issue will foster further research on ontologies ranging from theoretical to practical issues and to applications. The special issue starts off with papers on interoperability in ontologies and ontology merging, alignment and integration. Semantic interoperability between ontologies is essential for enabling communication and sharing of information between heterogeneous systems. The paper by Orgun et al. surveys the main approaches for semantic interoperability between domain ontologies. The authors critically examine various approaches based on the underlying technology used, i.e. agent- or non-agent-based, the degree of automation and the use of intermediaries such as lexicons and meta-ontologies. Their conclusion is that if ontologies for the semantic web are to realize their full potential, it is important to work towards full automation of the semantic translation between ontologies. The paper by Li and Yang discusses a novel agent-based approach for ontology mapping and integration. Their main aim is to identify the main tasks of ontology mapping and integration and assign them to different agents, with the purpose of providing a runtime environment for dynamic ontology management. This work leverages agent technology, and it is a step towards the full automation envisioned in the paper by Orgun et al. The paper by Qazvinian et al. proposes an evolutionary approach based on genetic algorithms to extract an optimal mapping in ontology matching. The main idea here is to transform the ontology alignment problem into an optimization problem based on maximizing the overall similarity between entities among two ontologies. The paper by Hooijmaijers and Stumptner addresses how ontology integration can be enhanced by considering author information, trust and credibility. It is observed that, by annotating ontologies with author information and trust ratings, the user is provided with extra flexibility when making decisions based on queries to an integrated ontology. Trust is a key concept in agent-based systems operating in dynamic environments such as the semantic web (Golbeck et al., 2003) and it should not come as a surprise that it should also play an important role in ontology integration. The next two papers further explore the design and implementation of content languages for the semantic web (Berners-Lee et al., 2001). Effective communication between agents operating on behalf of humans is essential to realize the ultimate goal of the semantic web. The paper by Schwitter and Tilbrook proposes a novel approach to support the creation of meaningful web annotations in a controlled natural language. The authors advance the thesis that, rather than using a formal language, a well-defined controlled natural language enables human annotators to summarize the contents of a website better. Annotations are then transformed into a machine-processable form based on predicate logic and checked for consistency and informativeness for question-answering. The paper by Erdur and Seylan starts with the well-known OWL Web Ontology Language (Smith et al., 2004) and bases their content language for agent communication on a hybrid description logic which allows for the representation and reasoning about beliefs and intentions of agents. As a result, it is shown that agents can conform to the semantics of agent communication that is explained in terms of the mental states of the participants. The last two papers address different topics. The paper by Lefort, Taylor and Ratcliffe provides an empirical study of description logic reasoners in building and maintaining large part–whole ontologies such as those used in supply-chain management or reliability assessment in the aerospace industry. The study starts with the transformation of large-scale part–whole hierarchies into ontologies based on two best practice ontology engineering patterns, and then feeds them to a number of description logic reasoners for performance benchmarking. The empirical study shows that a particular ontology engineering pattern (the use of right-identity axioms supported by the EL+description logic) results in better reasoner performance. The paper by Valencia-García et al. addresses the difficult task of learning ontologies from natural language documents. The presented semi-automatic methodology is driven by knowledge engineering techniques such as incremental knowledge acquisition from domain experts and natural language techniques such as part-of-speech tagging. It supports multiple semantic relationships between concepts in an ontology and is able to detect inconsistencies in the resulting ontologies. Many individuals contributed to this special issue. First, we would like to thank the Editor-in-Chief of Expert Systems, Lucia Rapanotti, for her enthusiasm and continuing support for the special issue. Second, we are also indebted to the authors of the 24 submissions who responded to the call for papers in early 2007. This special issue would not have been possible without their submissions. Last but not the least, we would like express our appreciation to our reviewers; they generously donated their time and expertise in reading the submissions and providing very detailed and constructive comments for the authors; we would like to thank them all: Mike Bain (University of New South Wales, Australia) Richard Booth (Mahasarakham University, Thailand) Werner Ceusters (SUNY Buffalo, USA) Samir Chopra (CUNY Brooklyn, USA) Bob Colomb (University of Queensland, Australia) Stephen Cranefield (University of Otago, New Zealand) Anne Cregan (NICTA and University of New South Wales, Australia) Peter Eklund (University of Wollongong, Australia) Atilla Elçi (Eastern Mediterranean University, Turkey) Giorgos Flouris (FORTH, Greece) Vadim Gerasimov (CSIRO, Australia) Aurona Gerber (Meraka Institute, South Africa) Manolis Gergatsoulis (Ionian University, Greece) Aditya Ghose (University of Wollongong, Australia) Guido Governatori (University of Queensland, Australia) Warwick Graco (Australian Taxation Office, Australia) Fikret Gürgen (Boḡaziçi University, Turkey) Dennis Hooijmaijers (University of South Australia, Australia) Bo Hu (University of Southampton, UK) Laurent Lefort (CSIRO, Australia) Costas Mantratzis (University of Westminster, UK) Philippe Martin (Griffith University, Australia) Lars Mönch (University of Hagen, Germany) Abhaya Nayak (Macquarie University, Australia) Bhavna Orgun (Macquarie University, Australia) Maurice Pagnucco (University of New South Wales, Australia) Jeff Pan (University of Aberdeen, UK) Laurent Perrussel (IRIT – Université Toulouse, France) Anet Potgieter (University of Cape Town, South Africa) Quentin Reul (University of Aberdeen, UK) Debbie Richards (Macquarie University, Australia) Jennifer Sampson (NICTA, Australia) Rolf Schwitter (Macquarie University, Australia) Steven Shapiro (University of Leipzig, Germany) Kerry Taylor (CSIRO, Australia) Jean-Marc Thevenin (IRIT – Université Toulouse, France) Olga de Troyer (Vrije Universiteit Brussel, Belgium) Chao Wang (Universiy of Technology, Sydney, Australia) Wayne Wobcke (University of New South Wales, Australia) Pιnar Yolum (Boḡaziçi University, Turkey) Minjie Zhang (University of Wollongong, Australia) Mehmet A. Orgun Mehmet A. Orgun is an associate professor at Macquarie University, Sydney, Australia. He received his BSc and MSc degrees in computer science and engineering from Hacettepe University, Ankara, Turkey, and his PhD degree in computer science from the University of Victoria, Canada, in 1991. Prior to joining Macquarie University as a lecturer in September 1992, he worked as a postdoctoral research associate at the University of Victoria in the Rigi project on software reverse engineering. His current research interests include intelligent agents, temporal reasoning, knowledge discovery and reactive and distributed systems. He is co-founder of the Intelligent Systems Group at Macquarie University. He has authored and co-authored more than 120 peer-reviewed technical papers. He has received funding for his research programme from the Australian Research Council and Macquarie University. He serves on the editorial boards of the Journal of Universal Computer Science and the Open Cybernetics and Systemics Journal. He recently served as the workshop co-chair of the Second Australasian Ontology Workshop (AOW 2006) and the 2nd IEEE International Workshop on Engineering Semantic Agent Systems (ESAS 2007). He was the Program Committee co-chair of the 20th Australian Joint Conference on Artificial Intelligence (AI'07). He is also serving as the workshop co-chair of the 32nd Annual IEEE International Computer Software and Applications Conference (COMPSAC 2008). He is a senior member of the IEEE. Thomas Meyer Thomas Meyer is a principal researcher and research group leader of the Knowledge Systems Group at the Meraka Institute, Pretoria, South Africa. He was a senior researcher in the Knowledge Representation and Reasoning program at NICTA, Sydney, Australia, from 2003 to 2007. During that time he also had a conjoint appointment as associate professor in the School of Computer Science at the University of New South Wales, Sydney. Prior to that he held positions as associate professor in computer science at the University of Pretoria, senior lecturer in computer science at the University of South Africa, Pretoria, and postdoctoral research fellow in information systems at the University of Wollongong, Australia. He obtained a PhD in computer science from the University of South Africa in 1999. He is interested in the reasoning capabilities of agents, both human and artificial. His current research interests include reasoning about ontologies using description logics, non-standard inference, dealing with preferences, and constraints. Thomas has authored and co-authored more than 90 technical papers in peer-reviewed conferences and workshops. He is on the programme committee of numerous conferences and workshops, including the AAAI Conference on Artificial Intelligence and the European Conference on Artificial Intelligence. He is co-chair of the Australasian Ontology Workshop series, and publicity chair for KR 2008: Eleventh International Conference on Principles of Knowledge Representation and Reasoning.

As partial justification of their framework for iterated belief revision Darwiche and Pearl convincingly argued against Boutilier's natural revision and provided a prototypical revision operator that fits into their scheme. We show that the Darwiche-Pearl arguments lead naturally to the acceptance of a smaller class of operators which we refer to as admissible. Admissible revision ensures that the penultimate input is not ignored completely, thereby eliminating natural revision, but includes the Darwiche-Pearl operator, Nayak's lexicographic revision operator, and a newly introduced operator called restrained revision. We demonstrate that restrained revision is the most conservative of admissible revision operators, effecting as few changes as possible, while lexicographic revision is the least conservative, and point out that restrained revision can also be viewed as a composite operator, consisting of natural revision preceded by an application of a "backwards revision" operator previously studied by Papini. Finally, we propose the establishment of a principled approach for choosing an appropriate revision operator in different contexts and discuss future work.

We provide a formal study of belief retraction operators that do not necessarily satisfy the (Inclusion) postulate. Our intuition is that a rational description of belief change must do justice to cases in which dropping a belief can lead to the inclusion, or ‘liberation’, of others in an agent’s corpus. We provide two models of liberation via retraction operators: σ-liberation and linear liberation. We show that the class of σ-liberation operators is included in the class of linear ones and provide axiomatic characterisations for each class. We show how any retraction operator (including the liberation operators) can be ‘converted’ into either a withdrawal operator (i.e., satisfying (Inclusion)) or a revision operator via (a slight variant of) the Harper Identity and the Levi Identity respectively.