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.

We describe a comprehensive framework for narrative understanding based on Episodic Logic (EL). This situational logic was developed and implemented as a semantic representation and commonsense knowledge representation that would serve the full range of interpretive and inferential needs of general NLU. The most distinctive feature of EL is its natural language-like expressiveness. It allows for generalized quantifiers, lambda abstraction, sentence and predicate modifiers, sentence and predicate reification, intensional predicates (corresponding to wanting, believing, making, etc.), unreliable generalizations, and perhaps most importantly, explicit situational variables (denoting episodes, events, states of affairs, etc.) linked to arbitrary formulas that describe them. These allow episodes to be explicitly related in terms of part-whole, temporal and causal relations. Episodic logical form is easily computed from surface syntax and lends itself to effective inference.

Problem solving with incomplete information is usually very costly, since multiple alternatives must be taken into account in the planning pro cess. In this paper, we present some pruning rules that lead to substantial cost savings. The rules are all based on the simple idea that, if goal achievement is the sole criterion for performance, a planner need not consider one "branch" in its search space when there is another "branch" characterized by equal or greater information. The idea is worked out for the cases of sequential planning, conditional planning, and interleaved planning and execution. The rules are of special value in this last case, as they provide a way for the problem solver to terminate its search without planning all the way to the goal and yet be assured that no important alternatives are overlooked.

Allen Newell was one of the founders and truly great scientists of AI. His contributions included foundational concepts and ground-breaking systems. His career was defined by the pursuit of a single, fundamental issue: the nature of the human mind. This article traces his pursuit from his early work on search and list processing in systems such as the LOGIC THEORIST and the GENERAL PROBLEM SOLVER; through his work on problem spaces, human problem solving, and production systems; through his final work on unified theories of cognition and SOAR.

The Digital Services Research Group and its predecessor groups and offshoots in Digital Equipment Corporation have been mobilizing leading-edge AI research to bear on real-life problems that face the corporation and its customers. The general strategy of the group is to explore emerging techniques relevant to service and support needs through developing rapid prototypes, deploying these prototypes, and incorporating feedback from users. With over 32 major projects undertaken during the past decade, we have worked on broad spectrum of problems and explored a variety of advanced AI techniques. This article describes the current AI activities in five areas: (1) enterprise advisory systems, (2) natural language processing and textual information retrieval, (3) largescale knowledge base management and access, (4) software configuration management, and (5) intrusion detection. We also list some future research directions.

Allen Newell was one of the founders and truly great scientists of AI. His contributions included foundational concepts and ground-breaking systems. His career was defined by the pursuit of a single, fundamental issue: the nature of the human mind. This article traces his pursuit from his early work on search and list processing in systems such as the LOGIC THEORIST and the GENERAL PROBLEM SOLVER; through his work on problem spaces, human problem solving, and production systems; through his final work on unified theories of cognition and SOAR.

The Association for the Advancement of Artificial Intelligence held its 1992 Spring Symposium Series on March 25-27 at Stanford University, Stanford, California. This article contains a summary of the symposia that were conducted: Artificial Intelligence in Medicine, Cognitive Aspects of Knowledge Acquisition, Computational Considerations in Supporting Incremental Modification and Reuse, Knowledge Assimilation, Practical Approaches to Scheduling and Planning, Producing Cooperative Explanations, Propositional Knowledge Representation, Selective Perception, and Reasoning with Diagrammatic Representations.

An effective to develop an abstract UI model which solution to this problem must have three encompasses the essence of those systems.

My Ph.D. dissertation (Goel 1989) presents a computational model of experience-based design. It first reviews the core issues in experience-based design, for example, (1) the content of a design experience (or case), (2) the internal organization of design cases, (3) the language for indexing the cases, (4) the mechanism for retrieving a case relevant to a given design task, (5) the mechanism for adapting a retrieved design to satisfy the constraints of the design task, (6) the mechanism for evaluating a design against the specification of the design task, (7) the mechanism for redesigning a failed design, (8) the mechanism for acquiring new design knowledge, (9) the mechanism for chunking information about a design into a new case, and (10) the mechanism for storing a new case in memory for potential reuse in the future. It then proposes that decisions about these issues might lie in the designer's comprehension of the designs of artifacts he/she has encountered in the past, that is, in his/her mental models of how the designs achieve the functions and satisfy the constraints of the artifacts.

The Association for the Advancement of Artificial Intelligence held its 1991 Fall Symposium Series on November 15-17 at the Asilomar Conference Center, Pacific Grove, California. This article contains summaries of the four symposia: Discourse Structure in Natural Language Understanding and Generation, Knowledge and Action at Social and Organizational Levels, Principles of Hybrid Reasoning, Sensory Aspects of Robotic Intelligence.