June 24: A. Voronkov, Expressive power and data complexity of first-order logic over trees


Subject: June 24: A. Voronkov, Expressive power and data complexity of first-order logic over trees
From: Helmut Veith (kgs-owner@dbai.tuwien.ac.at)
Date: Tue Jun 22 1999 - 15:52:06 MET DST


Lecture Announcement
-------------------------

Andrei Voronkov
=================================================
University of Manchester

Expressive power and data complexity of first-order logic over trees
--------------------------------------------------------------------
Thursday, June 24, 13:15

ABSTRACT:

We characterize the expressive power and data complexity of first-order
logic over trees (or equivalently, nonrecursive Prolog with negation). Our
main result is that the expressive power of first-order logic over trees
is equivalent to the expressive power of first-order logic over finite
structures. Therefore, every query expressible in first-order logic over
trees, is computable in polynomial time.

This contrasts to the huge difference in the complexity of first-order
logic over trees and over finite structures (nonelementary vs
PSPACE-complete).

We also define the notion of a range-restricted query over trees. We
prove that range-restricted first-order queries are precisely those
definable in a relational algebra of trees. Furthermore, we show that a
query is expressible in first-order logic over trees if and only if it
is a Boolean combination of range-restricted queries.

Our results that the use of recursive datastructures (trees) together
with nonrecursive query languages, gives no gain in expressive power.

(joint work with Evgeny Dantsin, Uppsala University and St.Petersburgh
Institute of Mathematics)

PLACE:

Seminarraum SEM 181A, Institut fuer Informationssysteme,
Paniglgasse 16, 1. Stock, 1040 Wien.

------------------------
Kurt-Goedel-Gesellschaft
Technische Universitaet Wien
Institut fuer Computersprachen E185.2
Resselgasse 3/1, A-1040 Wien

email: mailto:kgs@logic.tuwien.ac.at
http://logic.tuwien.ac.at:80/kgs/home.html
listserver: mailto:listproc@dbai.tuwien.ac.at

Mit Unterstuetzung des
Bundesministeriums fuer Wissenschaft und Forschung



This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:21 MET DST