Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-05T04:13:31.520Z Has data issue: false hasContentIssue false

Efficient knowledge representation systems

Published online by Cambridge University Press:  07 July 2009

Dario Giuse
Affiliation:
The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA

Abstract

Frame systems occupy an important place among formalisms for computer-based knowledge representation. A common concern about frame systems, however, is that they are not efficient enough. We argue that this is not necessarily true of all possible systems, and that the trade-off between generality and efficiency has not been fully explored. While many systems provide generality at the expense of performance, systems closer to the low end of the spectrum have not been investigated nearly as much. Those systems are well suited for applications that need flexible knowledge representation but cannot afford the high performance price.

We describe in detail KR, a very efficient frame system that provides mechanisms for knowledge representation including user-defined inheritance and relations, object-oriented programming, and constraint maintenance. The system is simple and compact and does not include some of the more complex functionality, but it is highly optimized and offers excellent performance for a variety of applications.

Type
Research Article
Copyright
Copyright © Cambridge University Press 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Anderson, JR and Bower, GH, 1973. Human Associative Memory. Holt, New York.Google Scholar
Bobrow, DG and Winograd, T, 1977. “An overview of KRL, a knowledge representation languageCognitive Science 1(1) 346.CrossRefGoogle Scholar
Bobrow, D et al. , 1985. ‘Common Loops: merging Common Lisp and object-oriented programming9th International Joint Conference on Artificial Intelligence.CrossRefGoogle Scholar
Bobrow, DG, DeMichiel, LG, Gabriel, RP, Keene, SE, Kiczales, G and Moon, DA, 1989. “Common lisp object system specificationLisp and Symbolic Computation 1(3/4) 245394.Google Scholar
Brachman, RJ, 1977. “A structural paradigm for representing knowledge” PhD Thesis, Harvard University, Cambridge, MA.Google Scholar
Brachman, RJ, 1979. “On the epistemological status of semantic networks” In: Associative Networks: Representation and Use of Knowledge by Computers, Academic Press, New York, pp. 350.CrossRefGoogle Scholar
Brachman, RJ, 1985. “‘I lied about the trees’, or, defauls and definitions in knowledge representationThe AI Magazine Fall. 8092.Google Scholar
Brachman, RJ and Levesque, HJ, 1985. Readings in Knowledge Representation. Morgan Kaufmann, Los Altos, CA.Google Scholar
Brachman, RJ and Schmolze, JG, 1983. “An overview of the KL-ONE knowledge representation systemCognitive Science. 9(2) 170216.Google Scholar
Clocksin, WF and Mellish, CS, 1981. Programming in Prolog. Springer-Verlag, Berlin, New York.Google Scholar
Davis, R, Buchanan, B and Shortliffe, E, 1975. Production Rules as a Representation for a Knowledge-Based Consultation Program. Tech. Rept. STAN-CS-75–591. Stanford Artificial Intelligence Laboratory.CrossRefGoogle Scholar
DeMichiel, LG, 1989. “Overview: the common lisp object systemLISP and Symbolic Computation. 1(3/4) 227244.CrossRefGoogle Scholar
Fahlman, SE, Hinton, GE and Sejnowski, TJ, 1983. “Massively Parallel Architectures for AI: NETL, Thistle, and Boltzmann MachinesProceedings of the AAAI-83 Conference.Washington, DC.Google Scholar
Feigenbaum, EA, McCorduck, P and Nii, HP, 1988. The Rise of the Expert Company. Times Books.Google Scholar
Feldman, JA, 1985. “Connectionist models and parallelism in high level visionComputer Visions, Graphics, and Image Processing 31 178200.Google Scholar
Fox, MS, Wright, JM and Adam, D, 1984. “Experiences with SRL: an analysis of a frame-based knowledge representation” First International Workshop on Export Database Systems.Google Scholar
Genesereth, MR and Nilsson, NJ, 1987. Logical foundations of artifical intelligence. Morgan Kaufmann, Los Altos, CA.Google Scholar
Giuse, D, 1987. KR: an Efficient Knowledge Representqtion System. Tech. Rept. CMU-RI-TR-87–23. The Robotics Institute, Carnegie-Mellon University.CrossRefGoogle Scholar
Giuse, D, 1988a. “LISP as a rapid prototyping environment: the Chinese TutorLISP and Symbolic Computation 1(2) 165184.CrossRefGoogle Scholar
Giuse, D, 1988b. “Intelligent tutoring systems for foreign language acquisitionProceedings of the Asia-Pacific Conference on Computer Education (APCCE 88).Shanghai,China, pp. 3358.Google Scholar
Hinton, GE, McClelland, JL and Rumelhart, DE, 1986. “Distributed representations” In Parallel Distributed Processing. Bradford Books, Cambridge, MA.Google Scholar
Knowledge Craft Reference Manual. 1986. Carnegie Group, Inc., Pittsburgh, PA.Google Scholar
Lieberman, H, 1986. “Using prototypical objects to implement shared behavior in object oriented systemsSigplan Notices 21(11) 214223. ACM Conference on Object-Oriented Programming Systems Languages and Applications; OOPSLA '86.CrossRefGoogle Scholar
Mac Randal, D, 1988. “Semantic networks” In Approaches to Knowledge Representation: An Introduction. Research Studies Press, Forest Grove, OR, pp. 4579.Google Scholar
McDonald, DB, 1987. CMU Common Lisp User's Manual – Mach/IBM RT PC Edition. Tech. Rept. CMU-CS-87–156. Computer Science Department, Carnegie-Mellon University.Google Scholar
Minsky, M, 1963. Computers and Thought. McGraw Hill, New York.Google Scholar
Myers, BA, 1988. The Garnet User Interface Development Environment: A Proposal. Tech. Rept. CMU-CS-88–153. Carnegie-Mellon University.Google Scholar
Myers, BA, Giuse, D, Dannenberg, RB, Vander Zanden, B, Kosbie, D, Marchal, P, Pervin, E and Kolojejchick, JA, 1989. The Garnet Toolkit Reference Manuals: Support for Highly-Interactive, Graphical User Interfaces in Lisp. Tech. Rept. CMU-CS-89–196. Carnegie Mellon University Computer Science Department.Google Scholar
Myers, BA, Vander Zanden, B and Dannenberg, RB, 1990. “Creating graphical objects by demonstration”, submitted for publication.Google Scholar
Nyberg, EH, 1988. The FrameKit user's guide. Center for Machine Translation. Carnegie Mellon University, March.Google Scholar
Quillian, MR, 1967. “Word concepts: a theory and simulation of some basic semantic capabilitiesBehavioral Science 12 (1967).CrossRefGoogle ScholarPubMed
Quillian, MR, 1968. “Semantic memory” In Semantic Information Processing. The MIT Press, Cambridge, MA, pp. 227270.Google Scholar
Rashid, RF, Accetta, M, Baron, R, Bolosky, W, Golub, D, Tevanian, A and Young, MW, 1986. “Mach: a new kernel foundation for UNIX development” Proceedings of Summer Usenix.Google Scholar
Roberts, RB and Goldstein, IP, 1977. The FRL Primer. Tech. Reot. 408. MIT AI Lab.Google Scholar
Shapiro, SC, 1977. “Representing and locating deduction rules in a semantic networkSIGART Newsletter 63 1418.Google Scholar
Sloman, A, 1985. “Why we need many knowledge representation formalisms” Tech. Rept. Cognitive Studies Research Papers, CSRP 052. School of Social Sciences, University of Sussex.Google Scholar
Steele, GL, 1984. Common LISP—The Language. Digital Press, Burlington, MA.Google Scholar
Szekely, PA and Myers, BA, 1988. “A user interface toolkit based on graphical objects and constraintsSigplan Notices 23(11) 3645.CrossRefGoogle Scholar
Tesler, L, 1981. “The Smalltalk environmentBYTE 8 90147.Google Scholar
Wilensky, R, 1984. “KODIAK: A knowledge representation languageProc. of the Sixth Annual Conference of the Cognitive Science Society.Boulder, CO, pp. 344353.Google Scholar
Wilensky, R, 1987. “Some problems and proposals for knowledge representation” Tech. Rept. 87–351. University of California, Computer Science Division.Google Scholar
Woods, WA, 1975. “What's in a link: foundations for semantic networks” In Representation and Understanding: Studies in Cognitive Science. Academic Press, New York, pp. 3582.CrossRefGoogle Scholar
Young, SR, Hauptmann, AG, Ward, WH, Smith, ET and Werner, P, 1989. “High-level knowledge sources in usable speech recognition systemsCommunications of the ACM 32(2) 183194.CrossRefGoogle Scholar