| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4663044 | Journal of Applied Logic | 2013 | 27 Pages |
Abstract
We present an algorithmically efficient criterion of modal definability for first-order existential conjunctive formulas with several free variables. Then we apply it to establish modal definability of some family of first-order ∀∃-formulas. Finally, we use our definability results to show that, in any expressive description logic, the problem of answering modally definable conjunctive queries is polynomially reducible to the problem of knowledge base consistency.
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
Stanislav Kikot, Evgeny Zolin,