Knowledge Embedding in the Description System Omega

Carl Hewitt, Giuseppe Attardi, Maria SimiAAAI 1980

This 1980 paper from the early days of Artificial Intelligence introduces Omega, a "description system" designed to bridge the gap between the rigid world of formal logic and the flexible, often messy world of human knowledge representation.

The Knowledge Representation Dilemma

In the late 1970s, AI researchers faced a significant hurdle. On one hand, First Order Logic (FOL) offered a powerful, mathematically sound way to represent theories, but it was often clunky and unsatisfactory for embedding real-world computer knowledge. On the other hand, a flurry of "knowledge representation languages" (like KRL, FRL, and PLANNER) had emerged. These were more intuitive for engineers—using concepts like "frames" or "property lists"—but they lacked rigorous semantics. Their "rules" were often just whatever the large, convoluted Lisp programs implementing them happened to do.

The authors (Hewitt, Attardi, and Simi) sought to create a system that had the best of both worlds: the structural convenience of frames and the formal axiomatization of logic.

The Omega Formalism

Omega uses a syntax based on "template English." Instead of abstract symbols, it uses instance descriptions like (a Son). The core of the system is the inheritance relation, denoted by is. For example, (a Son) is (a Man).

Key methodological choices include:

  • The Complemented Lattice: Omega treats the domain of descriptions as a lattice. It uses Something as the top (universal) and Nothing as the bottom (null). It introduces lattice operators (and, or, not) to merge or differentiate categories.
  • Monotonicity: Knowledge in Omega only accumulates. To model change, the authors use "viewpoints"—different contexts that can coexist without destroying previous information.
  • Axiomatization: The paper provides a formal set of axioms (Extensionality, Commutativity, Deletion, Merging, etc.) that define exactly how descriptions behave.
Example of the Merging axiom in Omega syntax.

As illustrated in the figure above, the Merging axiom allows the system to combine multiple descriptions of the same entity. If a complex number $z$ is described as having a positive real part and separately as having an integer real part, Omega can merge these into a single, more specific description.

Key Insights and Ideas

  • Lattice vs. Logic: One of the most subtle but important insights is the distinction between lattice operators (which combine descriptions) and logical operators (which combine statements). Confusing these two was a common pitfall in earlier AI languages.
  • Implicit Quantification: Omega avoids the "alphabet soup" of universal quantifiers ($\forall x$) by building them into the inheritance structure. Saying ((a Man) is (a Mortal)) is a more natural way of expressing "All men are mortal."
  • Handling Constraints: Omega can represent "constrained attributions." For example, it can describe a human who has only male children, a task that is surprisingly difficult in record-based systems like KRL or FRL.
  • Higher-Order Capabilities: The system can define properties of relations themselves—such as whether a relation is transitive or how to "invert" a relation (e.g., if Paul is the father of John, then John is the son of Paul).

Results and Impact

The authors successfully demonstrated that predicate calculus, type systems, and pattern matching could be unified into a single, cohesive syntax. They showed that Omega could express "$\omega$-order" (higher-order) quantificational calculus, which is significantly more expressive than the First Order Logic typically used in AI at the time.

By providing a succinct specification of the rules of inference, the authors created a "contract" between the people building the system and the people using it, a major step forward in software engineering for AI. While the system was theoretical, a preliminary implementation was developed on the M.I.T. CADR System (a famous early Lisp machine) for an office workstation prototype.

Limitations and Future Work

The authors acknowledge that while the system is expressive, they hadn't yet proven its consistency. Because Omega is self-referential (it can describe its own rules of inference), it risks falling into logical traps like Russell’s Paradox. Future work aimed to develop formal operational and denotational semantics to prove the system's consistency and further explore "viewpoints" for handling contradictory information.

Summary updated

BibTeX
@inproceedings{hewitt1980knowledge,
  author = {Carl Hewitt and Giuseppe Attardi and Maria Simi},
  title = {{Knowledge Embedding in the Description System Omega}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}

Loading related content...

Figure