A Scheme for Integrating Concrete Domains into Concept Languages

TL;DR

This paper introduces a novel scheme for extending KL-ONE-style concept languages to seamlessly incorporate concrete domains like integers or real numbers. This allows for richer, more natural knowledge representation by directly referencing domain-specific predicates, leading to sound and complete reasoning algorithms.

What Problem Does This Paper Address?

Traditional KL-ONE-based concept languages excel at representing abstract, taxonomic knowledge. However, they struggle when needing to express knowledge that inherently relies on concrete domains, such as numerical constraints or geometric relationships. For instance, defining a "woman" as "human and female" is straightforward, but adding a condition like "at least 21 years old" becomes cumbersome. Current approaches often resort to complex encodings or lack formal guarantees. This paper aims to bridge this gap by providing a principled way to integrate concrete domains, making knowledge representation more expressive and reasoning more efficient.

Methods

The authors propose a scheme for extending the ALC concept language (a representative KL-ONE language) with an arbitrary "admissible" concrete domain D. An admissible domain satisfies two key properties: its predicate names are closed under negation and include a name for the domain itself, and the satisfiability problem for finite conjunctions of its predicates is decidable.

The core of their approach lies in defining a new syntax for concept terms that allows predicate restrictions of the form P(u1, ..., un), where P is a predicate from the concrete domain and u1, ..., un are "feature chains" (sequences of functional roles). This allows direct referencing of concrete domain properties.

For reasoning, they define a unified model-theoretic semantics for the extended language. Crucially, they show that inference problems like subsumption, instantiation, and consistency in the extended language can be reduced to subtasks that are solved by a special-purpose reasoner for the concrete domain. This allows for the development of sound and complete algorithms for the extended system, leveraging existing reasoners for concrete domains.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Direct Integration is Key: Instead of contorting abstract representations, directly incorporating concrete domain predicates makes knowledge representation more intuitive and natural.
  • Admissibility is Crucial: The formal properties of a concrete domain (closure under negation, decidable satisfiability) are essential for enabling sound and complete reasoning in the extended concept language.
  • Feature Chains as Bridges: Feature chains act as a powerful mechanism to connect abstract individuals to concrete domain predicates, allowing for complex relationships to be expressed.
  • Sound and Complete Reasoning: By reducing inference problems to subtasks solvable by specialized concrete domain reasoners, the authors achieve sound and complete algorithms for the extended concept language, a significant improvement over many existing systems.
  • Unified Semantics: A single, consistent model-theoretic semantics underpins both the abstract and concrete aspects of the knowledge representation, simplifying the theoretical framework.

Key Results

The paper presents a formal scheme for extending concept languages with admissible concrete domains. They define the syntax and semantics of this extended language, called ACC(D). The main result is the development of a framework that allows for sound and complete algorithms to decide key inference problems:

  • Subsumption: Determining if one concept is a subconcept of another.
  • Instantiation: Determining if an abstract object is an instance of a concept.
  • Consistency: Determining if a set of assertions (an A-box) is consistent with a T-box (terminological knowledge).

These algorithms are achieved by reducing the problems to satisfiability checks within the concrete domain, leveraging the domain's specific reasoning capabilities.

Limitations and Future Work

The authors acknowledge that their complete reasoning algorithm has a complexity of at least PSPACE, which can be high. However, they note that this is a worst-case complexity and that the algorithm may perform much better on typical knowledge bases.

Future work could involve experimenting with more complex concrete domains and exploring optimizations for the reasoning algorithms. The paper also mentions that their approach differs from other extensions by providing a general scheme rather than a specific instance, and by achieving completeness. They are currently experimenting with a prototypical implementation using a fragment of real arithmetic for geometric descriptions.

Summary updated

BibTeX
@inproceedings{1991scheme,
  title = {{A Scheme for Integrating Concrete Domains into Concept Languages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure