The following papers will be presented during the conference's paper sessions.

• Solving Over-Constrained Problems with SAT Technology
  Josep Argelich and Felip Manya

• A Symbolic Search Based Approach for Quantified Boolean Formulas
  Gilles Audemard and Lakhdar Sais

• Substitutional Definition of Satisfiability in Classical Propositional Logic
  Anton Belov and Zbiginiew Stachniak

• A Clause-Based Heuristic for {SAT Solvers
  Nachum Dershowitz, Ziyad Hanna and Alexander Nadel

• Effective Preprocessing in {SAT through Variable and Clause Elimination
  Niklas Een and Armin Biere

• Resolution and Pebbling Games
  Nicola Galesi and Neil Thapen

• Local and Global Complete Solution Learning Methods for QBF
  Ian P. Gent and Andrew G.D. Rowley

• Equivalence checking of circuits with parameterized specifications
  Euguene Goldberg

• Observed Lower Bounds for Random 3-SAT Phase Transition Density using Linear Programming
  Marijn Heule and Hans van Maaren

• Simulating Cutting Plane proofs with restricted degree of falsity by Resolution
  Edward A. Hirsch and Sergey I. Nikolenko

• Resolution Tunnels for Improved SAT Performance
  Michal Kouril and John Franco

• Diversification and determinism in local search for satisfiability
  Chu Min Li and Wen Qi Huang

• On Finding All Minimally Unsatisfiable Subformulas
  Mark Liffiton and Karem Sakallah

• Optimizations for Compiling Declarative Models into Boolean Formulas
  Darko Marinov, Sarfraz Khurshid, Suhabe Bugrara, Lintao Zhang and Martin Rinard

• Random Walk With Continuously Smoothed Variable Weights
  Steven Prestwich

• Derandomization of PPSZ for Unique-k-SAT
  Daniel Rolf

• Heuristics for Fast Exact Model Counting
  Tian Sang and Paul Beame and Henry Kautz

• A Scalable Method for Solving Satisfiability of Integer Linear Arithmetic Logic
  Hossein M Sheini and Karem A. Sakallah

• DPvis - A Tool to Visualize the Structure of SAT Instances
  Carsten Sinz and Edda-Maria Dieringer

• Constraint Metrics for Local Search
  Finnegan Southey

• Input Distance and Lower Bounds for Propositional Resolution Proof Length
  Allen Van Gelder

• Sums of Squares, Satisfiability and Maximum Satisfiability
  Hans van Maaren and Linda van Norden

• Faster Exact Solving of SAT Formulae with a Low Number of Occurrences per Variables
  Magnus Wahlstrom

• A New Approach to Model Counting
  Wei Wei and Bart Selman

• Benchmarking SAT Solvers for Bounded Model Checking
  Emmnauel Zarpas

• On Subsumption Removal and On-the-Fly CNF Simplification
  Lintao Zhang

• Model-Equivalent Reductions
  Xishun Zhao and Hans Kleine Buning

The following papers will be presented during the conference's poster session.

• Improved Exact Solvers for Weighted Max-SAT
  Teresa Alsinet, Felip Manya and Jordi Planes

• Quantifier Trees for QBF
  Marco Benedetti

• Quantifier Rewriting and Equivalence Models for Quantified Horn Formulas
  Uwe Bubeck, Hans Kleine Buning and Xishun Zhao

• A Branching Heuristic Directed for Quantified Renamable Horn Formulas
  Sylvie Coste-Marquis, Daniel Le Berre and Florian Letombe

• An Improved Upper Bound for SAT
  Evgeny Dantsin and Alexander Wolpert

• Bounded Model Checking with QBF
  Nachum Dershowitz, Ziyad Hanna and Jacob Katz

• Variable Ordering for Efficient SAT Search by Analyzing Constraint-Variable Dependencies
  Vijay Durairaj and Priyank Kalla

• Cost-Effective Hyper-Resolution for Preprocessing CNF Formulas
  Roman Gershman and Ofer Strichman

• Automatic Generation of Simplification Rules for SAT and MAXSAT
  Alexander S. Kulikov

• Speedup Techniques Utilized in Modern SAT Solvers
  Matthew T. Lewis, Tobias Schubert and Bernd W. Becker

• FPGA Logic Synthesis using Quantified Boolean Satisfiability
  Andrew C. Ling, Deshanand P. Singh and Stephen D. Brown

• On Applying Cutting Planes in DLL-Based Algorithms for Pseudo-Boolean Optimization
  Vasco M. Manquinho and Joao Marques-Silva

• A New Set of Algebraic Benchmark Problems for SAT Solvers
  Andreas Meier and Volker Sorge

• A Branch and Bound Algorithm for Extracting Smallest Minimal Unsatisfiable Formulas
  Maher N. Mneimneh, Ines Lynce, Zaher S. Andraus, Joao Marques-Silva, Karem A. Sakallah

• Threshold Behaviour of WalkSAT and Focused Metropolis Search on Random 3-Satisfiability
  Sakari Seitz, Mikko Alava and Pekka Orponen

Accepted papers in Track A (65 papers) 
--------------------------------------

Philip Bille and Inge Li Grtz. 
The Tree Inclusion Problem: In Optimal Space and Faster

Miroslaw Kowaluk and Andrzej Lingas.
LCA queries in directed  acyclic graphs

Leah Epstein and Meital Levy.
Online Interval Coloring and Variants

Bengt J. Nilsson.
Approximate Guarding of Monotone and Rectilinear Polygons

Kamal Jain, MohammadTaghi Hajiaghayi and Kunal Talwar.
The Generalized Deadlock Resolution Problem

Martin Dietzfelbinger and Christoph Weidling. 
Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bin

Stephanie Wehner and Ronald de Wolf.
Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval

Juraj Hromkovic and Georg Schnitger. 
NFAs with and without $\epsilon$-transitions

Jochen Knemann, Stefano Leonardi, Guido Schfer and Stefan van Zwam.
From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the
Steiner Forest Problem

Douglas Wikstrm. On the l-Ary GCD-Algorithm in Rings of Integers

Chen Avin and Gunes Ercal. 
On The Cover Time of Random Geometric Graphs

Petra Berenbrink, Tom Friedetzky and Russell Martin. 
Dynamic Diffusion Load Balancing

Corina E. Patrascu and Mihai Patrascu.
On Dynamic Bit-Probe Complexity

Ingo Wegener. 
Simulated annealing beats Metropolis in combinatorial optimization

Christoph Ambhl.
An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks

Martin Farach-Colton, Gad M. Landau, S. Cenk Sahinalp and Dekel Tsur. 
Optimal spaced seeds for faster approximate string matching

Jiri Fiala, Peter Golovach and Jan Kratochvil.
Distance constrained labelings of graphs of bounded treewidth

Pascal Koiran, Vincent Nesme and Natacha Portier. 
A quantum lower bound for the query complexity of Simon's problem

Amit Kumar, Yogish Sabharwal and Sandeep Sen. 
Linear Time Algorithms for Clustering Problems in any dimensions

Charilaos Efthymiou and Paul Spirakis. 
On the Existence of Hamiltonian Cycles in Random Intersection Graphs

Martin Gairing, Burkhard Monien and Andreas Woclaw. 
A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines

Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman and David Peleg. 
Label-Guided Graph Exploration by a Finite Automaton

Nedialko B. Dimitrov and C. Greg Plaxton. 
Optimal Cover Time for a Graph-Based Coupon Collector Process

Gustav Hast. 
Approximating Max kCSP - outperforming a random assignment with almost a linear factor

Marie-Pierre Beal, Sylvain Lombardy and Jacques Sakarovitch. 
On the equivalence of Z-automata

Eugen Czeizler and Jarkko Kari.
A tight linear bound on the neighborhood of inverse cellular automata

Robert Spalek and Mario Szegedy. 
All Quantum Adversary Methods are Equivalent

Martin Beaudry, Francois Lemieux and Denis Therien. 
Groupoids that recognize only regular languages

Qian-Ping Gu and Hisao Tamaki. Optimal branch-decomposition of
planar graphs in $O(n^3)$ time

Jeff Ford and Anna Gal. 
Hadamard tensors and lower bounds on multiparty communication complexity

Telikepalli Kavitha.
An \tilde{O}(m^2n) Randomized Algorithm to compute a Minimum Cycle Basis of a Directed Graph

Fedor V. Fomin, Fabrizio Grandoni and Dieter Kratsch. 
Measure and Conquer: Domination - A Case Study

Isaac Elias and Jens Lagergren. 
Fast Neighbor Joining

Henry Lin, Tim Roughgarden, Eva Tardos and Asher Walkover. 
Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability

George Karakostas. 
A better approximation ratio for the Vertex Cover problem

David Kempe, Jon Kleinberg and Eva Tardos.
Influential Nodes in a Diffusion Model for Social Networks

Stephen Alstrup, Inge Li Grtz, Theis Rauhe, Mikkel Thorup and Uri Zwick. 
Union-Find with Constant Time Deletions

Bogdan Chlebus, Leszek Gasieniec, Dariusz Kowalski and Tomasz
Radzik. 
On the Wake-up Problem in Radio Networks

Li Zhang. 
The efficiency and fairness of a fixed budget resource allocation game

Manfred Droste and Paul Gastin. 
Weighted automata and weighted logics

Annamaria Kovacs. 
Fast Preemptive Sum-Multicoloring on Paths

Wun-Tat Chan, Tak-Wah Lam and Prudence Wong. 
Dynamic Bin Packing of Unit Fractions Items

Gianni Franceschini and Roberto Grossi.
Optimal In-Place Sorting of Vectors and Records

Liam Roditty and Uri Zwick. 
Replacement paths and k simple shortest paths in unweighted directed graphs

Hema Jampala and Norbert Zeh. 
Cache-Oblivious Planar Shortest Paths

Sriram Pemmaraju and Rajiv Raman. 
Approximation Algorithms for the Max-Coloring Problem

Ehsan Chiniforooshan, Arash Farzan and Mehdi Mirzazadeh. 
Worst Case Optimal Union-Intersection Expression Evaluation

Mihai Badoiu, Artur Czumaj, Piotr Indyk and Christian Sohler.
Facility Location in Sublinear Time

Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro and Peter Sanders.
Towards Optimal Multiple Selection

Jaikumar Radhakrishnan, Martin Roetteler and Pranab Sen. 
On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group

Arkadev Chattopadhyay and Kristoffer Arnsfelt Hansen. 
Lower Bounds for Circuits With Few Modular and Symmetric Gates

Pascal Tesson and Denis Thrien. 
Restricted Two-Variable FO+MOD Sentences, Circuits and Communication Complexity

Anupam Gupta and Martin Pal.
Stochastic Steiner Trees without a Root

Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo and Martin Skutella.
New Approaches for Virtual Private Network Design

Debora Donato, Stefano Leonardi and Panayiotis Tsaparas. 
Stability and Similarity of Link Analysis Ranking algorithms

Khaled Elbassioni, Aleksei V. Fishkin, Nabil H. Mustafa and Rene Sitters.
Approximation Algorithms for Euclidean Group TSP

Manan Sanghi, Ming-Yang Kao and Robert Schweller. 
Randomized Fast Design of Short DNA Words

David cashman, Avner magen and Allan borodin. 
How well can Primal-Dual and Local-Ratio algorithms perform?

Gerth Brodal, Rolf Fagerberg and Gabriel Moruz.
Cache-Aware and Cache-Oblivious Adaptive Sorting

Liam Roditty, Mikkel Thorup and Uri Zwick.
Deterministic constructions of approximate distance oracles and spanners}

Scott Diehl and Dieter Van Melkebeek. 
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines

Frederic Magniez and Ashwin Nayak. 
Quantum Complexity of Testing Group Commutativity

Paul Beame, Toniann Pitassi and Nathan Segerlind. 
Lower bounds for Lovasz-Schrijver systems and beyond, using multiparty communication complexity

Matthias Englert and Matthias Westermann. 
Reordering Buffer Management for Non-Uniform Cost Models

Matthew Cary, Atri Rudra and Ashish Sabharwal. 
On the Hardness of Embeddings Between Two Finite Metrics

Accepted papers in Track B (24 papers) 
--------------------------------------

Albert Atserias, Anuj Dawar and Martin Grohe.
Preservation under Extensions on Well-Behaved Finite Structures

Franck van Breugel, Claudio Hermida, Michael Makkai and James Worrell.
An Accessible Approach to Behavioural Pseudometrics

Parosh Abdulla, Johann Deneux, Joel Ouaknine and James Worrell. 
Decidability and Complexity Results for Timed Automata via Channel Machines

Krishnendu Chatterjee, Luca de Alfaro and Thomas A. Henzinger.
The Complexity of Stochastic Rabin and Streett Games

Damien Pous.
Up-to Techniques for Weak Bisimulation

Roberto Giacobazzi and Mila Dalla Preda.
Semantic-based Code Obfuscation by Abstract Interpretation

Michael Mislove.
Discrete Random Variables Over Domains

Rajeev Alur, Viraj Kumar, P. Madhusudan and Mahesh Viswanathan.
Congruences for Visibly Pushdown Languages

Cheng Li, Zhe Dang, Oscar Ibarra and Hsu-Chun Yen.
Signaling P Systems and Verification Problems

Wan Fokkink and Sumit Nain.
A Finite Basis for Failure Semantics

Damian Niwinski, Pawel Urzyczyn, Igor Walukiewicz and Teodor Knapik. 
Unsafe grammars and panic automata

Kousha Etessami and Mihalis Yannakakis.
Recursive Markov Decision Processes and Recursive Stochastic Games

Andrzej S. Murawski, C.-H. L. Ong and Igor Walukiewicz.
Idealized Algol with Ground Recursion, and DPDA Equivalence

Eric Badouel, Jules Chenou and Goulven Guillou.
Petri Algebras

Eugene Asarin and Pieter Collins.
Noisy Turing Machines

Giovanni Conforti, Damiano Macedonio and Vladimiro Sassone. BiLogics: 
Spatial-Nominal Logics for Bigraphs

MohammadReza Mousavi and Michel A. Reniers.
Orthogonal Extensions in Structural Operational Semantics

Martin Grohe, Christoph Koch and Nicole Schweikardt.
Tight Lower Bounds for Query Processing on Streaming and  External 
Memory Data

Aaron Bradley, Zohar Manna and Henny Sipma.
The Polyranking Principle

James Laird.
Decidability in Syntactic Control of Interference

Giorgio Delzanno and Maurizio Gabbrielli.
Compositional Verification of Asynchronous Processes via Constraint Solving

Bernhard Reus and Thomas Streicher.
About Hoare Logics for Higher-order Store

Michael Baldamus, Joachim Parrow and Björn Victor.
A Fully Abstract Encoding of the Applied pi-Calculus

Rocco De Nicola, Daniele Gorla and Rosario Pugliese.
Basic Observables for a Calculus for Global Computing

Accepted papers in Track C (24 papers) 
--------------------------------------

Klaus Kursawe and Victor Shoup
Optimistic Asynchronous Atomic Broadcast

Mitsuhiro Haneda, Mitsuru Kawazoe and Tetsuya Takahashi
Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting
Formulae for Hyperelliptic Curves of Type $y^2=x^{2k+1}+ax$

An Braeken, Yuri Borissov, Svetla Nikova and Bart Preneel
Classification of Boolean Functions of 6 Variables or Less with
Respect to Cryptographic Properties

Dario Catalano and Ivan Visconti
Hybrid Trapdoor Commitments and their Applications

Marius Zimand.
Simple extractors via constructions of cryptographic
pseudo-random generators

Helger Lipmaa, Guilin Wang and Feng Bao
Designated Verifier Signature Schemes: Attacks, New Security
Notions and A New Construction

Nicholas Hopper
On Steganographic Chosen Covertext Security

Marten Trolin and Douglas Wikstrom
Hierarchical Group Signatures

Ueli Maurer and Johan Sjodin.
Single-Key AIL-MACs from any FIL-MAC

Giovanni Di Crescenzo and Aggelos Kiayias
Asynchronous Perfectly Secure Communication over One-time Pads

Giuseppe Persiano and Ivan Visconti.
On the Round Complexity of Unbounded Concurrent Security.

Combining Intruder Theories.
Chevalier Yannick and Rusinowitch Michael

Martin Abadi and Bogdan Warinschi
Password-Based Encryption Analyzed

Mathieu Baudet, Veronique Cortier and Steve Kremer
Computationally sound implementations of equational theories against passive adversaries

Giovanni Di Crescenzo and Ivan Visconti
Concurrent Zero-Knowledge in the Public-Key Model

Roberto Tamassia and Nikos Triandopoulos
Computational Bounds on Hierarchical Data Processing with
Applications to Information Security

Neeraj Kayal
Solvability of a System of Bivariate Polynomial Equations over a
Finite Field

Marc Fischlin
Completely Non-Malleable Schemes

David Galindo
Improved Identity Based Encryption

Omer Horvitz and Jonathan Katz
Lower Bounds on the Efficiency ``Black-Box'' Commitment Schemes

Hoeteck Wee
On Round-Efficient Argument Systems

Craig Gentry and Zulfikar Ramzan
Towards Computational Private Block Retrieval with Asymptotically
Optimal Communication Rate

Tal Moran and Moni Naor
Basing Cryptographic Protocols on Tamper-Evident Seals

Eike Kiltz, Anton Mityagin, Saurabh Panjwani and Barath Raghavan
Append-Only Signatures

Sunday, May 22nd, 2005

Monday, May 23rd, 2005

Tuesday, May 24th, 2005

• Geoffrey Washburn and Stephanie Weirich. Generalizing Parametricity UsingInformation-flow
• Clemens Kupke and Yde Venema. Closure properties of coalgebra automata
• Abbas Edalat and Dirk Pattinson. Inverse and Implicit Functions in Domain Theory
• Jerome Leroux. A Polynomial Time Presburger Criterion and Synthesis forNumber Decision Diagrams
• Patrice Godefroid and Michael Huth. Model Checking Vs. Generalized ModelChecking: Semantic Minimizations for Temporal Logics
• Giuseppe Castagna, Rocco De Nicola and Daniele Varacca. Semantic Subtypingfor the PI-calculus
• Paul-Andre Mellies and Jerome Vouillon. Recursive polymorphic types andparametricity in an operational framework
• Pawel Sobocinski and Vladimiro Sassone. Reactive systems over cospans
• Anuj Dawar and Martin Otto. Modal Characterisation Theorems over SpecialClasses of Frames
• Emanuel Kieronski and Martin Otto. Small Substructures and DecidabilityIssues for First-Order Logic with Two Variables
• Richard Mayr, Parosh Abdulla and Noomene Ben Henda. Verifying InfiniteMarkov Chains with a Finite Attractor or the Global Coarseness Property
• Hongseok Yang, Lars Birkedal and Noah Torp-Smith. Semantics ofSeparation-logic Typing and Higher-order Frame Rules
• Kohei Honda, Martin Berger and Nobuko Yoshida. An Observationally CompleteLogic for Imperative Higher-Order Functions
• Bernd Finkbeiner and Sven Schewe. Uniform Distributed Synthesis
• Leonid Libkin and Pablo Barcelo. Temporal Logics over Unranked Trees
• Victor Dalmau. Generalized Majority-Minority Operations are Tractable
• Glynn Winskel. Name Generation and Linearity
• Ugo Dal Lago. The Geometry of Linear Higher-Order Recursion
• Maarten Marx and Evan Goris. Looping Caterpillars
• Luigi Santocanale. Completions of mu-algebras
• Soren Lassen. Normal Form Bisimulation for Call-By-Value Lambda Calculus
• Javier Esparza, Antonin Kucera and Richard Mayr. Quantitative Analysis of Probabilistic Pushdown Automata: Expectations and Variances
• Lutz Strassburger and Francois Lamarche. Constructing free Booleancategories
• Joel Ouaknine and James Worrell. On the Decidability of Metric TemporalLogic
• Martin Escardo and Ho Weng Kin. Operational domain theory and topology of asequential programming language
• Albert Atserias. Definability on a Random 3-CNF Formula
• Bruno Blanchet, Martin Abadi and Cedric Fournet. Automated Verification ofSelected Equivalences for Security Protocols
• Alexis Saurin. Separation with streams in the $\Lambda\mu$-calculus
• Krishnendu Chatterjee, Thomas A. Henzinger and MarcinJurdzinski. Mean-Payoff Parity Games
• Hannu Niemisto. On locality and uniform reduction
• Claudia Faggian and Francois Maurel. Ludics nets, a model of concurrentinteraction
• Christel Baier and Marcus Groesser. Recognizing omega-regular languageswith probabilistic automata
• Iovka Boneva, Jean-Marc Talbot and Sophie Tison. Expressiveness of aspatial logic for trees
• Christopher Hardin. Proof Theory for Kleene Algebra
• Benjamin Rossman. Existential Positive Types and Preservation underHomomorphisms
• Paul-Andre Mellies. A fully complete model of propositional linear logic
• Markus Lohrey. Model-Checking Hierarchical Structures
• Masahito Hasegawa. Relational Parametricity and Control
• Martin Hofmann. Proof-theoretic approach to description-logic
• Thorsten Altenkirch and Jonathan Grattage. A functional quantum programminglanguage
• Michael Maher. Herbrand Constraint Abduction
• Jos C.M. Baeten and Flavio Corradini. A Characterization of RegularExpressions in Process Algebra
• Limin Jia, Frances Spalding, David Walker and Neal Glew. CertifyingCompilation for a Language with Stack Allocation
• Albert Atserias. On Digraph Coloring Problems and Treewidth Duality

PROGRAM

Wednesday, June 22:

6:30pm - 8:30pm WELCOME RECEPTION

Thursday, June 23:

9:00-10:00 INVITED TALK 

Patrice Godefroid (Lucent Bell Labs)
	Generalized Model Checking

BREAK

10:30-12:00 Temporal Databases 1

Nicole Bidoit, Matthieu Objois
	Temporal query languages expressive power: muTL versus T-WHILE
Mohammed H. Al-Kateb, Essam M. Mansour, and Mohamed E. El-Sharkawi
	CME: A Temporal Relational Model for Efficient Coalescing
Carlo Combi and Angelo Montanari and Rosalba Rossato
	A uniform algebraic characterization of temporal functional dependencies

LUNCH BREAK

2:00-3:30 Temporal Logic in Computer Science 1

Andreas Schaefer
	Axiomatisation and decidability of multi-dimensional duration calculus
Carsten Lutz, Dirk Walther and Frank Wolter
	Quantitative temporal logics: PSPACE and below
Stephane Demri, Ranko Lazic, David Nowak
	On the freeze quantifier in Constraint LTL: decidability and complexity


BREAK & POSTERS

4:30-5:30 Temporal Representation and Reasoning in AI 1

Claudio Bettini, Sergio Mascetti
	An efficient algorithm for minimizing time granularity periodical representations
Mahat Khelfallah and Belaid Benhamou
	A Local Method for Prioritized Fusion of Temporal Information

Friday, June 24:

9:00-10:00 INVITED TALK 

Betty Salzberg (Northeastern) 
      Indexing Inventory Snapshots

BREAK

10:30-12:00 9:00-10:30  Temporal Logic in Computer Science 2

Marko Samer, Helmut Veith
	Deterministic CTL Query Solving
Pieter Hartel
	A trace semantics for Positive Core XPath
Alexei Lisitsa and Igor Potapov
	Temporal logic with predicate lambda-abstraction

LUNCH 

2:00-3:00 Temporal Representation and Reasoning in AI 2

Krzysztof R. Apt, Sebastian Brand
	Constraint-Based Qualitative Simulation
Philippe Muller, Axel Reymoneti
	Using inference for evaluating models of temporal discourse

BREAK & POSTERS

4:00-5:00  Temporal Logic in Computer Science 3

Ben D'Angelo, Sriram Sankaranarayanan, Cesar Sanchez, Will Robinson,
Bernd Finkbeiner, Henny B. Sipma, Sandeep Mehrotra, Zohar Manna
	Lola: Runtime Monitoring of Synchronous Systems
Roger Villemaire, Sylvain Halle, Omar Cherkaoui
	Configuration Logic: A multi-site Modal Logic

BOAT TOUR AND BANQUET (6:30)

Saturday, June 25:

9:00-10:00 TUTORIAL

James Pustejovsky (Brandeis)
      Time and the Semantic Web

BREAK

10:30-12:00 Temporal Databases 2

Fusheng Wang, Carlo Zaniolo, Xin Zhou
	Temporal XML? SQL Strikes Back!
Amal Elnahas, Omar Karam, Ingy Ramzy, Ahmed Hamad
	"TellMe": A Novel Location Management and Prediction Protocol for Moving Object Databses
Kiyoung Yang and Cyrus Shahabi
	Multilevel Distance-based Index Structure for Multivariate Time Series

CONTRIBUTED POSTERS

Seo-Young Noh, Shashi K. Gadia		
       An XML-based Framework for Temporal Database Implementation

Volker Gruhn, Ralf Laue			
       Specification Patterns For Time-Related Properties

Andre Trudel & Haiyi Zhang		
       Exploiting the relationship between IA networks and finite domain CSPs

Johann Eder and Horst Pichler
       Probabilistic Time Management for Workflow Systems

M.A. Reniers and Y.S. Usenko		
       Analysis of timed processes with data using algebraic transformations

Song Lin, Stefano Lonardi, Vana Kalogeraki, Dimitrios Gunopulos	    
       Applying LVQ Techniques to Compress Historical Information in Sensor Networks

Artie Basukoski and Alexander Bolotov	
       Search Strategies for Resolution in CTL-type Logics: Extension and Complexity

INVITED POSTERS

Angelo Montanari			
       Propositional interval temporal logics: some promising paths 

The Logic and Computation Group	      	
       Time in Liverpool - An overview of Temporal Research in the Logic and Computation Group

Fusheng Wang, Carlo Zaniolo and Xin Zhou	
       Version Management and Historical Queries in Digital Libraries

Peter Revesz				
       Efficient Rectangle Indexing Algorithms Based on Point Dominance

CiE 2005 is an interdisciplinary venue for researchers from computer science and mathematics focusing on New Computational Paradigms. These include prominently connections between computation and physical systems but also higher mathematical models of computation. The researchers from the different communities will exchange ideas, approaches and techniques in their respective work, thereby generating a wider community for work on computational issues that allows uniform approaches to diverse areas, the transformation of theoretical ideas into applicable projects, and general cross-fertilization transcending disciplinary borders.

There will be two three-hour tutorials (Buhrman and Weihrauch), eight plenary talks, six special sessions with altogether 25 talks and over 50 contributed talks covering the entire range of research in computability theory.

Plenary Talks: http://www.illc.uva.nl/CiE/index.php?page=12
Special Sessions: http://www.illc.uva.nl/CiE/index.php?page=6
Contributed Papers: http://www.illc.uva.nl/CiE/index.php?page=15

Regular registration (EUR 95, EUR 75 for students) will be possible until April 30th, 2005. After May 1st, 2005, there will be an option of Late Registration with higher fees.