Finite Representability Barriers in Description Logics

19 concepts10 papers1 proposal

When managing large-scale knowledge bases, we frequently need to modify their vocabulary. We might want to forget a sensitive concept to preserve privacy, create a simplified view for a specific task via uniform interpolation, or contract the knowledge base by removing an outdated axiom.

Intuitively, these operations sound like simple subtraction: if you remove a piece of data or a term, the remaining knowledge base should just get smaller. However, in expressive Description Logics (DLs) and rule languages, this intuition breaks down completely. Modifying a finite knowledge base can suddenly require an infinite number of axioms to preserve the remaining logical consequences. This phenomenon is known as the finite representability problem.

The Intuition: Why Shrinking Creates Infinities

To understand why removing information can require infinite axioms, consider how description logics express relationships. Suppose an ontology contains a chain of implications involving a "middle-man" concept, $B$:

$$A \sqsubseteq \exists R.B$$ $$B \sqsubseteq \exists R.B$$

This finite set of rules implies an infinite sequence of logical consequences about the role $R$: $A$ must have an $R$-successor, which has an $R$-successor, which has another $R$-successor, and so on, infinitely. The concept $B$ acts as a finite generator for this infinite chain.

Now, imagine we want to forget the concept $B$ while preserving every logical consequence that can be stated using only $A$ and $R$. Without the helper concept $B$ to loop back on, how do we express that $A$ initiates an infinite chain of $R$-successors?

In standard description logics, we cannot. We can write an axiom stating that $A$ has one successor ($\exists R.\top$), or two ($\exists R.\exists R.\top$), or three. But to capture the entire deductive closure of the original ontology without $B$, we would have to write an infinite conjunction of these increasingly deep existential restrictions. The finite syntax of our original logic is simply not expressive enough to encapsulate the remaining knowledge.

Forgetting and Uniform Interpolation

This expressivity gap is a fundamental barrier to modularizing and cleaning up ontologies. As shown by Boris Konev et al. in Forgetting and Uniform Interpolation in Large-Scale Description Logic Terminologies, eliminating specific vocabulary while preserving all logical consequences frequently yields a target theory that cannot be expressed within the original logic's syntax.

This lack of closure under uniform interpolation is not a minor edge case; it is a systemic property of expressive logics. Carsten Lutz et al. proved in Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics that for the standard expressive logic $\mathcal{ALC}$, deciding whether a finite uniform interpolant even exists is 2-EXPTIME-complete. When it does exist, the resulting ontology can be triple-exponentially larger than the original. To maintain semantic completeness without an exponential explosion, the authors demonstrate that one must shift to more powerful formalisms, such as fixpoint logics ($\mu$-calculus), which natively support the recursion required to capture infinite chains.

The barrier extends beyond description logics to database theory and existential rules. As Zhe Wang et al. demonstrated in Forgetting and Unfolding for Existential Rules, removing even a single predicate from an existential rule workflow can require an infinite set of rules to preserve logical equivalence, rendering the exact result undecidable in standard finite frameworks.

The Failure of Formula-Based Contraction

A closely related problem occurs in belief revision when we want to contract an ontology—explicitly retracting a specific axiom or consequence.

In simple propositional logic, contraction is straightforward: you look at the deductive closure, remove the unwanted formula, and select a maximal subset of remaining formulas. However, Bernardo Cuenca Grau et al. showed in Ontology Contraction: Beyond the Propositional Paradise that this strategy fails in description logics. Because the deductive closure of a description logic ontology is typically infinite, formula-based contraction methods cannot guarantee a finite or representable result.

As the authors elaborate in How to Contract Ontologies, many computationally efficient description logics are fundamentally not closed under contraction. The logically ideal result of removing information simply cannot be expressed using the input language's syntax, forcing a harsh trade-off between maintaining language constraints and achieving precise logical retraction.

What Makes Logics Behave Badly?

The risk of losing finite representability depends heavily on the specific constructors allowed in the logic:

Practical Workarounds: Approximations and Hybrids

Because a perfect, finite result often does not exist mathematically, researchers have developed alternative paradigms to make ontology modification practical:

  1. Finite Approximations: Instead of aiming for an exact but impossible infinite consequence set, Kewen Wang et al. in Concept and Role Forgetting in ALC Ontologies proposed using a sequence of finite approximations. This allows reasoning tools to operate on a usable, bounded version of the modified knowledge base that gets progressively closer to the ideal semantic result.
  2. Structural and Hybrid Frameworks: To handle contraction without getting lost in infinite deductive closures, Bernardo Cuenca Grau et al. proposed hybrid semantic frameworks that preserve both the human-readable syntactic structure of the ontology and its intended logical behavior, bypassing purely logic-based subset selection.
  3. Graph-Based Pruning: In simpler profiles like DL-Lite, the boundaries are cleaner. Kewen Wang et al. demonstrated in Incosistency-Tolerant Forgetting in DL-lite that graph-based databases and algorithms can efficiently prune messy or inconsistent data while maintaining robust reasoning capabilities, avoiding the expressivity traps of more complex description logics.

Key Foundational Work

Concept and Role Forgetting in ALC{\mathcal {ALC}} Ontologies (2009) — contributed 2 concept elements to this direction.
Forgetting and Uniform Interpolation in Large-Scale Description Logic Terminologies (2009) — contributed 1 concept elements to this direction.
A Forgetting-based Approach for Reasoning with Inconsistent Distributed Ontologies (2008) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 10 papers
  2. Version 1 · 2026-10-04 · 11 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_finite_representability_7d680696,
  title = {finite representability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-representability/rdr_7d680696446a4ab693a3b351c25e6e5f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_finite_representability_7d680696_v2,
  title = {finite representability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-representability/rdr_7d680696446a4ab693a3b351c25e6e5f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake