On limited conjunctions in polynomial feature logics, with applications in obda — Extended abstract

Stephanie McIntyre, Alexander Borgida, David Toman, Grant Weddell

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Standard reasoning problems are complete for EXPTIME in common feature-based description logics—ones in which all roles are restricted to being functional. We show how to control conjunctions on left-hand-sides of subsumptions in such a way so as to ensure polynomial time complexity. In particular, we present a PTIME algorithm for reasoning about knowledge base consistency. We then show how the resulting description logic allows features to be partial, not just total functions. Algorithms for polynomial-time query answering are presented. The above, in combination with referring expressions, provide a richer capability for ontology-based data access to relational data sources.

Original languageEnglish (US)
Title of host publicationPrinciples of Knowledge Representation and Reasoning
Subtitle of host publicationProceedings of the 16th International Conference, KR 2018
EditorsMichael Thielscher, Francesca Toni, Frank Wolter
PublisherAAAI press
Pages655-656
Number of pages2
ISBN (Electronic)9781577358039
StatePublished - 2018
Externally publishedYes
Event16th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2018 - Tempe, United States
Duration: Oct 30 2018Nov 2 2018

Publication series

NamePrinciples of Knowledge Representation and Reasoning: Proceedings of the 16th International Conference, KR 2018

Conference

Conference16th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2018
CountryUnited States
CityTempe
Period10/30/1811/2/18

All Science Journal Classification (ASJC) codes

  • Software
  • Logic

Fingerprint Dive into the research topics of 'On limited conjunctions in polynomial feature logics, with applications in obda — Extended abstract'. Together they form a unique fingerprint.

Cite this