Lecture Notes in Computer Science 2000 EditedbyG.Goos,J.HartmanisandJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo Reinhard Wilhelm (Ed.) Informatics 10 Years Back, 10 Years Ahead 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditor ReinhardWilhelm Universita¨tdesSaarlandes,FRInformatik Postfach151150,66041Saarbrücken,Germany E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Informatics:10yearsback,10yearsahead/ReinhardWilhelm(ed.). -Berlin;Heidelberg;NewYork;Barcelona;HongKong;London; Milan;Paris;Singapore;Tokyo:Springer,2001 (Lecturenotesincomputerscience;Vol.2000) ISBN3-540-41635-8 CRSubjectClassification(1998):A.1,D,F,H,I,B,C ISSN0302-9743 ISBN3-540-41635-8Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagBerlinHeidelbergNewYork amemberofBertelsmannSpringerScience+BusinessMediaGmbH ©Springer-VerlagBerlinHeidelberg2001 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyBollerMediendesign Printedonacid-freepaper SPIN10782222 06/3142 543210 Preface From August 27 to 31,2000,the International Conference and Research Center forComputerScienceinSchlossDagstuhl,Dagstuhlforshort,celebratedits10th anniversary. Since its founding in 1990, the objective of the Center has been to promote world-class research in computer science, support leading-edge contin- uing education, and promote the exchange of knowledge and findings between academia and industry. It hosts research seminars at which promising young research scientists are afforded the opportunity of discussing their views and research findings with the international elite of their field in a specific cutting- edge field of computer science. The seminars enable new ideas to be showcased, topical problems to be discussed, and the course to be set for future develop- ment inthis field. Roughly 15000scientists fromalloverthe worldandfromall areas of computer science as well as from application areas have participated in about 500 meetings in Dagstuhl during these 10 years. They have all enjoyed the“DagstuhlMagic”,asseveralguestshavecalledit,guaranteeingcreativeand productive meetings. At the occasion of the 10th anniversary, a conference was held, under the name Informatics - 10 Years Back, 10 Years Ahead. It was meant to do globally what usually happens locally in one field or a few related fields of Informatics every week in Dagstuhl, namely that a group of scientists presents the state of the art, identifies relevant open problems, and develops visions for the future. Internationallyrenownedresearcherswereaskedtoreflectuponwhatprogress hadbeenmadeintheir fieldinthe decadeofDagstuhl’sexistence andwhatwill probably be waiting for us in the next decade. We shamelessly, but successfully exploited their feelings of gratitude towards Dagstuhl; only very little pressure wasnecessarytomakethemaccepttheinvitation.Thespeakersinvestedconsid- erableeffortintopreparingtheirtalks,andtheirenthusiasmwascontagious;the audience was overwhelmedby talks of high quality. It was particularly welcome that a broad range of topics was presented, coveringmany areas of Informatics. The talks provokedquite lively discussions. The speakers agreed to contribute to this proceedings volume. The results of the discussions also found their way into the articles. Two authors, Fred Schneider and Robert Harper, even agreed to write a contribution jointly. Fred Schneider wasoriginallygroupedunder Security,while RobertHarper hadbeen askedtopresentSemantics.InRobert’sopinion,SemanticsisappliedTypeThe- ory, and currently one of the hottest applications of type theory is in the area of Security. ThespeakersrepresentedhighcompetenceacrossmanyareasofInformatics. Itwasthereforetempting to usetheircompetenceto discussandidentify Grand VI Preface Challenges in Informatics. This discussion process was started before and con- tinued during the conference. A number of challenges were identified. However, it couldnot be claimedthatthey werethe grandchallengesof Informatics.The listofchallengesisthereforenotincludedintheseproceedings,butpresentedon the Dagstuhl web site under http://www.dagstuhl.de/Challenges.It will be the starting point of an ongoing discussion process. Dagstuhl guests and scientists from outside are invited to contribute to this list. We would like to acknowledge the kind support for the conference that was provided by a variety of sources. Saarland University, Saarbru¨cken, offered its premises. Compaq, SAP AG, Dresdner Bank, Microsoft Research, Siemens AG, SUNMicrosystems,DaimlerChryslerAG,andsd&mprovidedfinancialsupport. Myveryspecialthanksgotothespeakerswhoinvestedtimeandenergyinto making the conference, and this volume, possible. Information about the International Conference and Research Center for Computer Science in SchlossDagstuhl, the concept, the organization,the appli- cation procedure for meetings, a description of the venue, photos, travel hints, the current program,and reports about past meetings, can be found under http://www.dagstuhl.de/ December 2000 Reinhard Wilhelm Scientific Director Intl. Conf. and Research Center for Computer Science, Schloss Dagstuhl, Germany Table of Contents The Web ...How to Make the Best Use of It The Web in 2010:Challenges and Opportunities for Database Research... 1 Gerhard Weikum Challenges in Ubiquitous Data Management........................... 24 Michael J. Franklin ...What’s Underneath Programmable Networks............................................ 34 Andrew T. Campbell, Michael E. Kounavis, John B. Vicente ...How to Still Feel Secure Multilateral Security: Enabling Technologies and Their Evaluation ....... 50 Andreas Pfitzmann Cryptography 2000±10 ............................................. 63 Ueli Maurer A Language-BasedApproach to Security.............................. 86 Fred B. Schneider, Greg Morrisett, Robert Harper Software ...the Right Engineering Software Engineering in the Years 2000 Minus and Plus Ten............. 102 Jochen Ludewig Thinking Tools for the Future of Computing Science.................... 112 Cliff B. Jones Orientations in Verification Engineering of Avionics Software ............ 131 Famantanantsoa Randimbivololona ...the Right Tooling Abstract Interpretation Based Formal Methods and Future Challenges ... 138 Patrick Cousot VIII Table of Contents Extended Static Checking: A Ten-Year Perspective..................... 157 K. Rustan M. Leino Progress on the State Explosion Problem in Model Checking ............ 176 Edmund Clarke, Orna Grumberg, Somesh Jha, Yuan Lu, Helmut Veith A Political Issue: Open Source? From Research Software to Open Source .............................. 195 Susan L. Graham Architecture Microprocessors— 10 Years Back, 10 Years Ahead .................... 209 Gurindar S. Sohi The Quantum Computing Challenge ................................. 219 Paul Vita´nyi Parallel Computation: MM +/- X.................................... 234 Lawrence Snyder Theory ...Why It Is Needed Computational Complexity and Mathematical Proofs................... 251 Juris Hartmanis Logic for Computer Science: The Engineering Challenge ................ 257 Wolfgang Thomas ...How It Becomes Practice From Algorithm to Programto Software Library....................... 268 Kurt Mehlhorn Artificial Intelligence Pervasive Speech and Language Technology ........................... 274 Wolfgang Wahlster Embodied Artificial Intelligence: 10 Years Back, 10 Years Forward ....... 294 Rolf Pfeifer Graphics and Vision Scientific Visualization - Methods and Applications - ................... 311 Hans Hagen, Achim Ebert, Rolf Hendrik van Lengen, Gerik Scheuermann Table of Contents IX Computer Vision: Past and Future ................................... 328 Jan-Olof Eklundh and Henrik I. Christensen Immersion into Other Disciplines Computational Biology at the Beginning of the Post-genomic Era ........ 341 Thomas Lengauer Computer Science in Physics ........................................ 356 A. Peter Young Author Index ................................................. 369 The Web in 2010: Challenges and Opportunities for Database Research Gerhard Weikum University of theSaarland, Saarbru¨cken, Germany [email protected], http://www-dbs.cs.uni-sb.de/ Abstract. The impressive advances in global networking and informa- tion technology provide great opportunities for all kinds of Web-based information services, ranging from digital libraries and information dis- covery to virtual-enterprise workflows and electronic commerce. How- ever, many of these services still exhibit rather poor quality in terms of unacceptable performance during load peaks, frequent and long out- ages, and unsatisfactory search results. For the next decade, the over- ridinggoal ofdatabaseresearchshouldbetoprovidemeansforbuilding zero-administration,self-tuninginformationserviceswithpredictablere- sponse time, virtually continuous availability, and, ultimately, “money- back” service-quality guarantees. A particularly challenging aspect of this theme is the quality of search results in digital libraries, scientific data repositories, and on the Web. To aim for more intelligent search that can truly find needles in haystacks, classical information retrieval methodsshouldbeintegratedwithqueryingcapabilities forstructurally richer Web data, most notably XML data, and automatic classification methodsbasedonstandardizedontologiesandstatisticalmachinelearn- ing.This papergivesan overviewofpromising research directions along these lines. 1 Introduction 1.1 Blessings and Curses of the World Wide Web We are witnessing the proliferation of the global information society with a sheer explosion of information services on the World Wide Web. This opens up unprecedented opportunities for information discovery, virtual enterprises and cyberspace-based collaboration, and also more mundane things such as e- commerce.Using suchservicesis,however,oftenafrustratingexperience.Many information services,including Web searchengines, deliver poor results - incon- sistent, arbitrarily inaccurate, or completely irrelevant data - to their clients, break easily and exhibit long outages, or perform so poorly that unacceptable response times ultimately render the offered service useless. The bottom line is thatthequalityofservicesishighlyunpredictable,andservicequalityguarantees are usually absent in today’s fast-moving IT world. R.Wilhelm(Ed.):Informatics.10YearsBack.10YearsAhead,LNCS2000,pp.1–23,2001. (cid:1)c Springer-VerlagBerlinHeidelberg2001