

Seminar of the Department of Mathematical Logic "Algorithmic problems in algebra and logic"
March 27, 2012 18:30, Moscow, MSU, auditorium 1604






Modal definability of firstorder formulas and its application to knowledge bases
E. E. Zolin^{} 
Number of views: 
This page:  71 

Abstract:
The talk is about an application of results from
a branch of modal logic known as Modal Definability Theory
to the problem of query answering in firstorder theories.
Modal definability of a firstorder formula $q(x)$ means the existence of a modal formula
that is valid at a world of a Kripke frame iff $q(x)$ is true at this world.
In firstorder logic, the following problem makes sense:
given a firstorder theory $T$ and a formula $q(x)$, called a query to $T$
in this context, find all constants $c$ (called answers to the query)
for which $T$ entails $q(c)$. It was recently discovered that the two
notions are closely related, and results from modal definability
can be used for query answering in firstorder theories and,
in particular, in knowledge bases. The framework can be
generalized also to queries with several free variables.
We shall also describe a family of conjunctive queries
that can be efficiently answered without rise of complexity
(on the contrary, the general query answering problem
is exponentially harder).
This is a joint work with Stanislav Kikot.

