Answering Regular Path Queries Over SQ Ontologies
This work provides an optimal algorithm for answering a specific type of query in a particular description logic, which is an incremental improvement for researchers working with knowledge representation and reasoning.
This paper addresses query answering in the description logic SQ, which supports qualified number restrictions on both transitive and non-transitive roles. The authors developed an optimal automata-based algorithm that answers positive existential regular path queries in 2ExpTime.
We study query answering in the description logic $\mathcal{SQ}$ supporting qualified number restrictions on both transitive and non-transitive roles. Our main contributions are a tree-like model property for $\mathcal{SQ}$ knowledge bases and, building upon this, an optimal automata-based algorithm for answering positive existential regular path queries in 2ExpTime.