Research map / Learning theory and algorithms / Combinatorial and search optimization
Minimal Macro-Based Rewritings of Formal Languages: Theory and Applications in Ontology Engineering (and Beyond)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces size-minimal rewriting of finite formal languages with nested syntactic macros, gives polynomial-time algorithms for three problem variants, and applies them to five biomedical OWL ontologies.
Problem
Rewriting finite formal languages (e.g., OWL ontologies) using nested syntactic macros so that the encoding is minimal in size, which is needed to reduce repetition while preserving syntactic structure.
Approach
Formalises macro systems over mixed ranked/unranked/ordered/unordered term trees, defines macro dependency as subterm containment, and shows that a size-minimal macrofication is unique and polynomial-time computable for given reduced macro definitions; for unrestricted macros without unary symbols, selects macros for non-dominated repeated subterms.
Key results
- Size-minimal encodings for Problem 3 reduce ontology size by 37% on SNOMED, 15% on Galen, 35% on Genomic CDS, 28% on FYPO and 17% on NCIT.
- All size-minimal encodings for the five ontologies are computed in less than a minute on an Apple M2 Max, versus 3-10 minutes per 100 concepts reported for a prior approach on SNOMED.
- Problem 3 reduces a higher share of class expressions than the prior approach in 13 of 15 comparisons, though average size reduction is mixed (prior approach higher in 7 of 15 cases).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use new macro definitions selected from repeated subterms instead of only the ontology's existing definitions | Ontology macro rewriting · SNOMED | proportional size reduction: 3% -> 37% | Helped |
| Use new macro definitions selected from repeated subterms instead of only the ontology's existing definitions | Ontology macro rewriting · Galen | proportional size reduction: 2%; 3% -> 15% | Helped |
| Use new macro definitions selected from repeated subterms instead of only the ontology's existing definitions | Ontology macro rewriting · Genomic CDS | proportional size reduction: 2%; 3% -> 35% | Helped |
| Use new macro definitions selected from repeated subterms instead of only the ontology's existing definitions | Ontology macro rewriting · FYPO | proportional size reduction: 21% -> 28% | Helped |
| Use new macro definitions selected from repeated subterms instead of only the ontology's existing definitions | Ontology macro rewriting · NCIT | proportional size reduction: 0% -> 17% | Helped |
| Compute size-minimal rewritings with the proposed algorithms | All three ontology rewriting problems · Five biomedical ontologies | processing time: less than a minute | Helped |
Surprising findings
- Greedily instantiating minimal or maximal macros in the containment Hasse diagram does not necessarily yield a minimal encoding when unary symbols are present.
- Problems 1 and 2 with existing EquivalentClasses definitions give only 0-3% reduction, far below the reductions from introducing new macros (Problem 3).
Limitations
- Complexity of the general Problem 3 for alphabets with unary symbols remains open; the simple selection criterion fails with unary symbols.
- Evaluation restricted to class expression axioms and to ontology macros without nesting features beyond the stated setup; SNOMED is not publicly downloadable.
Experimental setup
Datasets: SNOMED CT Galen Genomic CDS FYPO NCIT
Benchmarks: SNOMED CT Galen Genomic CDS FYPO NCIT
Metrics: proportional size reduction number of changed axioms percentage of class expressions reduced average size reduction per expression processing time
Baselines: Existing entailment-based OWL class expression minimisation (NK results reported
Builds on: term tree isomorphism finite ground term rewriting systems
Closest papers by meaning
- Small Is Beautiful: Computing Minimal Equivalent EL Concepts (AAAI 2017 · similarity 0.88)
- Repairing Ontologies via Axiom Weakening (AAAI 2018 · similarity 0.87)
- Efficient Extraction of EL-Ontology Deductive Modules (AAAI 2023 · similarity 0.86)
- First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics (AAAI 2022 · similarity 0.86)
- Characterizing the Program Expressive Power of Existential Rule Languages (AAAI 2022 · similarity 0.86)
- Efficient Axiomatization of OWL 2 EL Ontologies from Data by Means of Formal Concept Analysis (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.