The Precise Complexity of Reasoning in ALC with ω-Admissible Concrete Domains

Stefan BorgwardtStefan Borgwardt, Filippo De BortoliFilippo De Bortoli, Patrick KoopmannPatrick Koopmann

ISSN: 1613-0073

Stefan Borgwardt, Filippo De Bortoli, Patrick Koopmann
The Precise Complexity of Reasoning in ALC with ω-Admissible Concrete Domains
In Laura Giordano, Jean Christoph Jung, Ana Ozaki, eds., Proceedings of the 37th International Workshop on Description Logics (DL'24), volume 3739 of CEUR Workshop Proceedings, June 2024

Details
Bibtex

KurzfassungAbstract
Concrete domains have been introduced in the context of Description Logics to allow references to qualitative and quantitative values. In particular, the class of ω-admissible concrete domains, which includes Allen's interval algebra, the region connection calculus (RCC8), and the rational numbers with ordering and equality, has been shown to yield extensions of ALC for which concept satisfiability w.r.t. a general TBox is decidable. In this paper, we present an algorithm based on type elimination and use it to show that deciding the consistency of an ALC(D) ontology is ExpTime-complete if the concrete domain D is ω-admissible and its constraint satisfaction problem is decidable in exponential time. While this allows us to reason with concept and role assertions, we also investigate feature assertions f(a,c) that can specify a constant c as the value of a feature f for an individual a. We show that, under conditions satisfied by all known ω-admissible domains, we can add feature assertions without affecting the complexity.
Bemerkung: Note: An extended version of this paper can be found at: https://arxiv.org/abs/2405.19096
Weitere Informationen unter:Further Information: Link
Projekt:Project: ScaDS.AI
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaBoKo-DL-24,
      address = {Bergen, Norway},
      author = {Stefan {Borgwardt} and Filippo {De Bortoli} and Patrick {Koopmann}},
      booktitle = {Proceedings of the 37th International Workshop on Description Logics (DL'24) },
      editor = {Laura {Giordano} and Jean Christoph {Jung} and Ana {Ozaki}},
      publisher = {CEUR-WS},
      series = {{CEUR} Workshop Proceedings},
      title = {{The Precise Complexity of Reasoning in $\mathcal{ALC}$ with $\omega$-Admissible Concrete Domains}},
      volume = {3739},
      year = {2024},
    }