This paper combines two important directions of research in temporal resoning: that of finding maximal tractable subclasses of Allen's interval algebra, and that of reasoning with metric temporal information. Eight new maximal tractable subclasses of Allen's interval algebra are presented, some of them subsuming previously reported tractable algebras. The algebras allow for metric temporal constraints on interval starting or ending points, using the recent framework of Horn DLRs. Two of the algebras can express the notion of sequentiality between intervals, being the first such algebras admitting both qualitative and metric time.

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.

Touretzky (1984) proposed a formalism for nonmonotonic multiple inheritance reasoning which is sound in the presence of ambiguities and redundant links. We show that Touretzky's inheritance notion is NPhard, and thus, provided P#NP, computationally intractable. This result holds even when one only considers unambiguous, totally acyclic inheritance networks. A direct consequence of this result is that the conditioning strategy proposed by Touretzky to allow for fast parallel inference is also intractable. Therefore, it follows that nonmonotonic multiple inheritance hierarchies, although compact representations, may not allow for efficient retrieval of information as has been suggested in attempts to use such hierarchies, e.g., in NETL (Fahlman 1979). We also analyze the influence of various design choices made by Touretzky. We show that all versions of downward (coupled) inheritance, i.e., on-path or off-path preemption and skeptical or credulous reasoning, are intractable. However, tractability can be achieved when using upward (decoupled) inheritance.

A workshop on defeasible reasoning with specificity was held under the arch in St. Louis during April 1989, with support from AAAI and McDonnell Douglas, and the assistance of Rockwell Science Center Palo Alto and the Department of Computer Science of Washington University.

A workshop on defeasible reasoning with specificity was held under the arch in St. Louis during April 1989, with support from AAAI and McDonnell Douglas, and the assistance of Rockwell Science Center Palo Alto and the Department of Computer Science of Washington University.

After explicating the need for a large commonsense knowledge base spanning human consensus knowledge, we report on many of the lessons learned over the first five years of attempting its construction. We have come a long way in terms of methodology, representation language, techniques for efficient inferencing, the ontology of the knowledge base, and the environment and infrastructure in which the knowledge base is being built. We describe the evolution of Cyc and its current state and close with a look at our plans and expectations for the coming five years, including an argument for how and why the project might conclude at the end of this time.

In the emerge from a massive knowledge this subject.

In the emerge from a massive knowledge this subject.

After explicating the need for a large commonsense knowledge base spanning human consensus knowledge, we report on many of the lessons learned over the first five years of attempting its construction. We have come a long way in terms of methodology, representation language, techniques for efficient inferencing, the ontology of the knowledge base, and the environment and infrastructure in which the knowledge base is being built. We describe the evolution of Cyc and its current state and close with a look at our plans and expectations for the coming five years, including an argument for how and why the project might conclude at the end of this time.

The book under review here, Building Large Knowledge-Based Systems: Representation and Inference in the Cyc Project, describes progress so far in an attempt to build a system that is intended to exhibit general common-sense reasoning ability. This review first discusses aspects of the Cyc system, with a focus on important decisions made in designing its knowledge representation language, and on how claims about the performance of the system might be validated.‡ The review then turns to the book itself, discussing both its merits and its faults.