On Limited Conjunctions and Partial Features in Parameter-Tractable Feature Logics

  • Stephanie McIntyre University of Waterloo
  • Alexander Borgida Rutgers University
  • David Toman University of Waterloo
  • Grant Weddell University of Waterloo


Standard reasoning problems are complete for EXPTIME in common feature-based description logics—ones in which all roles are restricted to being functions. We show how to control conjunctions on left-hand-sides of subsumptions and use this restriction to develop a parameter-tractable algorithm for reasoning about knowledge base consistency. We then show how the resulting logic can simulate partial features, and present algorithms for efficient query answering in that setting.

AAAI Technical Track: Knowledge Representation and Reasoning