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

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.

Authors

• Stephanie McIntyre
• Alexander Borgida
• David Toman
• Grant Weddell

Keywords

No keywords are indexed for this paper.