Algernon and Access-Limited Logic
Access-limited logic, and its embodiment in a knowledge-representation
language named Algernon, has been a focus for research in the Qualitative Reasoning group.
News
(9-15-05)
The new implementation,
Algernon in Java,
created and maintained by Micheal Hewett, first at Stanford and now
at Hewett Research,
is available at SourceForge.
Access-Limited Logic is a language for representing knowledge in the
computer, and a method for drawing conclusions and answering questions
from that knowledge.
Previous languages and methods faced an apparently unsolvable conflict
between three important values: (1) having a clear and precise
meaning; (2) being computationally efficient; and (3) being able to
draw all correct conclusions eventually. Part of the efficiency
problem is that, out of a vast amount of knowledge, it is hard to find
the right facts and rules to bring together.
Like humans, access-limited logic uses the connections between related
concepts to focus its search for useful information. Although it is
possible to miss connections between concepts that lack an available
``access path,'' this method gives us values (1) and (2): clarity and
efficiency. As for value (3), known as ``completeness'', for a
language expressive enough for common-sense knowledge, it is
impossible to draw all correct conclusions efficiently. However, we
have shown that access-limited logic has the property of ``Socratic
completeness'': if a wise tutor asks the right series of questions,
any correct conclusion can be found (and each question will be
answered efficiently). Furthermore, for most common-sense knowledge,
the series of questions to ask can usually be found efficiently.
In addition to our theoretical work on Access-Limited Logic, we have
implemented a system named Algernon that embodies its principles.
Algernon has been used for the graduate expert systems course at UT,
for research toward at least four doctoral dissertations, and as a
research tool at UT, MCC, and Stanford University. MCC, in turn, has
distributed Algernon to its shareholders.
- Micheal Hewett. 1996.
Algernon v3 online documentation.
- B. J. Kuipers and J. M. Crawford. 1994.
Short Algernon Reference Manual (for Algernon version 1.3.0).
Unpublished manuscript.
- As of this writing (4-18-94), the reference manual may be more recent
than the file algernon.tar.Z.
- B. Kuipers. 1993.
Algernon for Expert Systems.
Unpublished manuscript.
- This evolving document illustrates how to write code in Algernon for
various useful tasks.
- Raman Rajagopalan. 1992.
Results of an experiment in domain knowledge base
construction: a comparison of the Classic and Algernon knowledge
representation systems. Working Papers of the AAAI Workshop on Tractable
Reasoning, AAAI-92, San Jose, CA, 1992.
- J. M. Crawford & B. J. Kuipers. 1991.
Algernon -- a tractable system for knowledge representation.
SIGART Bulletin 2(3): 35-44, June 1991.
[.pdf]
- J. M. Crawford & B. J. Kuipers. 1991.
Negation and proof by
contradiction in access-limited logic. In Proceedings of the National
Conference on Artificial Intelligence (AAAI-91), AAAI/MIT Press, 1991.
[.pdf]
- J. M. Crawford & B. J. Kuipers. 1991.
ALL: formalizing access-limited reasoning. In John Sowa (Ed.),
Principles of Semantic Networks, pp. 299-330. San Mateo, CA:
Morgan Kaufmann.
[.pdf]
- James Crawford. 1990.
Access-Limited Logic: A Language for
Knowledge Representation. Doctoral dissertation, Department of
Computer Sciences, University of Texas at Austin, Austin, Texas. UT
Artificial Intelligence TR AI90-141, October 1990.
[Table of Contents].
- This is the definitive formal description of Algernon.
- J. M. Crawford, A. Farquhar, B. J. Kuipers. 1990.
QPC: a
compiler from physical models into qualitative differential equations.
Proceedings of the National Conference on Artificial Intelligence
(AAAI-90), AAAI/MIT Press, 1990.
Revised version in Boi Faltings and
Peter Struss (Eds.), Recent Advances in Qualitative Physics, MIT
Press, 1992.
- J. M. Crawford and B. J. Kuipers. 1989.
Toward a theory of access-limited logic for knowledge representation.
In Proceedings of the First International Conference on Principles
of Knowledge Representation and Reasoning (KR'89). Los Altos,
CA: Morgan Kaufmann.
[.pdf]
Several doctoral dissertations have used Algernon as a central part of the
implementation.
- Chinatsu Aone. 1992. Treatment of plurals and
collective-distributive ambiguity in natural language understanding.
Doctoral dissertation, Department of Linguistics, The University of
Texas at Austin.
- Adam Farquhar. 1993.
Automated modeling of physical systems
in the presence of incomplete knowledge. University of Texas at
Austin, Artificial Intelligence Laboratory, Technical Report AI
93-207. (Doctoral dissertation, Department of Computer Sciences.)
- Jeff W. Rickel. 1995.
Automated modeling of complex
systems to answer prediction questions. Doctoral dissertation,
Department of Computer Sciences, The University of Texas at Austin.
(Available as technical report AI95-234.)
- Raman Rajagopalan. 1995.
Qualitative reasoning about
dynamic change in the spatial properties of a physical system.
Doctoral dissertation, Department of Computer Sciences, The University
of Texas at Austin. (Available as TR AI95-241.)
- Emilio Remolina. 2001.
A logical account of causal and topological maps.
Doctoral dissertation, Department of Computer Sciences,
The University of Texas at Austin.
Several other groups built software based on Algernon and Access-Limited Logic.
The source codes for Algernon and QPC are
available.
Ben Kuipers initially conceived of Algernon and Access-Limited Logic
as a synthesis of frames and logic-based approaches to knowledge
representation while teaching an undergraduate class on AI programming
methods. He has used Algernon as the programming vehicle for his
Expert Systems class at the University of Texas for a number of years.
James Crawford did all of the theory of Access-Limited Logic,
including inventing the key concept of "Socratic Completeness", and
did a near-complete reimplementation of Algernon. Crawford's PhD
thesis is the definitive description of Access-Limited Logic.
QPC, our compositional compiler for qualitative models, is implemented
in Algernon. This was initially a collaboration between Adam
Farquhar, James Crawford, and Ben Kuipers, and grew into Adam
Farquhar's PhD thesis.
Raman Rajagopalan and Jeff Rickel did their PhD research using QPC,
and were thus regular Algernon users.
Chinatsu Aone did a PhD thesis in linguistics on the understanding of
quantified expressions, and used Algernon as the knowledge
representation language. She convinced MCC to provide Algernon as one
of the knowledge representation languages for their NLKB (Natural
Language Knowledge Base) project.
Elias Costopoulos implemented Algernon in C++ for the PC.
Omid Sojoodi-Haghighi implemented the KM system based on the ideas in
Access-Limited Logic. KM is currently the
representation language for the Biology KB group.
Mike Hewett has reimplemented Algernon using the Algernon Abstract Machine.
[QR home]
BJK