Abstract
In the field of knowledge representation, a fundamental tension exists between the expressiveness of a language and the computational efficiency of its reasoning processes. This paper explores this "fundamental tradeoff" by analyzing frame-based description languages. We demonstrate that even minor additions to a language's expressive power can lead to a "computational cliff," shifting the complexity of determining subsumption from polynomial time to co-NP-completeness. This work establishes the theoretical foundation for what would later become the field of Description Logics.
Introduction
During the 1980s, frame-based systems became a dominant paradigm for representing structured knowledge in artificial intelligence. These systems allowed researchers to define concepts (frames) and their properties (slots). A critical service provided by these systems is subsumption: the ability to automatically determine if one concept is a specialization of another based solely on their formal definitions. For instance, a system should be able to infer that the category "Person whose children are all Doctors" is subsumed by the category "Person whose children are all Medical Professionals."
Historically, the features of these languages were often chosen based on intuitive utility rather than formal rigor. This paper addresses the lack of computational analysis regarding these features, proving that the cost of reasoning is perilously sensitive to the specific logical operators permitted within the language.
Formalizing the Language: $\mathcal{FL}^-$ and $\mathcal{FL}$
To analyze the complexity of subsumption, we define a distilled frame language, $\mathcal{FL}$. We compare two specific variants to pinpoint the source of computational intractability:
- $\mathcal{FL}^-$ (The Restricted Language): This version includes basic operators essential for description:
- Conjunction (AND): Combining multiple descriptions (e.g.,
(AND Person Male)). - Value Restriction (ALL): Restricting the range of a role (e.g.,
(ALL Child Doctor)). - Existential Restriction (SOME): Requiring at least one filler for a role (e.g.,
(SOME Child)). - $\mathcal{FL}$ (The Full Language): This version adds a single additional operator:
- Role Restriction (RESTR): Allowing the narrowing of a relationship based on a concept (e.g.,
(RESTR Child Male), which effectively defines the concept of a "son").
By establishing a formal extensional semantics—mapping these concepts to sets of individuals in a domain—we can define subsumption as a subset relationship: Concept A subsumes Concept B if and only if the set of individuals denoted by B is always a subset of the set denoted by A.
The Computational Cliff
The core finding of this research is the discovery of a "computational cliff." While the difference between $\mathcal{FL}^-$ and $\mathcal{FL}$ appears minor to a human designer, the impact on reasoning performance is profound.
Tractability of $\mathcal{FL}^-$
For the restricted language $\mathcal{FL}^-$, we provide an algorithm that operates by flattening concept descriptions into a normalized form and performing a structural comparison. We prove that this algorithm correctly determines subsumption in $O(n^2)$ time, where $n$ is the length of the descriptions. This confirms that basic frame-based reasoning is computationally efficient.
Intractability of $\mathcal{FL}$
By introducing the RESTR operator, the complexity of the problem changes fundamentally. We demonstrate this by providing a reduction from propositional logic in conjunctive normal form to $\mathcal{FL}$ descriptions. This reduction proves that determining subsumption in the full language is co-NP-complete. In practical terms, this means that as the complexity of the knowledge base grows, the time required to check even simple subsumption relationships may grow exponentially in the worst case.
The Fundamental Tradeoff in Knowledge Representation
This research highlights a crucial principle in AI: the Fundamental Tradeoff. There is an inherent conflict between the expressive power of a representation language and the tractability of its inference procedures.
Our results suggest that human intuition is often a poor guide for language design. To a developer, adding the ability to say "children who are male" feels like a natural and modest extension. However, this paper proves that such extensions can lead directly over a "computational precipice." Furthermore, we observed that intractability is not caused by complexity in general, but by specific combinations of logical features; adding other operators like AT-LEAST or ROLE-CHAIN to $\mathcal{FL}^-$ does not necessarily trigger the same jump in complexity.
Conclusion and Legacy
While this study focused on a specific set of operators, its implications are broad. It moved the field of knowledge representation away from ad-hoc implementations and toward a formal, semantics-based approach. This work laid the groundwork for Description Logics (DL), providing the theoretical framework used to design modern systems like the Web Ontology Language (OWL) used in the Semantic Web.
Future work in this area continues to map the boundaries of tractability, seeking the "sweet spot" of expressiveness that allows for powerful knowledge representation without sacrificing the guarantee of efficient reasoning.
Summary updated