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.

Brief Overview

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.

People

Papers

Applications

Several doctoral dissertations have used Algernon as a central part of the implementation. Several other groups built software based on Algernon and Access-Limited Logic.

Software

The source codes for Algernon and QPC are available.

Algernon Users and History

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