Computation of Interpolants for Description Logic Concepts in Hard Cases
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916854019129344 |
|---|---|
| author | Jung, Jean Christoph Kołodziejski, Jędrzej Wolter, Frank |
| author_facet | Jung, Jean Christoph Kołodziejski, Jędrzej Wolter, Frank |
| contents | While the computation of Craig interpolants for description logics (DLs) with the Craig Interpolation Property (CIP) is well understood, very little is known about the computation and size of interpolants for DLs without CIP or if one aims at interpolating concepts in a weaker DL than the DL of the input ontology and concepts. In this paper, we provide the first elementary algorithms computing (i) ALC-interpolants between ALC-concepts under ALCH-ontologies and (ii) ALC-interpolants between ALCQ-concepts under ALCQ-ontologies. The algorithms are based on recent decision procedures for interpolant existence. We also observe that, in contrast, uniform (possibly depth restricted) interpolants might be of non-elementary size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15689 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computation of Interpolants for Description Logic Concepts in Hard Cases Jung, Jean Christoph Kołodziejski, Jędrzej Wolter, Frank Logic in Computer Science While the computation of Craig interpolants for description logics (DLs) with the Craig Interpolation Property (CIP) is well understood, very little is known about the computation and size of interpolants for DLs without CIP or if one aims at interpolating concepts in a weaker DL than the DL of the input ontology and concepts. In this paper, we provide the first elementary algorithms computing (i) ALC-interpolants between ALC-concepts under ALCH-ontologies and (ii) ALC-interpolants between ALCQ-concepts under ALCQ-ontologies. The algorithms are based on recent decision procedures for interpolant existence. We also observe that, in contrast, uniform (possibly depth restricted) interpolants might be of non-elementary size. |
| title | Computation of Interpolants for Description Logic Concepts in Hard Cases |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2507.15689 |