> Congress / Advance Programme / Conferences / TCS

Tc1 - Foundations of Computer Science

Room for TCS-Algorithms: Vignemale

Room for TCS-Logic: Carlit

TCS 2004 is composed of two distinct, but interrelated tracks.

. TCS-Algorithms focuses on Algorithms, Complexity and Models of Computation, while
. TCS-Logic focuses on Logic, Semantics, Specification and Verification.

Conference Chair: Jean-Jacques Lévy (INRIA, France)
TCS-Algorithms Chair: Ernst Mayr (Technical U. Munich, Germany)
TCS-Logic Chair: John Mitchell (Stanford U., USA)

Programme

Monday 23 August 2004

13h30-15h:

TCS1-Algorithms

Looking inside AES and BES - Ilia Toli, Alberto Zanoni (U. Pisa, Italy)

Remove Key Escrow from The Identity-Based Encryption System - Zhaohui Cheng, Richard Comely, Luminita Vasiu (Middlesex U., UK)

Randomised Algorithm for Checking the Normality of Cryptographic Boolean Functions - An Braeken (KU Leuven, Belgium), Christopher Wolf (KU Leuven /ESAT-COSIC, Belgium), Bart Preneel (KU Leuven, Belgium)

TCS1-Logic

Prototyping Proof Carrying Code - Martin Wildmoser, Tobias Nipkow, Gerwin Klein (Technical U. Munich, Germany), Sebastian Nanz (Yale U., USA)

Contract-Oriented Development of Component Software - Zhiming Liu (IIST - UNU Macau, China), He Jifeng, Xiaoshan Li (U. Macau, China)

New insights on Architectural Connectors - Roberto Bruni (U. Pisa, Italy), José Luiz Fiadeiro (U. Leicester, UK), Ivan Lanese (U. Pisa, Italy), Antonia Lopes (U. Lisbon, Portugal), Ugo Montanari (U. Pisa, Italy)

15h30-17h:

TCS2-Algorithms

Reversible Circuit Realizations of Boolean Functions - Alex Brodsky (U. Toronto, Canada)

Resource Bounded Immunity and Simplicity - Toshio Suzuki (Osaka Prefecture U., Japan), Tomoyuki Yamakami (Trent U., Canada)

Degree Bounds on Polynomials and Relativization Theory - Holger Spakowski (U. Düsseldorf, Germany), Rahul Tripathi (U. Rochester, USA)

TCS2-Logic

On Complexity of Model-Checking for the TQL Logic - Iovka Boneva, Jean-Marc Talbot (LIFL, France)

A Generic Framework for Checking Semantical Equivalences between Pushdown Automata and Finite-State Automata - Antonin Kucera (Masaryk U.,Czech Republic), Richard Mayr (Albert-Ludwigs U. Freiburg, Germany)

Tuesday 24 August 2004

10h30-12h:

TCS3-Algorithms

The Firing Squad Synchronization Problem With Many Generals For One-Dimensional CA - Hubert Schmid, Thomas Worsch (U. Karlsruhe, Germany)

A Matrix q-Analogue of the Parikh Map - Omer Egecioglu, Oscar Ibarra (U. California at Santa Barbara, USA)

TCS3-Logic

A Calculus with Lazy Module Operators - Davide Ancona, Sonia Fagorzi, Elena Zucca (U. Genova, Italy)

Dynamic Typing with Dependent Types - Xinming Ou, Gang Tan, Yitzhak Mandelbaum, David Walker (Princeton U., USA)

Subtyping-Inheritance Conflicts: The Mobile Mixin Case - Lorenzo Bettini (U. Florence, Italy), Viviana Bono (U. Torino, Italy), Betti Venneri (U. Florence, Italy)

13h30-15h:

TCS4-Algorithms

Efficient Protocols for Computing the Optimal Swap Edges of a Shortest Path Tree - Paola Flocchini (U. Ottawa, Canada), Antonio Mesa Enriques (U. la Habana, Cuba), Linda Pagli, Giuseppe Prencipe (U. Pisa, Italy), Nicola Santoro (Carleton U., Canada)

Truthful Mechanisms for Generalized Utilitarian Problems - Giovanna Melideo (U. L'Aquila, Italy), Paolo Penna (Univ. di Salerno, Italy), Guido Proietti (U. L'Aquila, Italy), Roger Wattenhofer, Peter Widmayer (ETH Zurich, Switzerland)

The Driving Philosophers - Sébastien Baehni (EPFL, Switzerland), Roberto Baldoni (U. of Roma "La Sapienza", Italy), Rachid Guerraoui, Bastian Pochon (EPFL, Switzerland)

TCS4-Logic

Effective Chemistry for Synchrony and Asynchrony - Deepak Garg, (CMU, USA), Akash Lal (U. Wisconsin, USA), Sanjiva Prasad (IIT Delhi, India)

Probabilistic Controller Synthesis - Martin Leucker (Uppsala U., Sweden), Christel Baier, Marcus Groesser (U. Bonn, Germany), Benedikt Bollig (RWTH Aachen, Germany), Frank Ciesinski, (U. Bonn, Germany)

Highly Undecidable Questions for Process Algebras - Petr Jancar (Technical U. Ostrava, Czech Republic), Jiri Srba (BRICS, Aalborg U., Danemark)

15h30-17h:

TCS5

Room: Guillaumet 1

Invited Talk (TCS-Algorithms) : Stability of Approximation in Discrete Optimization - Juraj Hromkovic (ETH Zurich, Switzerland)

TCS-Algorithms

The Inherent Queuing Delay of Parallel Packet Switches - David Hay, Hagit Attiya (Technion, Israel)

TCS-Logic

Wednesday 25 August 2004

10h30-12h:

Room: Guillaumet 2

Invited Talk (TCS-Logic) : Towards a Broader Theory of Mobile Processes - Robin Milner (Cambridge U., UK)

TCS-Algorithms

Engineering an External Memory Minimum Spanning Tree Algorithm - Roman Dementiev, Peter Sanders (Max-Planck-Institut; Germany), Dominik Schultes (U. des Saarlands, Germany), Jop Sibeyn (U. Halle, Germany)

TCS-Logic

New-HOPLA: a Higher-order Process Language with Name Generation - Glynn Winskel, Francesco Zappa Nardelli (U. Cambridge, UK)

13h30-15h:

TCS7-Algorithms

Scheduling with Release Times and Deadlines on a Minimum Number of Machines - Mark Cieliebak, Thomas Erlebach, Fabian Hennecke, Birgitta Weber, Peter Widmayer (ETH Zurich, Switzerland)

Approximation Algorithms for Mixed Fractional Packing and Covering Problems - Klaus Jansen (U. Kiel, Germany)

On Weighted Rectangle Packing with Large Resources - Aleksei V. Fishkin, Olga Gerber, Klaus Jansen (U. Kiel, Germany)

TCS7-Logic

Behavioural Equivalences for Dynamic Web Data - Sergio Maffeis, Philippa Gardner (Imperial College, UK)

Behavioural Theory for Mobile Ambient - Massimo Merro (U. Verona, Italy), Francesco Zappa Nardelli (U. Cambridge, UK)

Nested Commits for Mobile Calculi: Extending Join - Roberto Bruni, Herman C. Melgratti, Ugo Montanari (U. Pisa, Italy)

15h30-17h:

TCS8-Algorithms

An O(n log 2 n) Algorithm for the Optimal Sink Location Problem on Dynamic Tree Networks - Satoko Mamada, (Osaka U., Japan), Takeaki Uno (National Institute of Informatics, Japan), Kazuhisa Makino (Osaka U., Japan), Satoru Fujishige (Kyoto U., Japan)

Efficient Algorithms for Handling Molecular Weighted Sequences - Costas S. Iliopoulos (KCL, UK), Christos Makris, Yannis Panagis (CEID, U. Patras, Greece), Katerina Perdikuri, Evangelos Theodoridis (U. Patras, Greece), Athanasios Tsakalidis (RACTI, Greece)

TCS8-Logic

Dynamic and Local Typing for Mobile Ambients - Mario Coppo, Mariangiola Dezani, Elio Giovannetti (U. Torino, Italy), Rosario Pugliese (U. Florence, Italy)

PolyA: True Type Polymorphism for Mobile Ambients - Torben Amtoft (Kansas State U., USA), Henning Makholm, J. B. Wells, (Heriot-Watt U., UK)

ecovering Resources in the p -calculus - David Teller (LIP Lyon, France)

Thursday 26 August 2004

10h30-12h:

 TCS9

Invited talk: The tPI (tRNA Pairing Index), a Mathematical Measure of Repetition in a (Biological) Sequence - Gaston Gonnet (ETH Zurich, Switzerland)

TCS-Algorithms

Imperfectness of Data for STS-Based Physical Mapping - Hiro Ito, Kazuo Iwama, Takeyuki Tamura (Kyoto U., Japan)

13h30-15h:

TCS10

Invited talk: A Decidable Analysis of Security Protocols - Michael Rusinowitch (INRIA Lorraine, France)

TCS-Algorithms

Solving Packing Problem with Weaker Block Solvers - Hu Zhang (U. Kiel, Germany)

TCS-Logic

Ensuring Termination by Typability - Yuxin Deng (INRIA and U. Paris 7, France), Davide Sangiorgi (U. Bologna, Italy)

15h30-17h:

TCS11-Algorithms

Adaptive Sorting with AVL Trees - Amr A. Elmasry (Alexandria U., Egypt)

Precise Analysis of p -Calculus in Cubic Time - Livio Colussi, Gilberto Filè, A. Griggio (U. Padova, Italy)

TCS11-Logic

The Simply-typed Pure Pattern Type System Ensures Strong Normalization - Benjamin Wack (U. Henri Poincaré, France)

Termination in Modal Kleene Algebra - Jules Desharnais (U. Laval, Canada), Bernhard W. Möller, Georg Struth (U. Ausgburg, Germany)

Regular Tree Language Recognition with Static Information - Alain Frisch, (Ecole Normale Supérieure de Paris, France)