LICS'97 Program

LICS'97 Program



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