DIMACS Workshop on Finite Models and Descriptive Complexity
Program of Workshop
Sunday, January 14, 1996
9:00 a.m. Moshe Vardi
"Program logics and finite-model theory"
10:00 break
10:30 Jerzy Tyszkiewicz
"Kolmogorov expressive power and Kolmogorov
descriptive complexity"
11:00 Allen Emerson
"Model Checking and the Mu-calculus"
12:00 lunch
2:00 Toniann Pitassi
"Algebraic Propositional Proof Systems"
3:00 Miki Ajtai
"Induction Axioms for Finite Models"
3:30 break
4:00 Martin Grohe
"Deterministic transitive closure in small
fragments of fixed point logics"
4:30 Gregory McColm
"Pebble Games and Zero-One Laws"
6:00 -- 9:00: Reception
=============================================================================
Monday, January 15, 1996
9:00 a.m. Tribute to the memory of Paris Kanellakis
10:00 break
10:30 Serge Abiteboul
"Temporal versus First-Order Logic to query
temporal databases"
11:00 Victor Vianu
"Databases and Finite-Model Theory"
12:00 lunch
2:00 Daniel Leivant
"Unifying concepts in implicit computational complexity"
3:00 Alex Stolboushkin
"Linear vs. Order Constraint Queries Over
Rational Databases"
3:30 break
4:00 Guozhu Dong
"Incremental database view maintenance using
first order logic"
4:30 Vladimir Sazonov
"On computability over hereditarily-finite sets in
logarithmic space"
=============================================================================
Tuesday, January 16, 1996
9:00 a.m. Ron Fagin
"Simplified Proofs about Logical Games"
10:00 break
10:30 Martin Otto
"Reductions concerning the number of variables"
11:00 Bruno Courcelle
"Graph structure definition using monadic
second-order languages"
12:00 lunch
2:00 Howard Straubing
"Finite Models, Automata and Circuit Complexity"
3:00 Gyuri Turan
"Computational learning theory and logic"
3:30 break
4:00 Jose Antonio Medina
"A Generalization of Fagin's Theorem"
4:30 Georg Gottlob
"Normal Forms for Second-Order Logic over Finite Structures,
and Classification of NP Optimization Problems"
=============================================================================
Wednesday, January 17, 1996
9:00 Lauri Hella
"Generalized quantifiers in finite model theory"
10:00 break
10:30 Steven Lindell
"Fixed-point vs. First-order definability on
structures with arithmetic"
11:00 Erich Graedel
"The classical decision problem and its connections
to finite model theory"
11:30 Clemens Lautemann
"On Binary NP"
12:00 lunch
=============================================================================
Organizers: Neil Immerman and Phokion Kolaitis
Local Arrangements: Ms. Sandy Barbu
e-mail: immerman@cs.umass.edu, kolaitis@cse.ucsc.edu, barbu@cs.princeton.edu
Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on November 30, 1995