On Finite and Unrestricted Query Entailment Beyond SQ with Number Restrictions on Transitive Roles

Tomasz Gogacz, Víctor Gutiérrez-Basulto, Yazmín Ibáñez-García, Jean Christoph Jung, Filip Murlak

IJCAI 2019 pp. 1719-1725

doi:10.24963/IJCAI.2019/238 /ijcai/2019/gogacz2019ijcai-finite/

Abstract

We study the description logic SQ with number restrictions applicable to transitive roles, extended with either nominals or inverse roles. We show tight 2EXPTIME upper bounds for unrestricted entailment of regular path queries for both extensions and finite entailment of positive existential queries for nominals. For inverses, we establish 2EXPTIME-completeness for unrestricted and finite entailment of instance queries (the latter under restriction to a single, transitive role).

PDF IJCAI Semantic Scholar

Cite

Text

Gogacz et al. "On Finite and Unrestricted Query Entailment Beyond SQ with Number Restrictions on Transitive Roles." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/238

Markdown

[Gogacz et al. "On Finite and Unrestricted Query Entailment Beyond SQ with Number Restrictions on Transitive Roles." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/gogacz2019ijcai-finite/) doi:10.24963/IJCAI.2019/238

BibTeX

@inproceedings{gogacz2019ijcai-finite,
  title     = {{On Finite and Unrestricted Query Entailment Beyond SQ with Number Restrictions on Transitive Roles}},
  author    = {Gogacz, Tomasz and Gutiérrez-Basulto, Víctor and Ibáñez-García, Yazmín and Jung, Jean Christoph and Murlak, Filip},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1719-1725},
  doi       = {10.24963/IJCAI.2019/238},
  url       = {https://mlanthology.org/ijcai/2019/gogacz2019ijcai-finite/}
}