English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In logic-based knowledge representation, query answering has essentiallyreplaced mere satisfiability checking as the inferencing problem of primaryinterest. For knowledge bases in the basic description logic ALC, thecomputational complexity of conjunctive query (CQ) answering is well known tobe ExpTime-complete and hence not harder than satisfiability. This does notchange when the logic is extended by certain features (such as counting or rolehierarchies), whereas adding others (inverses, nominals or transitivitytogether with role-hierarchies) turns CQ answering exponentially harder. Wecontribute to this line of results by showing the surprising fact that evenextending ALC by just the Self operator - which proved innocuous in many othercontexts - increases the complexity of CQ entailment to 2ExpTime. As common forthis type of problem, our proof establishes a reduction from alternating Turingmachines running in exponential space, but several novel ideas and encodingtricks are required to make the approach work in that specific, restrictedsetting.

The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard