The Abstract Expressive Power of First-Order and Description Logics with Concrete Domains

Franz BaaderFranz Baader, Filippo De BortoliFilippo De Bortoli

ISBN: 9798400702433
Download
DOI Link

Franz Baader, Filippo De Bortoli
The Abstract Expressive Power of First-Order and Description Logics with Concrete Domains
Proceedings of the 39th ACM/SIGAPP Symposium on Applied Computing, SAC '24, 754-761, April 2024. ACM

Details
Bibtex

KurzfassungAbstract
Concrete domains have been introduced in description logic (DL) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts.
The primary research goal in this context was to find restrictions on the concrete domain such that its integration into certain DLs preserves decidability or tractability. In this paper, we investigate the abstract expressive power of both first-order and description logics extended with concrete domains, i.e., we analyze which classes of first-order interpretations can be expressed using these logics, compared to what first-order logic without concrete domains can express. We demonstrate that, under natural conditions on the concrete domain D (which also play a role for decidability), extensions of first-order logic (FOL) or the well-known DL ALC with D share important formal characteristics with FOL, such as the compactness and the Löwenheim-Skolem properties. Nevertheless, their abstract expressive power need not be contained in that of FOL, though in some cases it is. To be more precise, we show, on the one hand, that unary concrete domains leave the abstract expressive power within FOL if we are allowed to introduce auxiliary predicates. On the other hand, we exhibit a class of concrete domains that push the abstract expressive power beyond that of FOL.
As a by-product of these investigations, we obtain (semi-)decidability results for some of the logics with concrete domains considered in this paper.
Weitere Informationen unter:Further Information: Link
Projekt:Project: ScaDS.AI
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{BaBo-SAC-24,
  author       = {Franz {Baader} and
                  Filippo {De Bortoli}},
  title        = {{The Abstract Expressive Power of First-Order and Description Logics with Concrete Domains}},
  year         = {2024},
  isbn         = {9798400702433},
  publisher    = {{ACM}},
  address      = {New York, NY, USA},
  url          = {https://doi.org/10.1145/3605098.3635984},
  doi          = {10.1145/3605098.3635984},
  booktitle    = {Proceedings of the 39th {ACM/SIGAPP} Symposium on Applied Computing},
  pages        = {754--761},
  numpages     = {8},
  location     = {\'Avila, Spain},
  series       = {SAC '24},
}

This work is licensed under a Creative Commons Attribution International 4.0 License.