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