• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Modal Definability of First-Order Formulas with Free Variables and Query Answering

Journal of Applied Logic. 2013. Vol. 11. No. 2. P. 190-216.
Kikot S., Zolin E.

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 $\forall\exists$-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.