SUNDAY 29 JUNE
08:30-09:30 Invited Speaker
(Chair: Andrew Pitts)
Luca Cardelli:
A Theory of Objects.
09:30-10:00 Coffee break
10:00-12:00 Rewriting & Deduction
(Chair: Claude Kirchner)
Franz Baader:
Combination of Compatible Reduction Orderings that are
Total on Ground Terms.
Jean-Pierre Jouannaud, Adel Bouhoula:
Automata-Driven Automated Induction.
Hubert Comon, Florent Jacquemard:
Ground Reducibility is EXPTIME-Complete.
Roberto Di Cosmo, Delia Kesner:
Strong Normalization of Explicit Substitutions via Cut
Elimination in Proof Nets.
12:00-13:30 Lunch
13:30-15:30 Linear Logic & Game Semantics
(Chair: Pat Lincoln)
Max Kanovich, Takayasu Ito:
Temporal Linear Logic Specifications for
Concurrent Processes.
Jim Laird:
Full Abstraction for Functional Languages with Control.
Vincent Danos, Patrick Baillot, Thomas Ehrhard:
Believe it or not, AJM's Games Model is a Model of
Classical Linear Logic.
Dominic J.D. Hughes:
Games and Definability for System F.
15:30-16:00 Coffee break
16:00-17:30 Model Checking
(Chair: Ken McMillan)
Henrik Reif Andersen, Henrik Hulgaard:
Boolean Expression Diagrams.
Igor Walukiewicz, Stefan Dziembowski, Marcin Jurdzinski:
How Much Memory is Needed to Win Infinite Games?
Marta Kwiatkowska, Michael Huth:
Quantitative Analysis and Model Checking.
18:00-19:00 Invited Speaker
(Chair: Moshe Vardi)
Anita Feferman:
The Saga of Alfred Tarski: From Warszawa to Berkeley
MONDAY 30 JUNE
08:30-10:00 Tutorial
(Chair: David Basin)
David McAllester:
Methods of Automated Complexity Analysis for
Inference Rules.
10:00-10:30 Coffee break
10:30-12:00 Concurrency
(Chair: Matthew Hennessy)
Naoki Kobayashi:
A Partially Deadlock-Free Typed Process Calculus.
Julian Rathke:
Unique Fixpoint Induction for Value-Passing Processes.
Prakash Panangaden, Richard Blute, Josee Desharnais,
Abbas Edalat:
Bisimulation for Labelled Markov Processes.
12:00-13:30 Lunch
13:30-15:30 Temporal Logic & Automata
(Chair: Colin Stirling)
Oded Maler, Eugene Asarin, Paul Caspi:
A Kleene Theorem for Timed Automata.
David Janin:
Automata, Tableaus and a Reduction Theorem for Fixpoint
Calculi in Arbitrary Complete Lattices.
Igor Walukiewicz, P.S. Thiagarajan:
An Expressively Complete Linear Time Temporal Logic for
Mazurkiewicz Traces.
Dexter Kozen:
On the Complexity of Reasoning in Kleene Algebra.
15:30-16:00 Coffee break
16:00-18.00 Finite Model Theory
(Chair: Anuj Dawar)
Leonid Libkin:
On the Forms of Locality over Finite Models.
Martin Grohe:
Large Finite Structures with Few L^{\em k}-Types.
Kousha Etessami, Moshe Y. Vardi, Thomas Wilke:
First-Order Logic with Two Variables and
Unary Temporal Logic.
Wolfgang Thomas, Oliver Matz:
The Monadic Quantifier Alternation Hierarchy over
Graphs is Infinite.
20:00 Business meeting
TUESDAY 1 JULY
08:30-09:30 Invited Speaker
(Chair: Damian Niwinski)
Leszek Pacholski:
Set Constraints.
09:30-10:00 Coffee break
10:00-12:00 Semantics & Domain Theory I
(Chair: Stephen Brookes)
Peter John Potts, Abbas Edalat, Martin Hötzel Escardo:
Semantics of Exact Real Arithmetic.
Jon G. Riecke, Anders Sandholm:
A Relational Account of Call-by-Value Sequentiality.
Gordon Plotkin, Marcelo Fiore, John Power:
Complete Cuboidal Sets in Axiomatic Domain Theory.
Gordon Plotkin, Daniele Turi:
Towards a Mathematical Operational Semantics.
12:00-13:30 Lunch
13:30-15:30 Decidability & Complexity Theory
(Chair: Jan Krajicek)
Sergei Vorobyov:
The "Hardest" Natural Decidable Theory.
Leszek Pacholski, Wieslaw Szwast, Lidia Tendera:
Complexity of Two-Variable Logic with Counting.
Erich Grädel, Martin Otto, Eric Rosen:
Two-Variable Logic with Counting is Decidable.
William C. Rounds, Guo-Qiang Zhang:
Complexity of Power Default Reasoning.
15:30-16:00 Coffee break
16:00-17:30 Types and Constraints
(Chair: Jens Palsberg)
Nevin Heintze, David McAllester:
On the Cubic Bottleneck in Subtyping and Flow Analysis.
Fritz Henglein, Jakob Rehof:
The Complexity of Subtype Entailment for Simple Types.
Witold Charatonik, Andreas Podelski:
Set Constraints with Intersection.
19:30 Banquet (The Royal Castle)
WEDNESDAY 2 JULY
08:30-10:00 Tutorial
(Chair: Claude Kirchner)
Hubert Comon:
Applications of Tree Automata in Rewriting and
Lambda Calculus.
10:00-10:30 Coffee break
10:30-12:00 Semantics & Domain Theory II
(Chair: Pierre-Louis Curien)
Martín Hötzel Escardó, Thomas Streicher:
Induction and Recursion on the Partial Real Line via
Biquotients of Bifree Algebras.
Martin Hofmann, Thomas Streicher:
Continuation Models are Universal for
$\lambda\mu$-calculus.
Pawel Urzyczyn, Jerzy Tiuryn,
Mariangiola Dezani-Ciancaglini:
Discrimination by Parallel Observers.
12:00-13:30 Lunch
13:30-15:00 Unification and Higher-Order Logic
(Chair: Amy Felty)
Jean Goubault-Larrecq:
Ramified Higher-Order Unification.
Iliano Cervesato, Frank Pfenning:
Linear Higher-Order Pre-Unification.
Raymond McDowell, Dale Miller:
A Logic for Reasoning with Higher-Order Abstract Syntax.
Leonid Libkin