Lecture Notes in Computer Science 2136 EditedbyG.Goos,J.HartmanisandJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo Jiˇr´ı Sgall Alesˇ Pultr Petr Kolman (Eds.) Mathematical Foundations of Computer Science 2001 26th International Symposium, MFCS 2001 Maria´nske´ La´zne˘, Czech Republic,August 27-31, 2001 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditors Jiˇr´ıSgall MathematicalInstitute,ASCR Zˇitna´25,11567Praha1,CzechRepublic E-mail:[email protected] AlesˇPultr PetrKolman CharlesUniversity,FacultyofMathematicsandPhysics InstituteforTheoreticalComputerScience(ITI) Malostranske´na´meˇst´ı25,11800Praha1,CzechRepublic E-mail:{pultr/kolman}@kam.ms.mff.cuni.cz Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Mathematicalfoundationsofcomputerscience2001:26thinternational symposium;proceedings/MFCS2001,MariánskéLáznÿée,CzechRepublic, August27-31,2001.JiÿéríSgall...(ed.).-Berlin;Heidelberg;NewYork; Barcelona;HongKong;London;Milan;Paris;Tokyo:Springer,2001 (Lecturenotesincomputerscience;Vol.2136) ISBN3-540-42496-2 CRSubjectClassification(1998):F,G.2,D.3,C.2,I.3 ISSN0302-9743 ISBN3-540-42496-2Springer-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 http://www.springer.de ©Springer-VerlagBerlinHeidelberg2001 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyDA-TeXGerdBlumenstein Printedonacid-freepaper SPIN10840127 06/3142 543210 Foreword This volume contains papers selected for presentation at the 26th International Symposium on Mathematical Foundations of Computer Science – MFCS 2001, held in Maria´nsk´e L´aznˇe, Czech Republic, August 27 – 31, 2001. MFCS 2001 was organized by the Mathematical Institute (Academy of Sci- ences of the Czech Republic), the Institute for Theoretical Computer Science (CharlesUniversity,FacultyofMathematicsandPhysics),theInstituteofCom- puter Science (Academy of Sciences of the Czech Republic), and Action M Agency.ItwassupportedbytheEuropeanResearchConsortiumforInformatics and Mathematics, the Czech Research Consortium for Informatics and Math- ematics, and the European Association for Theoretical Computer Science. We gratefully acknowledge the support of all these institutions. The series of MFCS symposia, organized on a rotating basis in Poland, Slo- vakia, and the Czech Republic, has a well-established tradition. The aim is to encourage high-quality research in all branches of theoretical computer science and bring together specialists who do not usually meet at specialized confer- ences.PreviousmeetingstookplaceinJablonna,1972;Sˇtrbsk´ePleso,1973;Jad- wisin,1974;Maria´nsk´eL´aznˇe,1975;Gdan´sk,1976;Tatransk´aLomnica,1977;Za- kopane,1978;Olomouc,1979;Rydzina,1980;Sˇtrbsk´ePleso,1981;Prague,1984; Bratislava,1986;KarlovyVary,1988;Pora¸bka-Kozubnik,1989;Banska´Bystrica, 1990;KazimierzDolny,1991;Prague,1992;Gdan´sk,1993;Koˇsice,1994;Prague, 1995; Krako´w, 1996; Bratislava, 1997; Brno, 1998; Szklarska Pore¸ba, 1999; and Bratislava, 2000. It is our pleasure to announce that at the opening of MFCS 2001, Dana Scott (Carnegie-MellonUniv., Pittsburg, PA, U.S.A.) was awardedthe Bolzano Honorary Medal of the Academy of Sciences of the Czech Republic for his con- tribution to the development of theoretical computer science and mathematics in general and his cooperation with Czech scientists in particular. The MFCS2001proceedingsconsistof10invitedpapers and51contributed papers. We are grateful to all the invited speakers for accepting our invitation and sharing their insights on their research areas. We thank the authors of all submissions for their contribution to the scientific program of the meeting. The contributed papers were selected by the Program Committee out of a total of 118 submissions. All submissions were evaluated by three or four members of the committee, with the assistance of referees, for a total of more than 450 reports. After electronic discussions, the final agreement was reached atthe selectionmeeting inPragueonMay11–12,2001(the programcommittee members denoted by * in the list below took partin the meeting). We thank all the program committee members and referees for their work which contributed to the quality of the meeting. We have tried to make the list of referees as complete and accurate as possible and apologize for any omissions and errors. VI Foreword Special thanks go to Jochen Bern who provided a reliable software system used for electronic submissions and reviewing (tested before on STACS 1999 through 2001), and volunteered a fair amount of his night-time to maintain and further improve the system according to our unrealistic specifications and expectations. Finally, we would like to thank Milena Zeithamlova´, Lucie V´achova´, and Andrea Kutnarova´ from Action M Agency for their excellent work on local ar- rangements. We wish MFCS 2002, to be held in Warsaw, success and many excellent contributions. June 2001 Jiˇr´ıSgall Aleˇs Pultr Petr Kolman Program Committee Manfred Broy (TU Munich) Harry Buhrman (CWI, Amsterdam) Anne Condon (Univ. of British Columbia, Vancouver) Peter van Emde Boas (Amsterdam Univ.) Martin Grohe (Univ. of Illinois, Chicago) Petr Ha´jek * (Academy of Sciences, Prague) Juraj Hromkovic * (RWTH Aachen) Russell Impagliazzo (UC San Diego) Achim Jung (Univ. of Birmingham) Juhani Karhuma¨ki * (Univ. of Turku) Matthias Krause * (Univ. Mannheim) J. A. Makowsky * (Technion, Haifa) Tadeusz Morzy (Poznan Univ. of Technology) Aleˇs Pultr * (Charles Univ., Prague, co-chair) Giuseppe Rosolini (Univ. of Genova) Branislav Rovan * (Comenius Univ., Bratislava) Don Sannella (Univ. of Edinburgh) Jiˇr´ıSgall * (Academy of Sciences, Prague, chair) Ga´bor Tardos (Academy of Sciences, Budapest) Igor Walukiewicz (Warsaw Univ.) Ingo Wegener * (Univ. Dortmund) Peter Widmayer (ETH, Zurich) Gerhard Woeginger * (Technical Univ. Graz) Moti Yung (Columbia Univ., New York). Foreword VII Referees E. Allender J. Fiala V. K˚urkova´ A. Ambainis E. Fischer M. Kutylowski K. Ambos-Spies S. Fishman J. van Leeuwen G. Ankoudinov T. Fleiner H. Lefmann P. Auer J. Flum M. Lenisa R. Babilon J. Forster S. Leonardi J. Baldwin L. Fortnow A. Lepist¨o K. Balinska K. Friedl Z. Liptak R. Beigel W. Gasarch L. P. Lisovik A. Benczur S. Gerke S. Lucks T. Bernholt O. Giel H. L¨otzbeyer M. Bl¨aser A. Goerdt S. P. Mansilla J. Bloemer M. Goldmann J. Manuch H. L. Bodlaender V. Grolmusz M. Mareˇs B. Bollig P. Hajnal J. Marino D. Bongartz V. Halava J. Matouˇsek A. Brodsky T. Harju R. Mayr H. Broersma J. Hastad J. McKinna R. Bruni P. Hell W. Merkle P. Buergisser U. Hertrampf S. Merz H.-J. B¨ockenhauer V. Heun M. Michal P. Callaghan J. Hillston B. Moeller C. S. Calude M. Hirvensalo T. Morzy O. Carton J.-H. Hoepman A. Muscholl B. Chlebus T. Hofmeister R. Neruda K. Chmiel J. Honkala T. Nipkow J. Chrzaszcz H. Hoogeveen D. Niwinski M. Cieliebak R. Jacob T. Noll J. Csirik A. Jakoby J. C. Oostveen L. Csirmaz T. Jansen L. Paolini F. Cucker M. Jerrum M. Parente C. Damm S. Jukna P. Penna S. V. Daneshmand M. Kaminski P. Jeavons G. Delzanno J. Kari A. Petit J. D´ıaz M. Karpinski T. Petkovic S. Dobrev H. Klauck J.-E. Pin W. Doerfler B. Klinz T. Pitassi M. Drmota T. Knapik T. Polzin S. Droste P. Koiran C. Pomm L. Epstein P. Kolman K. Pruhs M. Escardo J. Kraj´ıˇcek P. Pudla´k Z. Esik I. Kramosil R. Raz J. Esparza A. Kro´likowski O. Regev S. Fekete Z. Kr´olikowski R. Reischuk VIII Foreword R. Renner A. Simpson K. Tinnefeld L. Ronyai P. Siwak G. Turan G. Rote M. Skoviera J. Tyszkiewicz S. Rudich M. Skutella M. Uetz P. R˚uˇziˇcka Ch. Stamm P. Urzyczyn A. Salomaa I. Stark R. Vestergaard R. Sandner T. Stauner E. Vigoda D. Sangiorgi D. Sˇtefankoviˇc A. Vilbig L. Santocanale J. Stefanowski P. Vitanyi M. Sauerhoff B. Steffen I. Vrto P. Savicky´ A. Steger S. Waack M. Schaefer M. Steinby E. Wanke K. Schlude F. Stephan J. Watrous N. Schmitt J. Stoklosa D. Wawrzyniak G. Schnitger M. Sviridenko K. Weihrauch T. Schwentick G. Szabo M. Wenzel H. Schwichtenberg R. Szelepcsenyi C. Witt L. Segoufin D. Taylor S. Yu S. Seibert J. A. Telle S. Zˇ´ak G. Senizergues V. Terrier D. Sieling D. Th´erien H. Simon P. S. Thiagarajan Table of Contents Invited Talks A New Category for Semantics ..............................................1 Dana S. Scott On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity ......................3 Peter Bu¨rgisser Playing Games with Algorithms: Algorithmic Combinatorial Game Theory ..................................18 Erik D. Demaine Some Recent Results on Data Mining and Search ..........................33 Amos Fiat Hypertree Decompositions: A Survey ......................................37 Georg Gottlob, Nicola Leone, and Francesco Scarcello The Strength of Non-size-increasing Computation (Introduction and Summary) ..............................................58 Martin Hofmann Introduction to Recent Quantum Algorithms ...............................62 Peter Høyer Decomposition Methods and Sampling Circuits in the Cartesian Lattice ....74 Dana Randall New Algorithms for k-SAT Based on the Local Search Principle ............87 Uwe Sch¨oning Linear Temporal Logic and Finite Semigroups .............................96 Thomas Wilke Contributed Talks Refined Search Tree Technique for Dominating Set on Planar Graphs ...111 Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau, Rolf Niedermeier, Fran Rosamond, and Ulrike Stege The Computational Power of a Family of Decision Forests ................123 Kazuyuki Amano, Tsukuru Hirosawa, Yusuke Watanabe, and Akira Maruoka Exact Results for Accepting Probabilities of Quantum Automata .........135 Andris Ambainis and Arnolds K¸ikusts