On Limited Conjunctions and Partial Features in Parameter-Tractable Feature Logics - McIntyre, Stephanie; Borgida, Alexander; Toman, David; Weddell, Grant (Proceedings of the AAAI Conference on Artificial Intelligence, 2019)
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.