Reasoning in the Description Logic ALC under Category Semantics

We present in this paper a reformulation of the usual set-theoretical semantics of the description logic \(\mathcal{ALC}\) with general TBoxes by using categorical language. In this setting, \(\mathcal{ALC}\) concepts are represented as objects, concept subsumptions as arrows, and memberships as log...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-05
Main Authors: Brieulle, Ludovic, Chan Le Duc, Vaillant, Pascal
Format: Article
Language:English
Subjects:
Algorithms
Polynomials
Semantics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present in this paper a reformulation of the usual set-theoretical semantics of the description logic \(\mathcal{ALC}\) with general TBoxes by using categorical language. In this setting, \(\mathcal{ALC}\) concepts are represented as objects, concept subsumptions as arrows, and memberships as logical quantifiers over objects and arrows of categories. Such a category-based semantics provides a more modular representation of the semantics of \(\mathcal{ALC}\). This feature allows us to define a sublogic of \(\mathcal{ALC}\) by dropping the interaction between existential and universal restrictions, which would be responsible for an exponential complexity in space. Such a sublogic is undefinable in the usual set-theoretical semantics, We show that this sublogic is {\sc{PSPACE}} by proposing a deterministic algorithm for checking concept satisfiability which runs in polynomial space.
ISSN:2331-8422