![[LOGOUNIBO]](./logobo.gif) |
ICALP '97 24th International Colloquium on Automata, Languages, and Programming Bologna, Italy, July 7-11, 1997 |
![[LOGOEATCS]](./eatcslogo.gif) |
|
ICALP '97 24th International Colloquium on Automata, Languages, and Programming Bologna, Italy, July 7-11, 1997 |
|
|
Sunday, July 6
Monday, July 7 Tuesday, July 8 Wednesday, July 9 Thursday, July 10 Friday, July 11 |
| Postscript version here! |
| Back to ICALP'97 |
| Sunday, July 6 | |
| 18:30-20:30 | Registration |
| 20:30-21:30 |
Reception |
| Monday, July 7 | ||
| 8:30 | Registration | |
| 9:15 | Welcome address | |
| 9:30 |
Invited Lecture: by Dana Scott (Carnegie Mellon, Pittsburgh) (title to be announced) |
|
| 10:30 | An abstract data type for real numbers, Pietro Di Gianantonio (Univ. Udine) | |
| 10:55 | Coffee Break | |
| A : Formal Languages I | B : Computability | |
| 11:15 | Enumerative sequences of leaves in rational trees, Frederique Bassino (Univ. de Marne-la-Vallée), Marie-Pierre Beal (Univ. Paris 7 and CNRS), Dominique Perrin (Univ. de Marne-la-Vallée) | Recursive Computational Depth, James Lathrop, Jack Lutz (Ames, Iowa) |
| 11:40 | A completion algorithm for codes with bounded synchronization delay, Veronique Bruyere (Univ. of Mons-Hainaut) | Some bounds on the computational power of Piecewise Constant Derivative systems, Olivier Bournez (ENS, Lyon) |
| 12:05 | The expressibility of languages and relations by word equations , Juhani Karhumaeki (Turku Univ.), Wojciech Plandowski (Turku Centre for Computer Science), Filippo Mignosi (Univ. Palermo) | Monadic simultaneous rigid E-unification and related problems , Yuri Gurevich (Univ. Michigan), Andrei Voronkov (Uppsala Univ.) |
| 12:30 | Finite loops recognize exactly the regular open languages, Martin Beaudry (Univ. Sherbrooke), Francois Lemieux, Denis Therien (McGill Univ., Montreal) | Computability on the Probability Measures on the Borel Sets of the Unit Interval , Klaus Weihrauch (Univ. Hagen) |
| 12:55 | Lunch | |
| 14:45 |
Invited Lecture: Randomization and the Correctness of Programs, Michael O. Rabin (Hebrew Univ. Jerusalem & Harvard Univ.) |
|
| 15:45 | Tilings and quasiperiodicity , Bruno Durand (LIP-ENS Lyon) | |
| 16:10 | Coffee break | |
| A : Computational complexity | B : Semantics I | |
| 16:30 | Results on Resource-Bounded Measure , Harry Buhrman (CWI), Stephen Fenner (Univ. of Southern Main), Lance Fortnow (CWI, Univ. of Chicago) | Game Theoretic Analysis of Call-by-value Computation, Kohei Honda, Nobuko Yoshida (Univ. Edinburgh) |
| 16:55 | Randomization and nondeterminism are incomparable for ordered read-once branching programs, Farid Ablayev (Kazan Univ.) | On modular properties of higher order extensional lambda calculi , Roberto Di Cosmo, Neil Ghani (ENS, Paris) |
| 17:20 | Checking Properties of Polynomials , Bruno Codenotti (IMC-CNR, Pisa), Funda Ergun (Cornell Univ.), Peter S. Gemmell (Sandia National Labs), S. Ravi Kumar (Cornell Univ.) | On Explicit Substitution and Names , Eike Ritter, Valeria de Paiva (Univ. Birmingham) |
| 17:45 | 18:10 |
Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP , Edith Hemaspaandra (Le Moyne College, Syracuse NY), Lane Hemaspaandra (Univ. Rochester), Joerg Rothe (Univ. Jena) | On the Dynamics of Sharing Graphs , Andrea Asperti, Cosimo Laneve (Univ. Bologna) |
| Tuesday, July 8 | ||
| 9:00 |
Invited Lecture: Graphical Calculi for Interaction , Robin Milner (Univ. Cambridge) |
|
| 10:00 | Bisimulation for probabilistic transition systems: a coalgebraic approach, Erik de Vink, Jan Rutten (CWI, Amsterdam) | |
| 10:25 | Coffee Break | |
| A : Algorithms I | B : Calculi for Concurrency I | |
| 10:45 | Minimizing Diameters of Dynamic Trees, Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup (Univ. Copenhagen) | The name discipline of uniform receptiveness , Davide Sangiorgi (INRIA, Sophia-Antipolis) |
| 11:10 | Improving Spanning Trees by Upgrading Nodes, Sven Krumke (Univ. Wurzburg), Madhav Marathe (Los Alamos National Lab.), Hartmut Noltemeier (Univ. Wurzburg), Ramamurthy Ravi (Carnegie Mellon), SS Ravi (SUNY at Albany), Ravi Sundaram (Delta Trading Co.), Hans-Christoph Wirth (Univ. Wurzburg) | On confluence in the pi-calculus, Anna Philippou, David Walker (Univ. Warwick) |
| 11:35 | Dynamic algorithms for graphs of bounded treewidth, Torben Hagerup (Max-Plank-Institut, Saarbrücken) | A proof theoretical approach to communication, Yuxi Fu (Shangai Jiao Tong Univ.) |
| 12:00 | Break | |
| A : Formal languages II | B : Calculi for Concurrency II | |
| 12:10 | Solving Trace Equations Using Lexicographical Normal Forms, Volker Diekert (Univ. Stuttgart), Yury Matiyasevich (Univ. St.Petersberg), Anne Muscholl (Univ. Stuttgart) | An Algebra-Based Method to Associate Rewards with EMPA Terms, Marco Bernardo (Univ. Bologna) |
| 12:35 | Star-free picture expressions are strictly weaker than first-order logic, Thomas Wilke (Univ. Kiel) | A Semantically Sound Actor Tranlsation, Ian Mason, Carolyn Talcott (Univ. Stanford) |
| 13:00 | Lunch | |
| A : Algorithms II | B : Logic and Verification | |
| 14:45 | Periodic and Non-periodic Min-Max Equations, Uwe Schwiegelshohn (Univ. Dortmund), Lothar Thiele (Swiss Federal Institute of Technology, Zurich) | Computation Paths Logic: An Expressive, yet Elementary, Process Logic, David Harel, Eli Singerman (The Weizmann Institute of Science, Rehovot) |
| 15:10 | Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP, Edson Caceres (Univ. Federal de Mato Grosso do Sul, Campo Grande), Frank Dehne (Carleton Univ., Ottawa), Afonso Ferreira (CNRS LIP-ENS, Lyon), Paola Flocchini (Univ. Montreal), Ingo Rieping (Univ. Paderborn), Alessandro Roncato (Univ. Venezia), Nicola Santoro (Carleton Univ,. Ottawa), Siang Song (Univ. Sao Paulo) | Model Checking the Full Modal Mu-Calculus for Infinite Sequential Processes, Olaf Burkart (Univ. of Edinburgh), Bernhard Steffen (Univ. Passau) |
| 15:35 | Upper bound on communication complexity of private information retrieval, Andris Ambainis (Univ. Latvia) | Symbolic Model Checking for Probabilistic Processes , Christel Baier (Univ. Mannheim), Ed Clarke, Vassili Hartonas-Garmhausen (Carnegie Mellon), Marta Kwiatkowska, Mark Ryan (Univ. Birmingham) |
| 16:00 | Coffee Break | |
| A : Analysis of algorithms | B : Process Equivalences | |
| 16:20 | On the concentration of the height of binary search trees, John Michael Robson (Univ. Talence) | Distributed Processes and Location Failures, James Riely, Matthew Hennessy (Univ. Sussex) |
| 16:45 | An improved master theorem for divide-and-conquer recurrences, Salvador Roura (Univ. Politecnica de Catalunya, Barcelona) | Basic Observables for Processes, Michele Boreale (Univ. Roma La Sapienza), Rocco De Nicola, Rosario Pugliese (Univ. Firenze) |
| 17:10 | Break | |
| 17:15 | 18:15 |
Panel: Funding Policies for Theoretical Computer Science with the participation of Giorgio Ausiello (Rome), Gilles Kahn (INRIA), G.Metakides (DG III-EU) and Ugo Montanari (Pisa). |
|
| Wednesday, July 9 | ||
| 9:00 |
Guided tour through the city of Bologna |
|
| 11:30 | Laurea Honoris Causa in Computer Science tributed by the University of Bologna to Robin Milner and Maurice Nivat | |
| 12:30 | Lunch | |
| 14:45 |
Invited Lecture: NP-completeness: A Retrospective, Christos Papadimitriou (UC, Berkeley) |
|
| 15:45 | Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs, Alexander Andreev (Univ. Moscow), Andrea Clementi (Univ. Roma La Sapienza), Jose Rolim (Univ. Geneva) | |
| 16:10 | Coffee Break | |
| A : Routing algorithms | B : Petri Nets and Process Theory | |
| 16:30 | Constrained Bipartite Edge Coloring with Applications to Wavelength Routing, Christos Kaklamanis (Univ. Patras), Pino Persiano (Univ. Salerno), Thomas Erlebach (TU Munchen), Klaus Jansen (Univ. Trier) | Efficiency of Asynchronous Systems and Read Arcs in Petri Nets, Walter Vogler (Univ. Augsburg) |
| 16:55 | Colouring Paths in Directed Symmetric Trees with Applications to WDM Routing, Luisa Gargano (Univ. Salerno), Pavol Hell (Simon Fraser Univ. Burnaby), Stephane Perennes (Delft Univ. of Technology) | Bisimulation equivalence is decidable for one-counter processes, Petr Jancar (Univ. Ostrava) |
| 17:20 | On-line Routing in All-Optical Networks, Yair Bartal (UC Berkeley and ICSI), Stefano Leonardi (Univ. Roma La Sapienza) | Symbolic Reachability Analysis of FIFO Channel Systems with Nonregular Sets of Configurations, Ahmed Bouajjani, Peter Habermehl (VERIMAG Gieres) |
| 17:45 | A Complete Characterization of the Path Layout Construction Problem for ATM Networks with Given Hop Count and Load, Tamar Eilam (Technion, Haifa), Michele Flammini (Univ. L'Aquila), Shmuel Zaks (Technion, Haifa) | Axiomatizations for the Perpetual Loop, Wan Fokkink (Univ. of Wales, Swansea) |
| 18:10 | Break | |
| 18:20 | Gödel Prize | |
| 18:45 | 19:30 |
EATCS assembly | |
| Thursday, July 10 | ||
| 9:00 |
Invited Lecture: The LEDA Platform of Combinatorial and Geometric Computing, Kurt Mehlhorn and Stefan Näher (Max-Planck-Institut, Saarbrücken) |
|
| 10:00 | Maintaining Minimum Spanning Trees in Dynamic Graphs, Monika Rauch Henzinger (DEC, Palo Alto), Valerie King (Univ. Victoria) | |
| 10:25 | Coffee Break | |
| A : Algorithms III | B : Rewriting | |
| 10:45 | Efficient Splitting and Merging Algorithms for Order Decomposable Problems, Roberto Grossi (Univ. Firenze), Giuseppe F. Italiano (Univ. Venezia) | The Word Matching Problem Is Undecidable For Finite Special String-Rewriting Systems That Are Confluent, Paliath Narendran (State University of New York at Albany), Friedrich Otto (Univ. Kassel) |
| 11:10 | Efficient Array Partitioning, by Sanjeev Khanna, S. Muthukrishnan (Bell Labs, Murray Hill), Steven Skiena (SUNY at Stony Brook) | The Geometry of Orthogonal Reduction Spaces, Zurab Khasidashvili (NTT Basic Research Labs, Wakamiya Morinosato Atsugi-shi Kanagawa), John Glauert (School of Information Systems, UEA, Norwich) |
| 11:35 | Constructive Linear Time Algorithms for Branchwidth, Hans Bodlaender, Dimitrios Thilikos (Utrecht Univ.) | The Theory of Vaccines, Massimo Marchiori (Univ. Padova) |
| 12:00 | Break | |
| A : Formal languages III | B : Cryptography | |
| 12:10 | On recognizable and rational formal power series in partially commuting variables, Manfred Droste (Univ. Dresden), Paul Gastin (Univ. Paris 7) | On Characterization of Escrow Encryption Schemes, Yair Frankel, Moti Yung (CertCo, New York) |
| 12:35 | On a conjecture of J. Shallit, by Julien Cassaigne (Univ. Marseille) | Randomness-Efficient Non-Interactive Zero-Knowledge, Alfredo De Santis (Univ. Salerno), Giovanni Di Crescenzo (UC, San Diego), Giuseppe Persiano (Univ. Salerno) |
| 13:00 | Lunch | |
| 14:45 | Invited Lecture: Chains and Superchains in Finite Automata, Dominique Perrin, Olivier Carton (Univ. de Marne-la-Vallée) | |
| 15:45 | The Equivalence Problem for Deterministic Pushdown Automata is Decidable, Geraud Senizergues (Univ. Bordeaux) | |
| 16:10 | Coffee Break | |
| A : Algorithms IV | B : Semantics II and Automata | |
| 16:30 | Approximation results for the optimum cost partition problem, Klaus Jansen (Univ. Trier) | Refining and Compressing Abstract Domains, Roberto Giacobazzi (Univ. Pisa), Francesco Ranzato (Univ. Padova) |
| 16:55 | The Minimum Color Sum of Bipartite Graphs, Amotz BarNoy (Tel Aviv University), Guy Kortsarz (The Open University of Israel, Tel Aviv) | Labelled Reductions, Runtime Errors and Operational Subsumption, Laurent Dami (Univ. Geneve) |
| 17:20 | A Primal-Dual Approach to Approximation of Node-Deletion Problems for Matroidal Properties, Toshihiro Fujito (Hiroshima Univ.) | A Complete and Efficiently Computable Topological Classification of D-dimensional Linear Cellular Automata over Z_m, Giovanni Manzini (Univ. Torino), Luciano Margara (Univ. Bologna) |
| 17:45 | Independent sets in asteroidal triple-free graphs, Hajo Broersma, Ton Kloks (Univ. of Twente, Enschede), Dieter Kratsch, Haiko Mueller (Univ. Jena) | Recognizability Equals Definability for Partial k-Paths, Valentine Kabanets (Univ. Toronto) |
| 18:10 | 18:40 |
Celebration of the Silver Jubilee of the EATCS. Towards a History of Automata: Why Were They Introduced? What Are They Good for? Keynote speaker: Maurice Nivat (Univ. Paris 7) | |
| 20:30 | Banquet | |
| Friday, July 11 | ||
| 9:00 |
Invited Lecture: Constraint Programming and the `Computation as Deduction' Paradigm, Krzysztof R. Apt (CWI, Amsterdam and University of Amsterdam) |
|
| 10:00 | Discrete-time control for rectangular hybrid automata, Thomas A. Henzinger (UC, Berkeley), Peter W. Kopke (Cornell Univ.) | |
| 10:25 | Coffee Break | |
| 10:45 |
Invited Lecture: Using DNA to Compute, Richard J. Lipton (Princeton Univ.) |
|
| 11:45 | Break | |
| A : Biocomputing | B : Logic Programming | |
| 12:00 | Molecular Computing, Bounded Nondeterminism, and Efficient Recursion, Richard Beigel, Bin Fu (Yale Univ. and Univ. of Maryland at College Park) | Termination of Constraint Logic Programs, Salvatore Ruggieri (Univ. Pisa) |
| 12:25 | 12:50 |
Constructing Big Trees from Short Sequences, Peter Erdos (Mathematical Institute of the Hungarian Academy of Sciences, Budapest), Michael Steel (Univ. Canterbury, Christchurch), Laszlo Szekely (Univ. South Carolina, Columbia), Tandy Warnow (Univ. of Pennsylvania, Philadelphia) | The expressive power of unique total stable model semantics, Francesco Buccafurri, Sergio Greco, Domenico Sacca' (Univ. Calabria, Rende) |