Number Restrictions on Transitive Roles in Description Logics with Nominals

Víctor Gutiérrez-Basulto, Yazmín Angélica Ibáñez-García, Jean Christoph Jung

AAAI 2017 pp. 1121-1127

doi:10.1609/AAAI.V31I1.10678 /aaai/2017/gutierrezbasulto2017aaai-number/

Abstract

We study description logics (DLs) supporting number restrictions on transitive roles. We first take a look at SOQ and SON with binary and unary coding of numbers, and provide algorithms for the satisfiability problem and tight complexity bounds ranging from EXPTIME to NEXPTIME. We then show that by allowing for counting only up to one (functionality), inverse roles and role inclusions can be added without losing decidability. We finally investigate DLs of the DL-Lite-family, and show that, in the presence of role inclusions, the core fragment becomes undecidable.

PDF AAAI Semantic Scholar

Cite

Text

Gutiérrez-Basulto et al. "Number Restrictions on Transitive Roles in Description Logics with Nominals." AAAI Conference on Artificial Intelligence, 2017. doi:10.1609/AAAI.V31I1.10678

Markdown

[Gutiérrez-Basulto et al. "Number Restrictions on Transitive Roles in Description Logics with Nominals." AAAI Conference on Artificial Intelligence, 2017.](https://mlanthology.org/aaai/2017/gutierrezbasulto2017aaai-number/) doi:10.1609/AAAI.V31I1.10678

BibTeX

@inproceedings{gutierrezbasulto2017aaai-number,
  title     = {{Number Restrictions on Transitive Roles in Description Logics with Nominals}},
  author    = {Gutiérrez-Basulto, Víctor and Ibáñez-García, Yazmín Angélica and Jung, Jean Christoph},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2017},
  pages     = {1121-1127},
  doi       = {10.1609/AAAI.V31I1.10678},
  url       = {https://mlanthology.org/aaai/2017/gutierrezbasulto2017aaai-number/}
}