This paper introduces a new methodology of revising general KBs in DL-Lite. Two specific revision operators are defined, their properties are investigated and algorithms for computing revisions are developed.

Research effort, with its emphasis on evaluation and measurable progress, things began to change. Instead SHRDLU (WIN72) is perhaps the canonical example. of systems whose architecture and vocabulary were The rapid growth of efforts to found the next generation of based on linguistic theory (in this case acoustic phonetics), systems on general-purpose knowledge representation languages new approaches based on statistical modelling and Bayesian (I'm thinking of several varieties of semantic nets, probability emerged and quickly spread. "Every time I fire a from plain to partitioned, as well as KRL, KL-ONE and linguist my system's performance improves" (Fred Jellinek, their successors, ending (not yet, of course) with CYC (See head of speech recognition at IBM, c. 1980, latterly repudiated (BRA08) for all these) stumbled to a halt once their failure by Fred but widely attested). As advanced from resolution theorem provers through a number more and more problems are re-conceived as instances of of stages to the current proliferation of a range of Description the noisy channel model, the empiricist paradigm continually Logic'reasoners'; Whereas in the 1970s and 1980s there grew, so did the need to manage the impact of change and was real energy and optimism at the interface between computational conflict: enter'truth maintenance', subsequently renamed and theoretical linguistics, the overwhelming success'reason maintenance'. While still using some of But outflanking these'normal science' advances of AI, the terminology of linguistic theory, computational linguistics the paradigm shifters were coming up fast on the outside: practioners are increasingly detached from theory itself, over the last ten years machine learning has spread from which has suffered a, perhaps connected, loss of energy and small specialist niches such as speech recognition to become sense of progress.

Fuzzy Description Logics (DLs) are a family of logics which allow the representation of (and the reasoning with) structured knowledge affected by vagueness. Although most of the not very expressive crisp DLs, such as ALC, enjoy the Finite Model Property (FMP), this is not the case once we move into the fuzzy case. In this paper we show that if we allow arbitrary knowledge bases, then the fuzzy DLs ALC under Lukasiewicz and Product fuzzy logics do not verify the FMP even if we restrict to witnessed models; in other words, finite satisfiability and witnessed satisfiability are different for arbitrary knowledge bases. The aim of this paper is to point out the failure of FMP because it affects several algorithms published in the literature for reasoning under fuzzy ALC.

This article surveys previous work on combining planning techniques with expressive representations of knowledge in description logics to reason about tasks, plans, and goals. Description logics can reason about the logical definition of a class and automatically infer class-subclass subsumption relations as well as classify instances into classes based on their definitions. Descriptions of actions, plans, and goals can be exploited during plan generation, plan recognition, or plan evaluation. Another emerging use of these techniques is the semantic web, where current ontology languages based on description logics need to be extended to reason about goals and capabilities for web services and agents.

This article surveys previous work on combining planning techniques with expressive representations of knowledge in description logics to reason about tasks, plans, and goals. Description logics can reason about the logical definition of a class and automatically infer class-subclass subsumption relations as well as classify instances into classes based on their definitions. Descriptions of actions, plans, and goals can be exploited during plan generation, plan recognition, or plan evaluation. These techniques should be of interest to planning practitioners working on knowledge-rich application domains. Another emerging use of these techniques is the semantic web, where current ontology languages based on description logics need to be extended to reason about goals and capabilities for web services and agents.

Data integration is the problem of combining data residing at different autonomous, heterogeneous sources and providing the client with a unified, reconciled global view of the data. We discuss dataintegration systems, taking the abstract viewpoint that the global view is an ontology expressed in a class-based formalism. We resort to an expressive description logic, ALCQI, that fully captures classbased representation formalisms, and we show that query answering in data integration, as well as all other relevant reasoning tasks, is decidable. However, when we have to deal with large amounts of data, the high computational complexity in the size of the data makes the use of a fullfledged expressive description logic infeasible in practice. This leads us to consider DL-Lite, a specifically tailored restriction of ALCQI that ensures tractability of query answering in data integration while keeping enough expressive power to capture the most relevant features of class-based formalisms.

We study the complexity of the combination of the Description Logics ALCQ and ALCQI with a terminological formalism based on cardinality restrictions on concepts. These combinations can naturally be embedded into C^2, the two variable fragment of predicate logic with counting quantifiers, which yields decidability in NExpTime. We show that this approach leads to an optimal solution for ALCQI, as ALCQI with cardinality restrictions has the same complexity as C^2 (NExpTime-complete). In contrast, we show that for ALCQ, the problem can be solved in ExpTime. This result is obtained by a reduction of reasoning with cardinality restrictions to reasoning with the (in general weaker) terminological formalism of general axioms for ALCQ extended with nominals. Using the same reduction, we show that, for the extension of ALCQI with nominals, reasoning with general axioms is a NExpTime-complete problem. Finally, we sharpen this result and show that pure concept satisfiability for ALCQI with nominals is NExpTime-complete. Without nominals, this problem is known to be PSpace-complete.

A class of interval-based temporal languages for uniformly representing and reasoning about actions and plans is presented. Actions are represented by describing what is true while the action itself is occurring, and plans are constructed by temporally relating actions and world states. The temporal languages are members of the family of Description Logics, which are characterized by high expressivity combined with good computational properties. The subsumption problem for a class of temporal Description Logics is investigated and sound and complete decision procedures are given. The basic language TL-F is considered first: it is the composition of a temporal logic TL -- able to express interval temporal networks -- together with the non-temporal logic F -- a Feature Description Logic. It is proven that subsumption in this language is an NP-complete problem. Then it is shown how to reason with the more expressive languages TLU-FU and TL-ALCF. The former adds disjunction both at the temporal and non-temporal sides of the language, the latter extends the non-temporal side with set-valued features (i.e., roles) and a propositionally complete language.

Most modern formalisms used in Databases and Artificial Intelligence for describing an application domain are based on the notions of class (or concept) and relationship among classes. One interesting feature of such formalisms is the possibility of defining a class, i.e., providing a set of properties that precisely characterize the instances of the class. Many recent articles point out that there are several ways of assigning a meaning to a class definition containing some sort of recursion. In this paper, we argue that, instead of choosing a single style of semantics, we achieve better results by adopting a formalism that allows for different semantics to coexist. We demonstrate the feasibility of our argument, by presenting a knowledge representation formalism, the description logic muALCQ, with the above characteristics. In addition to the constructs for conjunction, disjunction, negation, quantifiers, and qualified number restrictions, muALCQ includes special fixpoint constructs to express (suitably interpreted) recursive definitions. These constructs enable the usual frame-based descriptions to be combined with definitions of recursive data structures such as directed acyclic graphs, lists, streams, etc. We establish several properties of muALCQ, including the decidability and the computational complexity of reasoning, by formulating a correspondence with a particular modal logic of programs called the modal mu-calculus.

This paper analyzes the correctness of the subsumption algorithm used in CLASSIC, a description logic-based knowledge representation system that is being used in practical applications. In order to deal efficiently with individuals in CLASSIC descriptions, the developers have had to use an algorithm that is incomplete with respect to the standard, model-theoretic semantics for description logics. We provide a variant semantics for descriptions with respect to which the current implementation is complete, and which can be independently motivated. The soundness and completeness of the polynomial-time subsumption algorithm is established using description graphs, which are an abstracted version of the implementation structures used in CLASSIC, and are of independent interest.