BULLETIN OF THE EATCS 78, October 2002 CONTENTS 1. EATCS Matters Letter from the President . . . . 1 Letter from the Bulletin Editor . . . . 2 The Japanese Chapter (by O. Watanabe) . . . . 3 2. ICALP 2002 Report on the General Assembly (by B. Rovan) . . . . 5 Report on ICALP 2002 (by M. Kudlek) . . . . 8 3. G\"odel Prize 2003 G\"odel Prize . . . . 16 4. Contents of TCS . . . . 19 5. EATCS Monographs and Texts . . . . 30 6. Institutional Sponsors . . . . 43 BRICS - Computer Science Department of University of Aarhus and Aalborg University (by U.H. Engberg, M. Nielsen, G. Winskel) . . . . 44 IPA - Institute for Programming research and Algorithmics (by T. Borghuis) . . . . 47 7. Sister Organizations Contents of SIGACT News . . . . 49 IFIP Technical Committee 1 (IFIP TC1), Foundations of Computer Science (by G. Ausiello, R. Gorrieri) . . . . 50 8. News from Australia (by S. Peuker) . . . . 55 9. News from New Zealand (by C.S. Calude) . . . . 56 10. News from Latin America (by A. Viola) . . . . 58 11. News from India (by M. Mukund) Primes in P (by J. Radhakrishnan) . . . . 61 12. News from Ireland (by A.K. Seda) . . . . 66 13. Columns J. D\'{\iaz: The Algorithmics Column Primes $\in$ P (Without Assumptions) . . . . 67 H. Ehrig: The Formal Specification Column Bigraphs meet Double Pushouts . . . . 72 L. Fortnow: The Computational Complexity Column Understanding the Mulmuley-Sohoni Approach to P vs. NP \\ (by K.W. Regan) . . . . 86 Y. Gurevich: The Logic in Computer Science Column Pairwise Testing (by A. Blass, Y. Gurevich) . . . . 100 M. Mavronicolas: The Distributed Computing Column Distributed Communication Algorithms \\ (by I. Chatzigiannakis, S. Nikoletseas, P. Spirakis) . . . . 133 M. Nielsen: The Concurrency Column Roadmap of Infinite Results (by J. Srba) . . . . 163 An Introduction to Probabilistic Automata (by M. Stoelinga) . . . . 176 G. Rozenberg: The Natural Computing Column Universality and Quantum Computing (by M. Hirvensalo) . . . . 199 A. Salomaa: The Formal Language Theory Column Membrane Computing: New Results, New Problems \\ (by C. Mart\'{\in-Vide, A. P\u{aun, G. P\u{aun) . . . . 204 14. Reflections EATCS Award Acceptance Speech (by M. Nivat) . . . . 213 15. Technical Contributions D.S. Bridges: Reality and Virtual Reality in Mathematics . . . . 221 R. Freund, M. Oswald: A Short Note on Analysing P Systems with Antiport Rules . . . . 231 J. Honkala: A Note on Systems of Alternative Word Equations . . . . 237 G. Rote: Crossing the Bridge at Night . . . . 241 L. Staiger, H. Yamasaki: A Simple Example of an $\omega$-Language Topologically 16. Education Matters (by H.-J. Kreowski) . . . . 251 A Note on MMiSS (by B. Krieg-Br\"uckner) . . . . 252 17. Reports on Conferences First term of the First International Ph.D. School in Formal Languages and Applications, Tarragona, Spain, 2 April - 30 May 2002 \\ (report by V. Mitrana) . . . . 255 Eighteenth British Colloquium on Theoretical Computer Science (BCTCS18), Bristol, United Kingdom, 7-10 April 2002 (report by Ch. Tofts) . . . . 257 Advanced School and Workshop on Models and Algorithms for the World Wide Web (MAW 02), Udine, Italy, 17-22 June 2002 (report by M. Montangero) . . . . 271 Computing Beyond Silicon Summer School (CBSSS), Pasadena, CA, U.S.A., \\ 17 June - 17 July 2002 (report by E. Losseva) . . . . 273 Twenty-Third International Conference on Application and Theory of Petri Nets (ICATPN 2002), Adelaide, Australia, 24-28 June 2002 \\ (report by L. Petrucci) . . . . 276 Thirteenth Annual Symposium on Combinatorial Pattern Matching 2002 \\ (CPM 2002), Fukuoka, Japan, 3-5 July 2002 (report by F. Franek) . . . . 278 TCS conference at the 17th IFIP World Computer Congress, Montreal, Canada, 26-29 August 2002 (report by J. Gruska) . . . . 279 18. Conference Announcements DIMACS Workshops and Events Calendar . . . . 283 Fixed Points in Computer Science (FICS'2003), A Satellite Workshop to \\ ETAPS'2003, Warsaw, Poland, 12-13 April 2003 . . . . 290 Ninth International Meeting on DNA Based Computers (DNA9), Madison, Wisconsin, U.S.A., 1-4 June 2003 . . . . 291 Third International Conference of B and Z-Users, Turku, Finland, \\ 4-6 June 2003 . . . . 293 Twenty-Ninth International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), Elspeet, The Netherlands, 19-21 June 2003 . . . . 298 Twenty-Fourth International Conference on Application and Theory of Petri Nets (ICATPN 2003), Eindhoven, The Netherlands, 23-27 June 2003 . . . . 300 Seventh International Conference on Developments in Language Theory, Szeged, Hungary, 7-11 July 2003 . . . . 302 Fourth International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS'03), Dijon, France, 7-12 July 2003 . . . . 303 Andrei Ershov Fifth International Conference on Perspectives of System Informatics (PSI'03), Novosibirsk, Akademgorodok, Russia, 9-12 July 2003 . . . . 304 Eighth International Conference on Implementation and Application of Automata (CIAA 2003), Santa Barbara, California, U.S.A., 16-18 July 2003 . . . . 306 Twenty-Eighth International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), Bratislava, Slovak Republic, \\ 25-29 August 2003 . . . . 308 International Conference on Computability and Complexity in Analysis \\ (CCA 2003), Cincinnati, U.S.A., 28-30 August 2003 . . . . 309 Fourth Advanced Course on Petri Nets, Eichst\"att, Germany, \\ 15-25 September 2003 . . . . 310 {\em Thirtieth International Colloquium on Automata, Languages and Programming (ICALP 2003), Eindhoven, The Netherlands, 30 June - 4 July 2003 . . . . 311 19. Agenda of Events . . . . 313 20. Reports on Computer Science Organizations European Educational Forum (EEF) (by T. Borghuis) . . . . 315 21. Abstracts of Ph.D. Theses R. Zizza: On the Power of Classes of Splicing Systems . . . . 319 22. Miscellaneous Ole-Johan Dahl, Obituary (by K. Nygaard) . . . . 323 Kristen Nygaard, Obituary (by O. Lehrmann Madsen) . . . . 325 Structure of Scientific Collaboration in Graph Transformation (by G. Valiente) . . . . 329 23. Moving Around . . . . 346 24. Puzzle Corner (by L. Rosaz) . . . . 347 25. EATCS Leaflet . . . . 350 26. Cartoons . . . . 18, 54, 220, 312, 346