(Message inbox:62) Return-Path: Received: from CS.CMU.EDU by MISSING.LINK.CS.CMU.EDU id aa11611; 14 Feb 96 15:59 EST Received: from hearn.nic.surfnet.nl by CS.CMU.EDU id aa13637; 14 Feb 96 15:56:28 EST Received: from HEARN.NIC.SURFNET.NL by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with BSMTP id 6141; Wed, 14 Feb 96 21:50:13 +0100 Received: from NIC.SURFNET.NL (NJE origin LISTSERV@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2a/1.8a) with BSMTP id 9138; Wed, 14 Feb 1996 21:49:55 +0100 Received: from NIC.SURFNET.NL by NIC.SURFNET.NL (LISTSERV release 1.8b) with NJE id 2369 for DMA-LIST@NIC.SURFNET.NL; Wed, 14 Feb 1996 21:49:38 +0100 Received: from HEARN (NJE origin SMTP@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2a/1.8a) with BSMTP id 9122; Wed, 14 Feb 1996 21:49:34 +0100 Received: from utmfu0.math.utwente.nl by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with TCP; Wed, 14 Feb 96 21:49:30 +0100 Received: by utmfu0.math.utwente.nl ($Revision: 1.36.108.11 $/16.2) id AA220480923; Wed, 14 Feb 1996 21:48:43 +0100 Full-Name: DMANET Mailer: Elm [revision: 66.36.1.1] Approved-By: DMANET Message-ID: <199602142048.AA220480923@utmfu0.math.utwente.nl> Date: Wed, 14 Feb 1996 21:48:41 MET Reply-To: icalp96@uni-paderborn.de Sender: DMANET From: DMANET Subject: ICALP 96: Program To: Multiple recipients of list DMA-LIST =============================================================================== FIRST CALL FOR PARTICIPATION AND PROGRAM 23rd INTERNATIONAL COLLOQUIUM ON AUTOMATA, LANGUAGES AND PROGRAMMING ICALP'96 JULY 8 -- JULY 12, 1996 Paderborn, Germany ******************************************************************************* ******************************************************************************* This and further information is available from the ICALP'96 www-server ************** http://www.uni-paderborn.de/~icalp96/ *********************** ******************************************************************************* ******************************************************************************* PROGRAM COMMITTEE: =============================================================================== J. Balcazar, Barcelona B. Monien, Paderborn (Co-Chairman) J. Berstel, Paris J. Munro, Waterloo R. Freivalds, Riga L. Pacholski, Wroclaw Z. Galil, New York A. Pnueli, Rehovot J. Karhumaki, Turku A. Rosenberg, Amherst R. Kemp, Frankfurt D. Sanella, Edinburgh W. Maass, Graz S. Skyum, Aarhus A. Marchetti-Spaccamela, Roma P. Spirakis, Patras J. Matousek, Praha P. Vitanyi, Amsterdam F. Meyer auf der Heide, Paderborn (Co-Chairman) INVITED SPEAKERS: =============================================================================== -- H. Ganzinger, Saarbruecken -- M. Latteux, Lille and V. Bruyere, Mons -- M. Rabin, Jerusalem and Cambridge -- A. Ranade, Berkeley and Bombay -- A. Razborov, Moscow PROGRAM: =============================================================================== MONDAY, JULY 8, 1996 ******************** 8:45 Opening 9:00 Invited Lecture: "Saturation-Based Theorem Proving" H. Ganzinger, (Saarbruecken, Germany) SESSION 1 -- PROCESS THEORY I Chair: Burkhard Monien (Paderborn, Germany) 9:50 "Algebraic Characterizations of Decorated Trace Equivalences over Tree-like Structures" X. J. Chen, R. De Nicola (Roma, Italy) 10:15 "Fast Asynchronous Systems in Dense Time" L. Jenner, W. Vogler (Augsburg, Germany) 10:40 BREAK SESSION 2 -- FAIRNESS, DOMINATION, AND THE MU-CALCULUS Chair: Amir Pnueli (Rehovot, Israel) 11:00 "A Hierarchy Theorem for the MU-Calculus" G. Lenzi (Pisa, Italy) 11:25 "An Effective Tableau System for the Linear Time MU-Calculus" J. Bradfield (Edinburgh, United Kingdom), J. Esparza, A. Mader (Muenchen, Germany) 11:50 "Characterizing Fairness Implementability for Multiparty Interaction" Y.-J. Joung (Taipei, Taiwan) 12:15 "Termination of Context-Sensitive Rewriting by Rewriting" S. Lucas (Valencia, Spain) 12:40 LUNCH SESSION 3 -- LOGIC AND ALGEBRA Chair: Leszek Pacholski (Wroclaw, Poland) 14:15 "A Complete Gentzen-style Axiomatization for Set Constraints" A. Cheng, D. Kozen (Cornell, USA) 14:40 "Fatal Errors in Conditional Expressions" M. Billaud (Bordeaux, France) 15:05 "Different Types of Arrow Between Logical Frameworks" T. Mossakowski (Bremen, Germany) 15:30 "Effective Models of Polymorphism, Subtyping and Recursion" J. Mitchell (Stanford, USA), R. Viswanathan (Cambridge, United Kingdom) 15:55 BREAK SESSION 4 -- LANGUAGES AND PROCESSES Chair: Don Sanella (Edinburgh, United Kingdom) 16:20 "Regularity of All Context-free Processes is Decidable" D. J. B. Bosscher, W. O. D. Griffioen (Amsterdam, The Netherlands) 16:45 "On Infinite Transition Graphs Having a Decidable Monadic Theory" D. Caucal (Rennes, France) 17:10 "Semi-groups Acting on Context-free Graphs" G. Senizergues (Bordeaux, France) 17:35 "Hard Sets Method and Semilinear Reservoir Method with Applications" L. P. Lisovik (Kiev, Ukraine) 18:00 END OF SESSION 19:00 Guided Walk through Paderborn TUESDAY, JULY 9, 1996 ********************* 9:00 Invited Lecture: "Bandwidth-efficient Parallel Computation" Abhiram Ranade (Berkeley, USA, and Bombay, India) SESSION 5 -- ALGEBRAIC COMPLEXITY Chair: Rainer Kemp (Frankfurt, Germany) 9:50 "Random Polynomials and Polynomial Factorization" Ph. Flajolet, X. Gourdon (LeChesnay, France) D. Panario (Toronto, Canada) 10:15 "Optimal Groebner Base Algorithms for Binomial Ideals" U. Koppenhagen and E. W. Mayr (Muenchen, Germany) 10:40 BREAK SESSION 6 -- GRAPH ALGORITHMS Chair: Sven Skyum (Aarhus, Denmark) 11:00 "Minimum Fill-in of Circle and Circular-arc Graphs" T. Kloks (Eindhoven, The Netherlands), D. Kratsch (Jena, Germany), C. K. Wong (Hong Kong) 11:25 "Practical Approximation Schemes for Maximum Induced-Subgraph Problems on K_{3,3}-free or K_5-free Graphs" Z. Z. Chen (Tokyo, Japan) 11:50 "Searching a Fixed Graph" E. Koutsoupias (Los Angeles, USA), Ch. Papadimitriou (San Diego, USA), M. Yannakakis (Murray Hill, USA) 12:15 "Improved Sampling with Applications to Dynamic Graph Algorithms" M. Rauch Henzinger (Cornell, USA), M. Thorup (Copenhagen, Denmark) 12:40 LUNCH SESSION 7 -- AUTOMATA Chair: Juhani Karhumaki (Turku, Finland) 14:15 "The Expressive Power of Existential First Order Sentences of Buechi's Sequential Calculus" J.-E. Pin (Paris, France) 14:40 "Fixpoints for Rabin Tree Automata Make Complementation Easy" R. Kaivola (Edinburgh, United Kingdom) 15:05 "New Upper Bounds to the Limitedness of Distance Automata" K. Hashiguchi (Okayama, Japan) 15:30 "Recognizing Regular Expressions by Means of Dataflow Networks" P. Raymond (Montbonnot-St. Martin, France) 15:55 BREAK SESSION 8 -- COMPLEXITY THEORY Chair: Paul Vitanyi (Amsterdam, The Netherlands) 16:20 "On the Power of Randomized Branching Programs" F. Ablayev (Kazan, Russia), M. Karpinski (Bonn, Germany) 16:45 "Hitting sets Derandomize BPP" A. E. Andreev (Moscow, Russia), A. E. Clementi (Roma, Italy), J.D.P. Rolim (Geneva, Switzerland) 17:10 "On Type-2 Probabilistic Quantifiers" R. Book (Santa Barbara, USA), H. Vollmer, K. Wagner (Wuerzburg, Germany) 17:35 "Speeding-up Single-Tape Nondeterministic Computations by Single Alternation, with Separation Results" J. Wiedermann (Prague, Czech Republic) 18:00 END OF SESSION 18:15 General Assembly of the EATCS WEDNESDAY, JULY 10, 1996 ************************ 9:00 Invited Lecture: "Variable-length Maximal Codes" Michel Latteux (Lille, France), Veronique Bruyere (Mons, Belgium) SESSION 9 -- COMBINATORICS ON WORDS Chair: Jean Berstel (Paris, France) 9:50 "On \omega-Generators and Codes" S. Julia (Sophia Antipolis, France) 10:15 "On Standard Sturmian Morphisms" A. de Luca (Roma, Italy) 10:40 BREAK SESSION 10 -- ALGORTIHMS I Chair: Ian Munro (Waterloo, Canada) 11:00 "Visual Cryptography for General Access Structures" G. Ateniese, C. Blundo, A. De Santis (Salerno, Italy), D. R. Stinson (Lincoln, USA) 11:25 "On Capital Investment" Y. Azar (Tel Aviv, Israel), Y. Bartal (Berkeley, USA), E. Feuerstein (Buenos Aires, Argentina), A. Fiat (Tel Aviv, Israel), St. Leonardi (Roma, Italy), A. Rosen (Toronto, Canada) 11:50 LUNCH 13:00 EXCURSION TO CORVEY CASTLE Visit of the Castle Library at the Principality of Corvey 19:30 CONFERENCE DINNER at the Buergerhaus "Im Schlosspark", Schloss Neuhaus THURSDAY, JULY 11, 1996 *********************** 9:00 Invited Lecture: "Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetics" Alexander Razborov (Moscow, Russia) SESSION 11 -- LOWER BOUNDS Chair: Rusins Freivalds (Riga, Latvia) 9:50 "Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication" P. B. Miltersen (Toronto, Canada) 10:15 "Lower Bounds for Row Minima Searching" P. G. Bradford, K. Reinert (Saarbruecken, Germany) 10:40 BREAK SESSION 12 -- PROCESS THEORY II Chair: Harald Ganzinger (Saarbruecken, Germany) 11:00 "On the Complexity of Relational Problems for Finite State Processes" S.K. Shukla, H.B. Hunt, D.J. Rosenkrantz, R.E. Stearns (Albany, USA) 11:25 "Deciding Finiteness of Petri Nets Up To Bisimulation" P. Jancar (Ostrava, Czech Republic), J. Esparza (Muenchen, Germany) 11:50 "Mobile Processes with a Distributed Environment" C. Bodei, P. Degano, C. Priami (Pisa, Italy) 12:15 "The Meaning of Negative Premises in Transition System Specifications II" R.J. van Glabbeek (Stanford, USA) 12:40 LUNCH SESSION 13 -- DATA STRUCTURES Chair: Paul Spirakis (Patras, Greece) 14:15 "Average Case Analyses of List Update Algorithms, with Applications to Data Compression" S. Albers (Saarbruecken, Germany), M. Mitzenmacher (Berkeley, USA) 14:40 "Self-organizing Data Structures with Dependent Accesses" F. Schulz, E. Schoemer (Saarbruecken, Germany) 15:05 "Lopsided Trees: Analyses, Algorithms and Applications" V. S.-N. Choi, M. Golin (Hong Kong) 15:30 "Optimal Logarithmic Time Randomized Suffix Tree Construction" M. Farach (Rutgers, USA), S. Muthukrishnan (Warwick, United Kingdom) 15:55 BREAK SESSION 14 -- PARALLEL ALGORITHMS Chair: Arnold Rosenberg (Amherst, USA) 16:20 "Improved Parallel Approximation of a Class of Integer Programming Programming Problems" N. Alon (Tel Aviv, Israel), A. Srinivasan (Singapore) 16:45 "Efficient Collective Communication in Optical Networks" J.C. Bermond, S. Perennes (Sophia Antipolis, France), L. Gargano, A.A. Rescigno, U. Vaccaro (Salerno, Italy) 17:10 "Shared-Memory Simulations on a Faulty-Memory DMM" B. S. Chlebus (Warszawa, Poland), A. Gambin (Dortmund, Germany), P. Indyk (Stanford, USA) 17:35 "Fast Deterministic Backtrack Search" K. T. Herley (Cork, Ireland), A. Pietracaprina, G. Pucci (Padova, Italy) 18:00 END OF SESSION 19:00 Reception by the Mayor of Paderborn FRIDAY, JULY 12, 1996 *********************** 9:00 Invited Lecture: "Parallel Computing, From Theory to Practice" Michael Rabin (Jerusalem, Israel and Harvard, USA) SESSION 15 -- DISTRIBUTED SYSTEMS Chair: Friedhelm Meyer auf der Heide (Paderborn, Germany) 9:50 "Agent Rendezvous: A Dynamic Symmetry-Breaking Problem" X. Yu (Columbia, USA), M. Yung (Watson Research Center, USA) 10:15 "Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler" Y. Aumann, M.A. Bender (Harvard, USA) 10:40 BREAK SESSION 16 -- ALGORITHMS II Chair: Alberto Marchetti-Spaccamela (Roma, Italy) 11:00 "A Formal Framework for Evaluating Heuristic Programs" L. Cowen (Baltimore, USA), J. Feigenbaum (Murray Hill, USA), S. Kannan (Philadelphia, USA) 11:25 "Improved Scheduling Algorithms for Minsum Criteria" S. Chakrabarti (Berkeley, USA), C. Phillips (Albuquerque, USA), A. Schulz (Berlin, Germany), D.B. Shmoys (Cornell, USA), C. Stein (Hanover, USA), J. Wein (Brooklyn, USA) 11:50 "On the Complexity of String Folding" M. Paterson (Warwick, United Kingdom), T. Przytycka (Odense, Denmark) 12:15 "A Polynomial-Time Algorithm for Near-Perfect Phylogeny" D. Fernandez-Baca (Ames, USA), J. Lagergren (Stockholm, Sweden) 12:40 LUNCH END OF ICALP'96 =============================================================================== GENERAL INFORMATION =============================================================================== LOCATION/CONFERENCE SITE: =============================================================================== All lectures will be given in the Conference Hall of the "Heinz Nixdorf MuseumsForum", Fuerstenallee 7, 33102 Paderborn. REGISTRATION/RECEPTION: =============================================================================== There will be a reception for all registrants from 6.00 pm to 9.00 pm on Sunday 7 at the Paderborn University, Building F, Fuerstenallee 11. This building is located next to the conference site. TRAVEL: =============================================================================== There are several ways to reach Paderborn. The airport of Paderborn/Lippstadt offers various connections to international airports (e.g. Amsterdam, London, Paris). Taxis (cost about 50 DM) and regular busses are available from the airport to the city (25 km). The nearest international airports are Duesseldorf (180 km), Hannover (160 km) and Frankfurt (300 km). There are good train connections from all these locations and other cities. Highway Connection: A33 - exit Paderborn-Zentrum. The conference site, Fuerstenallee 7, has regular connections with bus no. 11 (final destination: "Thuner Siedlung"; exit at bus stop: "Hopfenweg") from the city center as well as from the railway station. CLIMATE: =============================================================================== Daytime temperatures in July are expected to be around 22 degrees Celsius, nighttime temperatures around 15 degrees Celsius. Sunshine is expected with smaller rain showers once in a while. The conference rooms are fully air-conditioned. ACCOMODATION: =============================================================================== The room capacity of hotels in the center of Paderborn, and therefore closely to the conference site, is limited. The organizing team highly recommends your booking as soon as possible. !!! Please use the accomodation & registration form available from the !!! ICALP'96 www-page at http://uni-paderborn.de/~icalp96/ or the combined form at the end of this call or contact the organizing team. Attention: A hotel reservation, applied after June, 10 1996, cannot be guaranteed. REGISTRATION FEE: =============================================================================== Registration by May 15 after May 15 ------------------------------------------------------ Member of EATCS 360 DM 410 DM Non-member 400 DM 450 DM Student * 240 DM 290 DM Accompanying Person 120 DM 170 DM * certification of full-time student status has to be included The registration fee covers: member/ student accompanying non-member person --------------------------------------------------------- Receptions ++ ++ ++ Excursion ++ ++ ++ Guided Walk ++ ++ ++ ++ included Lunches, Refreshments ++ ++ -- -- not included Conference Dinner ++ -- ++ Proceedings ++ -- -- 1 year EATCS membership ++ -- -- The registration fee has to be paid either by bank transfer to the account (make sure that all intermediate bank charges are covered by your payment): Paderborn University Purpose: ICALP'96 Sparkasse Paderborn Account No.: 16107542 Bank Code: 472 501 01 or by a cheque (currency: German Mark (DM), Eurocheque preferred) payable to Prof. Dr. B. Monien and send it to Dr. Walter Unger, Paderborn University, Dept. of Computer Science, Fuerstenallee 11, D-33102 Paderborn, Germany !!! Please use the accomodation & registration form available from the !!! ICALP'96 www-page at http://uni-paderborn.de/~icalp96/ or the combined form at the end of this call or contact the organizing team. CANCELLATION: =============================================================================== In the case of cancellation another participant can be named without any costs. Otherwise an arrangement fee of 75.- DM has to be paid. No refund will be made to those canceling their registration after June 10. ACCOMPANYING PERSON PROGRAM: =============================================================================== In addition to the receptions, excursion and conference dinner the organizing team plans an interesting program for all accompanying persons during the talks. Tour A Visit of Detmold (a nice little town with good shopping areas), open air museum, castle, organ recital Tour B Sight-seeing Westphalia/Lippe: Schieder-Schwalenberg, Hameln and others. Tour C Visiting Kassel (famous castle and garden) All accompanying persons who are registered together with a conference parti- cipant will receive detailed information (including cost estimates for these additional activities), other interested persons will receive further informa- tion on request. EVENTS: =============================================================================== Sunday, July 7 Reception at the Paderborn University, Building F, 18:00 - 21:00 Fuerstenallee 11. This building is located next to the conference site. Monday, July 8 Guided walk through Paderborn 19:00 Tuesday, July 9 EATCS General Assembly 18:15 (at the conference site) Wednesday, July 10 Excursion to Corvey. Visit of the Castle Library at the Excursion 13:00 Principality of Corvey with its over 70.000 books and writs. Conference Dinner at the Buergerhaus "Im Schlosspark" in Schloss Neuhaus 19:30 Thursday, July 11 Reception by the Mayor of Paderborn in the City Hall 19:00 SPONSORS: =============================================================================== -- DFG - Deutsche Forschungsgemeinschaft -- Paderborn University -- Stadt Paderborn PROCEEDINGS: =============================================================================== Conference Proceedings are published by Springer-Verlag in the series "Lecture Notes in Computer Science" and will be distributed at the conference. ORGANIZING COMMITTEE: =============================================================================== Bernard Bauer Christian Scheideler Birgit Farr Willy-B. Strothmann Erich Koester Walter Unger Friedhelm Meyer auf der Heide Rolf Wanka Burkhard Monien FURTHER INFORMATION: =============================================================================== You will find all forms and a lot of additional information on the ICALP'96 www-page http://uni-paderborn.de/~icalp96/ or contact the organzing team via: email icalp96@uni-paderborn.de phone +49 5251 60-6296 fax +49 5251 60-6297 =============================================================================== =============================================================================== =============================================================================== ICALP'96 ACCOMODATION & REGISTRATION FORM =============================================================================== =============================================================================== =============================================================================== Please, fill in this form with typewriter or block letters, very legible and send it to Dr. Walter Unger Paderborn University Dept. of Computer Science Fuerstenallee 11 D-33102 Paderborn Surname: __________________________ Firstname: ________________________ Title: ___________________________ Affiliation: ______________________________________________________________ Address: ______________________________________________________________ ______________________________________________________________ ______________________ Country: ___________________________ ______________________ Phone: ___________________________ Email: ______________________ Fax: ___________________________ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Accomodation Form: If you fill in the accomodation form, the organizing team ****************** will forward it directly to the Verkehrsverein Paderborn, Marienplatz 2a, D-33098 Paderborn, Germany Phone: +49 5251 26461, Fax: +49 5251 22884 Attention: A hotel reservation, applied after June 10th, cannot be guaranteed. Arrival Date: ___________________ Time: __________________ Departure Date:__________________ Time: __________________ Please reserve: [ ] -- mark appropiately A B C from 130.- DM 80.- DM to 130.- DM up to 80.- DM ------------------------------------------------------------------------------- ___ single room(s) [ ] [ ] [ ] ___ double room(s) [ ] [ ] [ ] (Price per room and day) If no room(s) are available in selected category a) I herewith make a reservation of ___ room(s) of category ___ b) I herewith make a double room of category ___ at my exclusive disposal ___________________________________________________________ place, date and signature - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Registration Form: Complete one for each participant. ****************** [ ] -- mark appropiately my conference fee is: Registration by May 15 after May 15 ---------------------------------------------------------- Member of EATCS [ ] 360 DM [ ] 410 DM Non-member [ ] 400 DM [ ] 450 DM Student * [ ] 240 DM [ ] 290 DM * certification of full-time student Accompanying Person [ ] 120 DM [ ] 170 DM status has to be included How many: ___ Give their name(s): ___________________________________________________________ Total fee DM: ___________ [ ] I have transferred the fee to the ICALP account (no. 16107542) at the Sparkasse Paderborn (bank code 472 501 01) (make sure that all intermediate bank charges are covered by your payment, please enclode a copy ot the receipt of your payment) [ ] Cheque enclosed ___________________________________________________________ place, date and signature =============================================================================== =============================================================================== =============================================================================== -- ****************************************************** Contributions to be spread via DMANET are submitted to DMANET@math.utwente.nl Replies to a message carried on DMANET should NOT be addressed to DMANET but to the original sender. The original sender, however, is invited to prepare an update of the replies received and to communicate it via DMANET. DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)