mlsanityData to 14 Oct 2026

Finite Entailment of UCRPQs over ALC Ontologies

arXiv 2204.14261 ↗First posted 29 Apr 2022cs.LO cs.AI cs.DBcited by 0

Not on the map. Why?

Abstract (arXiv)

We investigate the problem of finite entailment of ontology-mediated queries. We consider the expressive query language, unions of conjunctive regular path queries (UCRPQs), extending the well-known class of union of conjunctive queries, with regular expressions over roles. We look at ontologies formulated using the description logic ALC, and show a tight 2EXPTIME upper bound for entailment of UCRPQs. At the core of our decision procedure, there is a novel automata-based technique introducing a stratification of interpretations induced by the deterministic finite automaton underlying the input UCRPQ

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 8 of its 51 references that are in the map. First posted on arXiv 29 Apr 2022.

Builds on

8 of 51 references.

References · 8

  1. 2013Querying the Guarded Fragmentcited by 6
  2. 2014Nested Regular Path Queries in Description Logicscited by 4
  3. 2018Finite Query Answering in Expressive Description Logics with Transitive Rolescited by 4
  4. 2018Finite Satisfiability of Unary Negation Fragment with Transitivitycited by 3
  5. 2015Finite Open-World Query Answering with Number Restrictions (Extended Version)cited by 1
  6. 2020On Finite Entailment of Non-Local Queries in Description Logicscited by 1
  7. 2020On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Rolescited by 1
  8. 2020Answering Regular Path Queries Over SQ Ontologiescited by 1

Built on by

Not cited yet.