Lecture Today: T. Schwentick, Characterizing Linear Time


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


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



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