Mitchell, Tom, Levesque, Hector
Mitchell and Levesque provide commentary on the two AAAI Classic Paper awards, given at the AAAI-05 conference in Pittsburgh, Pennsylvania. The two winning papers were "Quantifying the Inductive Bias in Concept Learning," by David Haussler, and "Default Reasoning, Nonmonotonic Logics, and the Frame Problem," by Steve Hanks and Drew McDermott.
See also:A Fundamental Tradeoff in Knowledge Representation and Reasoning. Slides. Department of Computer and Information Science. Norwegian University of Science and Technology. IT3706 - Knowledge Representation and Modelling, 2005.Knowledge Representation and Reasoning. Morgan Kaufmann, 2004.Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1989.Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (1st ed.). James Allen, Ronald J. Brachman, Erik Sandewall, Hector J. Levesque, Ray Reiter, and Richard Fikes (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.Annual Review of Computer Science Vol. 1: 255-287
Typ ical inferences automatically computed by AI representation systems include inheritance of properties, set membership and set inclusion, part/subpart inferences, type subsumption, and resolution. Here we address a fundamental problem in the nature of the service to be provided by knowledge representation systems: the greater the expressiveness of the language for representing knowledge, the harder it becomes to compute the needed inferences (see  for an overview of this tradeoff). In this brief paper, we present a formal analysis of the computational cost of expressiveness in a simple frame-based description language. Intuitively, we think of concepts as representing individuals, and roles as representing relations between individuals.