Source-linked AI summary
Syntactic Simplification of OWL Class Expressions
Alkid Baci, N'Dah Jean Kouagou, Caglar Demir, Axel-Cyrille Ngonga Ngomo
TL;DR
Complex OWL class expressions hinder readability and reasoning efficiency, so CES applies semantics-preserving syntactic rewrites to simplify them. On 200 expressions from two medium-sized datasets, it achieved up to 86% length and 90% runtime reductions.
Problem
Verbose or redundant OWL class expressions reduce ontology readability and can increase the computational burden of description-logic reasoning.
Method
CES recursively applies terminating, semantics-preserving syntactic rewriting rules to simplify OWL class expressions.
Results
86% maximum length reduction and 90% maximum runtime reduction were recorded on 200 class expressions from two medium-sized datasets.
Takeaways & Limitations
CES can serve as a post-processing step that reduces verbosity and improves reasoning efficiency in ontology-based systems.
Takeaways & Limitations
Because all tested hypotheses were generated by TDL, the reported reduction rates may not represent expressions produced by other concept-learning systems.
Abstract
from arXiv · showhide
Class expression learning often produces complex OWL class expressions that are difficult to interpret and reason over. However, by following theoretically grounded simplification principles, this complexity can be reduced. In this paper, we propose Class Expression Simplifier (CES), a novel algorithm for the syntactic simplification of class expressions in Description Logics (DL). CES aims to preserve formal semantics while reducing representational complexity. It systematically applies rewriting rules to eliminate redundancies and identify simpler yet equivalent expressions, thereby producing more compact and human-readable representations without altering logical entailments. We evaluate the effectiveness of CES on class expressions learned from two medium-sized ontologies, demonstrating measurable improvements in reasoning efficiency and reductions in verbosity. This work contributes to the broader goal of making ontology-driven applications more accessible, maintainable, and scalable, with direct implications for knowledge graph construction, semantic search, and Web-scale reasoning. CES is implemented within the open-source Python framework OWLAPY and is publicly available.
1 Introduction
Complex OWL class expressions hinder readability and reasoning efficiency, motivating syntactic simplification that preserves semantics. The paper introduces CES, a terminating rewriting algorithm with DL-based rules and evaluates it on 200 expressions from two medium-sized datasets.
- OWL class expressions combine logical operators and role restrictions to specify rich, precise concepts for Semantic Web applications.
- Verbose or redundant expressions reduce ontology readability and can increase reasoning-task size, harming description-logic reasoner performance.These inefficiencies can become prohibitive when ontologies are combined with massive knowledge graphs.
- Systematic syntactic simplification methods for OWL class expressions remain largely underexplored compared with semantic reasoning, optimization, and modularization.FaCT++ offers a limited comparison through simplified normal-form transformations.
- CES defines DL-based rewriting rules and recursively simplifies SOIQ(D) concepts with transitive roles while excluding other RBox axioms.The recursive approach guarantees termination and adheres strictly to syntactic simplification.
- 200 class expressions from two medium-sized datasets are used to evaluate CES’s reductions in expression length and reasoning runtime.
2 Background
Description Logics provide OWL’s formal foundation, representing complex class expressions with Boolean connectives, quantifiers, and role restrictions. CES simplification is guided by redundancy elimination and equivalence preservation, using terminating, semantically sound rewriting rules.
- DL foundations: Description Logics define OWL concepts with conjunction, disjunction, negation, existential restrictions, and universal restrictions over roles.Expressions are interpreted over a domain through an interpretation function mapping concepts and roles to subsets of that domain.
- Simplification principles: Redundancy elimination removes duplicate subexpressions and orders or flattens conjuncts and disjuncts.Equivalence preservation applies algebraic rules to obtain shorter expressions with identical semantics.
- Simplification principles: The rewriting algorithm is designed for termination and semantic soundness and processes expressions according to the unique name assumption.These principles guide the rules used under equivalence preservation.
- Equivalence-preserving rules: Absorption and idempotence eliminate redundant disjunctive or conjunctive structures, including C ⊔(C ⊓D) ≡C and C ⊓C ≡C.The corresponding laws also include C ⊓(C ⊔D) ≡C and C ⊔C ≡C.
- Equivalence-preserving rules: Identity and domination simplify interactions with ⊤ and ⊥: C ⊓⊤≡C, C ⊔⊥≡C, C ⊔⊤≡⊤, and C ⊓⊥≡⊥.Excluded-middle and non-contradiction rules additionally yield C ⊔¬C ≡⊤ and C ⊓¬C ≡⊥.
- Structural rewriting: Additional rules combine restrictions over the same role, subsume redundant cardinality bounds, factor common subexpressions, and factor negations.The rules also extend to upper-bound and datatype restrictions, while quantifier distribution merges filler expressions.
3 Methodology
CES defines simplification as a semantics-preserving reduction in class-expression length and recursively applies contextual rewriting rules in a single pass. For n-ary expressions, it combines operand- and connective-level simplification with recursive factorization to produce structurally compact expressions.
- Simplification objective: Simplification transforms a class expression into a syntactically shorter, semantically equivalent expression under every interpretation.The transformation reduces the OWL constructs needed to represent the expression while preserving its interpretation.
- Recursive simplification: The recursive simplify(c, p) function applies as many relevant rules as possible in one pass, using the parent expression for contextual rules.The parent parameter supports rules requiring knowledge of the surrounding n-ary expression.
- N-ary expression rules: N-ary simplification flattens nested expressions, removes duplicates, applies logical laws, checks cardinality subsumption, and factorizes the result.The procedure handles idempotence, absorption, domination or identity, excluded middle, and operand-level recursion.
- Factorization: Factorization operates at recursive union or intersection roots to reduce structural length after local rewriting has simplified all operands.It is especially important when intermediate expressions remain verbose despite local rule applications.
- Factorization: Recursive factorization converts the initial expression to top-level DNF, identifies common or redundant subexpressions, and repeats until no further factorization is possible.The final expression is structurally compact while preserving the original expression’s semantics.
4 Evaluation
CES was evaluated on 200 learned class expressions from two medium-sized ontologies, measuring construct-based length and instance-retrieval runtime. It achieved substantial reductions in both verbosity and reasoning cost, with low simplification overhead.
- Evaluation setup: The evaluation generated 200 class expressions from random learning problems over the Carcinogenesis and Mutagenesis datasets in SML-bench.Expressions were produced with the Tree-based OWL Class Expression Learner (TDL).
- Evaluation metrics: Length was measured by OWL construct units, while reasoning efficiency was measured using StructuralReasoner instance-retrieval runtime.StructuralReasoner is the native reasoner of OWLAPY.
- Results: 86% was the highest recorded length reduction relative to the original expression.Length comparisons were reported in construct units for original and CES-simplified expressions.
- Results: 90% was the highest recorded runtime reduction relative to the original expression.Runtime comparisons measured instance retrieval in seconds before and after simplification.
- Simplification overhead: Average simplification runtime was 0.11s on Mutagenesis and 0.16s on Carcinogenesis.The longest expression, with length 4284, took 1.34 seconds to simplify.
5 Discussion and Conclusion
CES is presented as a semantics-preserving syntactic simplification algorithm that reduces OWL class-expression verbosity and improves reasoning efficiency. The discussion highlights its integration potential while noting limitations from TDL-only evaluation and single-pass process ordering.
- Contributions: CES reduces OWL class-expression verbosity and improves reasoning efficiency through purely syntactic, semantics-preserving simplification.The method can be integrated into class-expression learning systems as a default post-processing step before presenting the final hypothesis.
- Limitations: CES’s reported reduction rates may not generalize beyond hypotheses generated by TDL, especially for systems producing shorter or structurally different expressions.The evaluation used hypotheses generated exclusively by TDL.
- Limitations: Single-pass simplification makes the ordering of processes such as factorization and cardinality-restriction merging a limitation.The passage identifies process ordering as affecting CES’s simplification behavior.
- Implications: CES offers a practical step toward more interpretable and maintainable ontology-based systems while remaining broadly applicable without requiring a reasoner or background ontology.Its syntactic-only design avoids dependence on a reasoner.