FLoC'99

WORKSHOP ON FINITE MODEL THEORY AND ITS APPLICATIONS
THE 1999 FEDERATED LOGIC CONFERENCE
July 1, 1999

The interactions between finite model theory and computer science have expanded both in depth and in scope in recent years. Well-established connections, such as those between finite model theory and complexity theory and with relational databases, remain extremely fruitful. In addition, there are newer connections, such as those between finite model theory and verification, between finite model theory and linguistics, and between finite model theory and new database models (e.g. spatial and temporal databases). The goal of this one-day informal workshop is both to allow established researchers in the field of finite model theory to share contributions, and to introduce these new developments to a wide audience.

Invited speakers. Martin Grohe, Kerkko Luosto, Martin Otto.

Registration  will be handled by FLoC'99. Please visit http://floc99.itc.it to register.
The fee is 80 euros, and it includes:

Organizers.
Michael Benedikt, e-mail:benedikt@research.bell-labs.com.
Leonid Libkin, e-mail:libkin@research.bell-labs.com.
Jouko Väänänen, e-mail:jvaanane@cc.helsinki.fi.
 

                                                                  PROGRAM


SPECIAL SESSION: JOINT INVITED TALKS BY FLoC WORKSHOPS W1, W12 AND W14.

June 30                         Room 8-L
13:50-14:40 Neil Immerman (U. Mass)
Dynamic Reachability 
14:50-15:40 Thomas Schwentick (U. Mainz): 
The Linear Order in Descriptive Complexity Theory
15:40-16:10 COFFEE BREAK
16:10-17:00 Victor Vianu (UC San Diego): 
Topological Queries in Spatial Databases 
17:10-18:00 Christos Papadimitriou (UC Berkeley):
Complexity in AI and Knowledge Representation

                       WORKSHOP PROGRAM    JULY 1                Room 8-L
9:00-9:50 INVITED TALK :  Martin Grohe (U. Freiburg)
Identifying embeddable graphs with few variables
9:50-10:15 Efficient Fragment of Transitive Closure Logic
Natasha Alechina (U. Nottingham),
Neil Immerman (UMass)
10:15-10:40 Logical description of cross-serial dependencies
Hans-Peter Kolb, Uwe Moennich, Frank Morawietz (U. Tuebingen)
10:40-11:10  coffee break
11:10-12:00 INVITED TALK : Kerkko Luosto (Helsinki U.)
Special techniques for analyzing the expressive power of 
generalized quantifiers
12:00-12:25 Efficient Algorithms for Optimization and
Enumeration Problems on Patchable Graphs
Janos Makowsky (Technion)
12:25-2:00 lunch
14:10--15:00 INVITED TALK: Martin Otto (RWTH Aachen)
Issues in algorithmic model theory for specific domains
15:05-15:30 On the Complexity of Random Maps 
Kevin Compton (BRICS and U. Michigan)
15:30-16:00 Coffee break
16:00-16:25 Datalog LITE: temporal versus deductive reasoning 
in verification
Georg Gottlob (TU Vienna), 
Erich Graedel (RWTH Aachen),
Helmut Veith (TU Vienna)
16:25-16:50 First-order topological properties of planar 
spatial databases
Bart Kuijpers (U Antwerp)
16:50-17:15 Descriptive Complexity Theory for Constraint Databases
Stephan Kreutzer (RWTH Aachen)
17:15-17:40 On Second-Order Generalized Quantifiers
Anders Andersson (Uppsala U.)
17:40-17:50 refreshments
17:50-18:40 The descriptive complexity of constraint satisfaction
Moshe Y. Vardi 
(joint with workshop on Implicit Computational Complexity; Room 7-L)