**Subject: **Lecture Today: T. Schwentick, Characterizing Linear Time

**From: **Helmut Veith (*kgs-owner@dbai.tuwien.ac.at*)

**Date: **Mon Oct 18 1999 - 11:04:22 MET DST

**sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Helmut Veith : "October 25: J. Wiedermann"**Previous message:**Helmut Veith : "June 24: A. Voronkov, Expressive power and data complexity of first-order logic over trees"

Lecture Announcement

-------------------------

Thomas Schwentick

=================================================

Johannes Gutenberg-Universitaet Mainz

Characterizing Linear Time

------------------------------------------

Monday October 18, 16:00

ABSTRACT:

The notion of Linear Time is not as robust as, say Polynomial Time.

Therefore there exist several linear time complexity classes.

In recent years there have been given several logical and algebraic

characterizations of such classes that shall be surveyed in this talk.

The classes under consideration are given by all problems computable in

linear time on

- deterministic or non-deterministic

- Turing machines or Random Access Machines.

There are several motivations for such characterizations. First, it is

often useful to get a different view of a complexity class. Second, such

characterizations often lead to the discovery of complete problems. Third,

a logical characterizations of a complexity class might be the first step

of a lower bound proof, e.g. by using logical games.

Besides these complexity theoretic motivations logical characterizations

of deterministic linear time classes may help in constructing query

languages that are able to express exactly all linear-time-evaluable

queries.

!!! NEW PLACE:

Seminarraum, Institut fuer Informationssysteme,

FAVORITENSTRASSE 9, STIEGE 2, 3. STOCK, Room HF 0309

See http://www.dbai.tuwien.ac.at/address for directions.

------------------------

Kurt-Goedel-Gesellschaft

Technische Universitaet Wien

Institut fuer Computersprachen E185.2

Favoritenstrasse 9, 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

**Next message:**Helmut Veith : "October 25: J. Wiedermann"**Previous message:**Helmut Veith : "June 24: A. Voronkov, Expressive power and data complexity of first-order logic over trees"

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