From owner-theorynt@LISTSERV.NODAK.EDU Wed Apr 23 14:13:22 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id OAA00032 for ; Wed, 23 Apr 1997 14:13:21 -0700 (PDT) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by CS.Stanford.EDU (8.8.4/8.8.4) with ESMTP id OAA13609; Wed, 23 Apr 1997 14:02:29 -0700 (PDT) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.CDC33B30@listserv.nodak.edu>; Wed, 23 Apr 1997 16:02:54 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 786378 for THEORYNT@LISTSERV.NODAK.EDU; Wed, 23 Apr 1997 16:02:49 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.CA3DE500@listserv.nodak.edu>; Wed, 23 Apr 1997 16:02:48 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 786367 for THEORY-A@LISTSERV.NODAK.EDU; Wed, 23 Apr 1997 16:02:47 -0500 Received: from pollux.usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.C7704610@listserv.nodak.edu>; Wed, 23 Apr 1997 16:02:44 -0500 Received: (from ierardi@localhost) by pollux.usc.edu (8.8.4/8.8.4/usc) id OAA16729 for theory-a@listserv.nodak.edu; Wed, 23 Apr 1997 14:02:41 -0700 (PDT) Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: <199704181347.AA05166@ciociosan.cs.unibo.it> Date: Wed, 23 Apr 1997 14:02:39 PDT Reply-To: Theory-A - TheoryNet World-Wide Events , Nadia Busi Sender: TheoryNet List From: Nadia Busi Subject: [Theory-A] ICALP'97 - preliminary programme Comments: To: THEORY-A@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU X-Mozilla-Status: 0001 Content-Length: 20289 ******************************************************* * * * ICALP '97 * * ========= * * 24th International Colloquium on Automata, * * Languages, and Programming * * * * Silver Jubilee of EATCS * * * * Bologna, Italy, July 7th - 11th, 1997 * * * ******************************************************* PRELIMINARY PROGRAMME ******************************************************* This announcement and more information about the conference is available per www under http://www.cs.unibo.it/icalp97/ or by sending e-mail to icalp97@cs.unibo.it Please address inquiries, registration form and hotel reservation form to the Conference Office: Italiana & Co. - ICALP'97 Via Altabella 3 I-40126 BOLOGNA (Italy) Phone: + 39 51 228716 Fax: + 39 51 222881 Email: italiana@bo.nettuno.it ------------------------------------------------------------------------------- GENERAL INFORMATION ^^^^^^^^^^^^^^^^^^^ The 24th annual meeting of the European Association for Theoretical Computer Science (EATCS) will take place in Bologna, Italy, July 7-11 1997. ICALP '97 comes in conjunction with the 25th anniversary of the foundation of EATCS. To celebrate the SILVER JUBILEE, this edition of ICALP includes several new events: - Celebration of EATCS and of its founders (keynote speaker M. Nivat - Paris) - Invited Lectures on major advances in theoretical computer science since EATCS has been established: R. Milner (Cambridge) M.O. Rabin (Jerusalem and Harvard) C. Papadimitriou (Berkeley) D.S. Scott (Pittsburgh) - Invited Lectures on the state of the art and new promising trends: K.R. Apt (Amsterdam) K. Mehlhorn (Saarbruecken) R.J. Lipton (Princeton) D. Perrin (Marne-la-Vallee) - A panel on 'Funding Policies for Theoretical Computer Science' with representatives from major research agencies and from the European Community. - A number of Satellite Workshops, listed below, on theory and applications. ICALP SATELLITE WORKSHOPS ^^^^^^^^^^^^^^^^^^^^^^^^^ - Workshop on New Trends in Semantics - Bologna (4-5 July) Organizers: A.Asperti (Bologna), E.Moggi (Genova) and G.Rosolini (Genova). Invited Speakers: S.Abramski (Edinburgh), V.Danos (Paris), A.Joyal (Montreal), D.Sangiorgi (Sophia-Antipolis). http://www.disi.unige.it/conferences/new-trends97/ - Second International ERCIM Workshop on Formal Methods in Industrial Critical Systems - Cesena (4-5 July) - Organizers: S. Gnesi, D. Latella, L. Simoncini (Pisa). Invited Speakers: E.Brinksma (Twente), U.Herzog (Erlangen), R.Mazzeo (Sasib Railways), G.Mongardi (Ansaldo Trasporti). http://fdt.cnuce.cnr.it/~latella/FMICS/WS/Cesena97/workshop.html - Second International Workshop on Advanced Intelligent Networks (AIN'97) - Cesena (4-5 July) - Organizers: T. Margaria and B. Steffen (Passau). Invited Speakers: P.Zave (AT&T), M.Decina (Milano), A.Limongiello (Telecom Italia). http://brahms.fmi.uni-passau.de/bs/organization/ain97/ain97.html - Workshop on Approximation and Randomized Techniques in Computer Science (Random) - Bologna (11-12 July) - Organizers: J. Rolim (Geneva) and A. Clementi (Rome). Invited Speakers: S.Arora (Princeton), P.Crescenzi (Rome), R.Impagliazzo (San Diego), M.Karpinski (Bonn). http://cuiwww.unige.ch/~random97 - Workshop on Recent Developments in Formal Languages - Bologna (11-12 July) Organizer: S.Varricchio (L'Aquila), G.Pirillo (Firenze). Invited Speaker: D. Perrin (Marne-la-Vallee). http://univaq.it/~varricch/workshop.html - Workshop on Algorithmic Aspects of Communication - Bologna (11-12 July) - Organizers: M. Bonuccelli (Pisa) and A. Marchetti-Spaccamela (Rome). http://www.di.unipi.it/~bonucce/AlAsCo.html - Second International Workshop on Verification of Infinite State Systems (Infinity) - Bologna (11-12 July) - Organizer: F.Moller (Uppsala). http://www.csd.uu.se/~fm/infinity97cfp.html ------------------------------------------------------------------------- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % CONFERENCE PROGRAMME % % % % ICALP '97 % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Sunday, July 6 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Registration: Aula Prodi, 18:30-20:30 Reception: Aula Prodi, 20:30-21:30 Monday, July 7 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Registration: Aula Absidale, 8:30- 9:15 Welcome address: 9:15- 9:30 9:30 Invited Lecture: Dana Scott (CMU, Pittsburgh) (title to be announced) 10:30 An abstract data type for real numbers P. Di Gianantonio Coffee Break: 10:55 - 11:15 ------------------------------------------------------------------------- 11:15 - 12:55 Parallel Sessions A : Formal Languages I B : Computability ------------------------------------------------------------------------- Enumerative sequences of leaves Recursive Computational Depth in rational trees J.Lathrop, J. Lutz F.Bassino, M.-P. Beal, D. Perrin A completion algorithm for codes Some bounds on the computational with bounded synchronization delay power of Piecewise Constant V. Bruyere Derivative systems O. Bournez The expressibility of languages Monadic simultaneous rigid and relations by word equations E-unification and related problems J.Karhumaeki, W.Plandowski, Y.Gurevich, A.Voronkov F.Mignosi Finite loops recognize exactly Computability on the Probability the regular open languages Measures on the Borel Sets of the M.Beaudry, F.Lemieux, D.Therien Unit Interval K.Weihrauch ------------------------------------------------------------------------- Lunch: 12:55 - 14:45 14:45 Invited Lecture: Michael O. Rabin (Hebrew U. of Jerusalem & Harvard U.) Randomization and the Correctness of Programs 15:45 Tilings and quasiperiodicity B. Durand Coffee Break: 16:10 - 16:30 ------------------------------------------------------------------------- 16:30 - 18:10 Parallel Sessions A : Computational Complexity B : Semantics I ------------------------------------------------------------------------- Results on Resource-Bounded Measure Game Theoretic Analysis of H.Buhrman, S.Fenner, L.Fortnow Call-by-value Computation K.Honda, N.Yoshida Randomization and nondeterminism On modular properties of higher are incomparable for ordered order extensional lambda calculi read-once branching programs R. Di Cosmo, N. Ghani F. Ablayev Checking Properties of Polynomials On Explicit Substitution and Names B.Codenotti, F.Ergun, P.S. Gemmell, E. Ritter, V. de Paiva S.Ravi Kumar Exact Analysis of Dodgson Elections: On the Dynamics of Sharing Graphs Lewis Carroll's 1876 Voting System A. Asperti, C. Laneve is Complete for Parallel Access to NP E.Hemaspaandra, L.Hemaspaandra, J.Rothe ------------------------------------------------------------------------- Tuesday, July 8 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 9:00 Invited Lecture: Robin Milner (U. Cambridge) Graphical Calculi for Interaction 10:00 Bisimulation for probabilistic transition systems: A coalgebraic approach E. de Vink, J. Rutten Coffee Break: 10:25 - 10:45 ------------------------------------------------------------------------- 10:45 - 12:00 Parallel Sessions A : Algorithms I B : Calculi for Concurrency I ------------------------------------------------------------------------- Minimizing Diameters of Dynamic The name discipline of uniform Trees receptiveness S.Alstrup,J.Holm,K.de Lichtenberg, D. Sangiorgi M.Thorup Improving Spanning Trees by On confluence in the pi-calculus Upgrading Nodes A. Philippou, D. Walker S.Krumke, M.Marathe, H. Noltemeier, R.Ravi,SS Ravi, R.Sundaram, H.-C. Wirth Dynamic algorithms for graphs of A proof theoretical approach to bounded treewidth communication T. Hagerup Y. Fu Break: 12:00 - 12:10 ------------------------------------------------------------------------- 12:10 - 13:00 Parallel Sessions A : Formal Languages II B : Calculi for Concurrency II ------------------------------------------------------------------------- Solving Trace Equations Using An Algebra-Based Method to Lexicographical Normal Forms Associate Rewards with EMPA Terms V.Diekert, Y.Matiyasevich, M. Bernardo A. Muscholl Star-free picture expressions are A Semantically Sound Actor strictly weaker than 1st-order logic Translation T. Wilke I. Mason, C. Talcott ------------------------------------------------------------------------- Lunch: 13:00 - 14:45 ------------------------------------------------------------------------- 14:45 - 16:00 Parallel Sessions A : Algorithms II B : Logic and Verification ------------------------------------------------------------------------- Periodic and Non-periodic Min-Max Computation Paths Logic: An Equations Expressive, yet Elementary, U.Schwiegelshohn, L.Thiele Process Logic D.Harel, E.Singerman Efficient Parallel Graph Algorithms Model Checking the Full Modal For Coarse Grained Multicomputers Mu-Calculus for Infinite Sequential and BSP Processes E.Caceres, F.Dehne, A.Ferreira, O.Burkart, B.Steffen P.Flocchini, I.Rieping, A.Roncato, N.Santoro, S.Song Upper bound on communication Symbolic Model Checking for complexity of private information Probabilistic Processes retrieval C.Baier, M.Kwiatkowska, M.Ryan, A.Ambainis E.Clarke, V.Hartonas-Garmhausen ------------------------------------------------------------------------- Coffee Break: 16:00 - 16:20 ------------------------------------------------------------------------- 16:20 - 17:10 Parallel Sessions A : Analysis of Algorithms B : Process Equivalences ------------------------------------------------------------------------- On the concentration of the height Distributed Processes and Location of binary search trees Failures J.M. Robson J.Riely, M.Hennessy An improved master theorem for Basic Observables for Processes divide-and-conquer recurrences M.Boreale, R.De Nicola, R.Pugliese S. Roura ------------------------------------------------------------------------- Break: 17:10 - 17:15 17:15 - 18:15 Panel: Funding Policies for Theoretical Computer Science (with the participation of G.Metakides, DG III-EU) ------------------------------------------------------------------------- Wednesday, July 9 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 9:00 - 11:30 Excursion: Guided tour to the city of Bologna 11:30 - 12:30 Laurea Honoris Causa in Computer Science tributed to Robin Milner and Maurice Nivat by the University of Bologna Lunch: 12:30 - 14:45 14:45 - 15:45 Invited Lecture: Christos Papadimitriou (Berkeley) NP-completeness: A Retrospective 15:45 - 16:10 Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs A. Andreev, A. Clementi, J. Rolim Coffee Break: 16:10 - 16:30 ------------------------------------------------------------------------- 16:30 - 18:10 Parallel Sessions A : Routing Algorithms B : Petri Nets and Process Theory ------------------------------------------------------------------------- Constrained Bipartite Edge Coloring Efficiency of Asynchronous Systems with Applications to Wavelength and Read Arcs in Petri Nets Routing W.Vogler C.Kaklamanis,G.Persiano,T.Erlebach, K.Jansen Colouring Paths in Directed Bisimulation equivalence is Symmetric Trees with Applications decidable for one-counter processes to WDM Routing P.Jancar L.Gargano, P.Hell, S.Perennes On-line Routing in All-Optical Symbolic Reachability Analysis of Networks FIFO Channel Systems with Nonregular Y.Bartal, S.Leonardi Sets of Configurations A.Bouajjani, P.Habermehl A Complete Characterization of the Axiomatizations for the Perpetual Path Layout Construction Problem for Loop ATM Networks with Given Hop Count W.Fokkink and Load T.Eilam, M.Flammini, S.Zaks ------------------------------------------------------------------------- Break: 18:10 - 18:20 18:20 - 18:45 Goedel Prize 18:45 - 19:30 EATCS General Assembly ------------------------------------------------------------------------- Thursday, July 10 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 9:00 Invited Lecture: Kurt Mehlhorn and Stefan Naeher (Max-Planck Institut, Saarbruecken) The LEDA Platform of Combinatorial and Geometric Computing 10:00 Maintaining Minimum Spanning Trees in Dynamic Graphs M. Rauch Henzinger, V. King Coffee Break: 10:25 - 10:45 ------------------------------------------------------------------------- 10:45 - 12:00 Parallel Sessions A : Algorithms III B : Rewriting ------------------------------------------------------------------------- Efficient Splitting and Merging The Word Matching Problem is Algorithms for Order Decomposable Undecidable for Finite Special Problems String-Rewriting Systems that R.Grossi, G.F.Italiano are Confluent P.Narendran, F.Otto Efficient Array Partitioning The Geometry of Orthogonal S.Khanna, S.Muthukrishnan, S.Skiena Reduction Spaces Z.Khasidashvili, J.Glauert Constructive Linear Time Algorithms The Theory of Vaccines for Branchwidth M.Marchiori H.Bodlaender, D.Thilikos Break: 12:00 - 12:10 ------------------------------------------------------------------------- 12:10 - 13:00 Parallel Sessions A : Formal Languages III B : Cryptography ------------------------------------------------------------------------- On recognizable and rational formal On Characterization of Escrow power series in partially commuting Encryption Schemes variables Y.Frankel, M.Yung M.Droste, P.Gastin On a conjecture of J. Shallit Randomness-Efficient Non- J.Cassaigne Interactive Zero-Knowledge A.De Santis, G.Di Crescenzo, G.Persiano ------------------------------------------------------------------------- Lunch: 13:00 - 14:45 14:45 Invited Lecture: Dominique Perrin and Olivier Carton (U. de Marne-la-Vallee) Chains and Superchains in Finite Automata 15:45 The Equivalence Problem for Deterministic Pushdown Automata is Decidable G. Senizergues Coffee Break: 16:10 - 16:30 ------------------------------------------------------------------------- 16:30 - 18:10 Parallel Sessions A : Algorithms IV B : Semantics II and Automata ------------------------------------------------------------------------- Approximation results for the Refining and Compressing Abstract optimum cost partition problem Domains K.Jansen R.Giacobazzi, F.Ranzato The Minimum Color Sum of Bipartite Labelled Reductions, Runtime Graphs Errors, and Operational Subsumption A.BarNoy, G.Kortsarz L.Dami A Primal-Dual Approach to A Complete and Efficiently Approximation of Node-Deletion Computable Topological Problems for Matroidal Properties Classification of D-dimensional T.Fujito Linear Cellular Automata over Z_m G.Manzini, L.Margara Independent sets in asteroidal Recognizability Equals Definability triple-free graphs for Partial k-Paths H.Broersma, T.Kloks, D.Kratsch, V. Kabanets H.Mueller ------------------------------------------------------------------------- 18:10 - 18:40 Celebration of the Silver Jubilee of the EATCS Keynote speaker: Maurice Nivat (Paris 7) Towards a History of Automata: Why Were They Introduced? What Are They Good for? 20:30 Banquet ------------------------------------------------------------------------- Friday, July 11 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 9:00 Invited Lecture: Krzystof R. Apt (CWI, Amsterdam) Constraint Programming and the 'Computation as Deduction' Paradigm 10:00 Discrete-time control for rectangular hybrid automata Thomas A. Henzinger, Peter W. Kopke Coffee Break: 10:25 - 10:45 10:45 Invited Lecture: Richard J. Lipton (Princeton Univ.) Using DNA to Compute Break: 11:45 - 12:00 ------------------------------------------------------------------------- 12:00 - 12:50 Parallel Sessions A : Biocomputing B : Logic Programming ------------------------------------------------------------------------- Molecular Computing, Bounded Termination of Constraint Logic Nondeterminism, and Efficient Programs Recursion R.Beigel, B.Fu S.Ruggieri Constructing Big Trees from Short The expressive power of unique Sequences total stable model semantics P.Erdos, M.Steel, L.Szekely, F.Buccafurri, S.Greco, D.Sacca' T.Warnow End of ICALP'97 ------------------------------------------------------------------------- RELATED CONFERENCES ^^^^^^^^^^^^^^^^^^^ ICALP'97 will be preceded by LICS'97 and CONCUR'97, which will be held in Warsaw, Poland, the week before. For more details see http://www.bell-labs.com/topic/conferences/lics/ http://www.ipipan.waw.pl/conferences/concur97/ Warsaw is easily connected to Bologna via Vienna, Frankfurt, Munich, Rome, Paris, Bruxelles, Amsterdam, London and others. Further information for participants will be sent in a next mail and may be found per www.