Non-distributive description logic
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909168464560128 |
|---|---|
| author | van der Berg, Ineke De Domenico, Andrea Greco, Giuseppe Manoorkar, Krishna B. Palmigiano, Alessandra Panettiere, Mattia |
| author_facet | van der Berg, Ineke De Domenico, Andrea Greco, Giuseppe Manoorkar, Krishna B. Palmigiano, Alessandra Panettiere, Mattia |
| contents | We define LE-ALC, a generalization of the description logic ALC based on the propositional logic of general (i.e. not necessarily distributive) lattices, and semantically interpreted on relational structures based on formal contexts from Formal Concept Analysis (FCA). The description logic LE-ALC allows us to formally describe databases with objects, features, and formal concepts, represented according to FCA as Galois-stable sets of objects and features. We describe ABoxes and TBoxes in LE-ALC, provide a tableaux algorithm for checking the consistency of LE-ALC knowledge bases with acyclic TBoxes, and show its termination, soundness and completeness. Interestingly, consistency checking for LE-ALC is in PTIME for acyclic and completely unravelled TBoxes, while the analogous problem in the classical ALC setting is PSPACE-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_09561 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Non-distributive description logic van der Berg, Ineke De Domenico, Andrea Greco, Giuseppe Manoorkar, Krishna B. Palmigiano, Alessandra Panettiere, Mattia Logic We define LE-ALC, a generalization of the description logic ALC based on the propositional logic of general (i.e. not necessarily distributive) lattices, and semantically interpreted on relational structures based on formal contexts from Formal Concept Analysis (FCA). The description logic LE-ALC allows us to formally describe databases with objects, features, and formal concepts, represented according to FCA as Galois-stable sets of objects and features. We describe ABoxes and TBoxes in LE-ALC, provide a tableaux algorithm for checking the consistency of LE-ALC knowledge bases with acyclic TBoxes, and show its termination, soundness and completeness. Interestingly, consistency checking for LE-ALC is in PTIME for acyclic and completely unravelled TBoxes, while the analogous problem in the classical ALC setting is PSPACE-complete. |
| title | Non-distributive description logic |
| topic | Logic |
| url | https://arxiv.org/abs/2307.09561 |