> Congress / Advance Programme / Conferences / TCS

Tc1 - Foundations of Computer Science

In recent years, IT applications have evolved in innovative ways. Highly distributed networks have now become a common platform for large-scale distributed programming, high bandwidth communication is cheap and widespread, and most of our computers are equipped with processors enabling us to perform a multitude of tasks. In addition, mobile computing (referring specifically to wireless devices and, more broadly, to dynamically reconfigurable systems) has made it possible to exploit interaction in novel ways.

To harness the flexibility and power of these rapidly evolving, interactive systems, we need to come up with radically new foundational ideas and principles. Now is the time to develop the theoretical foundations required to design these systems and to cope with the many complex issues involved in their construction. Now is also the time to develop effective principles for building and analyzing such systems.

Our computational goal is to discover techniques, models and algorithms allowing us to construct systems that are flexible, dependable, secure, robust and efficient. In terms of programming, it is interesting to note that Internet applications differ substantially from traditional applications in the following areas: scalability, connectivity, heterogeneity, and autonomy. Hence, new programming paradigms (thin client and application servers, peer-to-peer collaboration, code-on-demand, mobile agents) have been proposed for Internet applications. This scenario is appealing from a scientific point of view, since most of the open problems and several of the concepts requiring fine-tuning fall within the domain of computer science research. More specifically, there is a need for models, languages and logics that are distributed, interactive and concurrent; open and reconfigurable; higher order and typed; equipped with abstract compositional semantics; and efficiently verifiable.

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

. Track 1 ( TCS-Algorithms ) focuses on Algorithms, Complexity and Models of Computation, while
. Track 2 ( TCS-Logic ) focuses on Logic, Semantics, Specification and Verification.

The IFIP TCS 2004 conference is sponsored by IFIP TC1 on Foundations of Computer Science in cooperation with SIGACT and EATCS.

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. Muenchen, Germany), Sebastian Nanz (Yale U., USA)

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

ew 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 (Universität 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)

Tailoring Recursion to Characterize Non-Deterministic Complexity Classes Over Arbitrary Structures - Olivier Bournez (INRIA Lorraine, France), Paulin Jacobé de Naurois, Jean-Yves Marion (LORIA, France), Felipe Cucker, (City U., Hong-Kong)

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, 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

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

Asymptotic Behaviors of Type-2 Algorithms and Induced Baire Topologies - Chung-Chih Li (Lamar U., Beaumont Texas USA)

Wednesday 25 August 2004

10h30-12h:

TCS6

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, London, UK)

A behavioural theory for Mobile Ambients from Systems to Processes - 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)

Recovering 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)

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)

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

TCS11-Logic

The Simply-typed Pure Pattern Type System Ensures Strong Normalization - Benjamin Wack (U. Henri Poincaré, Nancy, 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, Paris, France)