Lecture Notes in Computer Science 2237 EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Tokyo Philippe Codognet (Ed.) Logic Programming 17th International Conference, ICLP 2001 Paphos,Cyprus,November26–December1,2001 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditor PhilippeCodognet UniversityofParis6,LIP6,case169 8rueduCapitaineScott,75015Paris,France E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Logicprogramming:17thinternationalconference;proceedings/ICLP2001, Paphos,Cyprus,November26-December1,2001.PhilippeCocognet(ed.).- Berlin;Heidelberg;NewYork;Barcelona;HongKong;London;Milan; Paris;Tokyo:Springer,2001 (Lecturenotesincomputerscience;Vol.2237) ISBN3-540-42935-2 CRSubjectClassification(1998):D.1.6,I.2.3,D.3,F.3,F.4.1 ISSN0302-9743 ISBN3-540-42935-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,dataconversionbySteingräberSatztechnikGmbH,Heidelberg Printedonacid-freepaper SPIN:10845826 06/3142 543210 Preface A new millennium has started and new tools, heirs of three decades of research and development in the Logic Programming paradigm, are bringing new solu- tionstocopewiththeincreasingcomplexityoftoday’scomputersystems.Com- putationallogicingeneralandlogicprogramminginparticularwillalwaysplaya keyroleintheunderstanding,formalizing,anddevelopmentofcomplexsoftware. ICLP2001 was the 17th International Conference on Logic Programming andcontinuedaseriesofconferencesinitiatedinMarseille,France,in1982.This year ICLP was held in conjunction with CP2001, the 7th International Con- ference on Principle and Practice of Constraint Programming. A coordinated program schedule and joint events were organized in order to maximize the in- teraction between these two neighboring communities. LOPSTR2001, the 11th international workshop on Logic-based Program Synthesis and Transformation was also co-located with ICLP2001 and CP2001 this year, bringing together a larger community to share novel research results. Seven satellite workshops were also associated to the conference and took place on the day following the conference. We received 64 papers, among which 23 were selected for presentation at the conference and inclusion in the conference proceedings. In addition to paper presentations, the conference program also included four invited talks and four tutorials. We chose this year to celebrate the founders of the logic programming field,namelyAlainColmerauerandBobKowalski,whoarebothcelebratingtheir 60th birthday. The other two invited talks were given by Patrick Cousot, pio- neerinthefieldofabstractinterpretation,andAshishGupta,whopresentedhis industrial experience on cross-enterprise databases at amazon.com and Tavant Technologies. The four tutorials were given by Eric Villemonte de la Clergerie, V.S. Subrahmanian, Kazunori Ueda, and Jan Wielemaker. I would like to thank all the authors of the submitted papers, the Program Committee members, and the referees for their time and efforts spent in the re- viewingprocess,theconferencechairTonyKakasandhisteamattheUniversity of Cyprus for the excellent organization of the conference, and Toby Walsh, the CP2001 program chair, for his constant cooperation and interaction. Last but not least, special thanks to Yoann Fabre at the University of Paris 6 for taking care of installing and maintaining the paper review system. September 2001 Philippe Codognet Organization Conference Chair Tony Kakas University of Cyprus Program Chair Philippe Codognet University of Paris Workshop Chair Antonio Brogi University of Pisa Program Committee Krzysztof Apt CWI, Amsterdam Frederic Benhamou University of Nantes Veronica Dahl Simon Fraser University Bart Demoen University of Leuven Danny De Schreye University of Leuven Ju¨rgen Dix University of Koblenz Gilberto Fil´e University of Padova Seif Haridi SICS, Stockholm Manuel Hermenegildo Technical University of Madrid Pat Hill University of Leeds Gerard Huet INRIA Antonis Kakas University of Cyprus Michael Maher Loyola University Chicago Kim Marriott Monash University Catuscia Palamidessi Pennsylvania State University Luis Moniz Pereira New University of Lisbon Andreas Podelski Max-Planck Institute V.S. Subrahmanian University of Maryland Kazunori Ueda Waseda University, Tokyo Pascal Van Hentenryck Brown University Toby Walsh University of York VIII Organization Referees Salvador Abreu Roberta Gori Gilles Richard M. Aiello Frederic Goualard Francesca Rossi Hassan A¨ıt-Kaci John Grant S. Ruggieri Jose Julio Alferes Laurent Granvilliers D. Sacc´a James Bailey Gopal Gupta Chiaki Sakama Francois Barthelemy Chris Hankin Vitor Santos Costa S. Billot Michael Hanus Frederic Saubion Philippe Blache Katsumi Inoue Francesca Scozzari Annalisa Bossi Gerda Janssens Alexander Serebrenik S. Brand Arnaud Lallouet Kish Shen Gerhard Brewka Evelina Lamma Jan-Georg Smaus Maurice Bruynooghe Antonio Ferna´ndez Leiva Harald Sondergaard Roberto Bruni Vladimir Lifschitz Fausto Spoto Manuel Carro Wiktor Marek Iain Duncan Stalker Witold Charatonik Nancy Mazur Robert Sta´rk Livio Colussi Bernd Meyer Frieder Stolzenburg Agostino Cortesi Laurent Michel Ju¨rgen Stuber Patrick Cousot Dale Miller Terrance Swift Carlos Viegas Dam´asio Phan Minh Dung Paul Tarau F. de Boer Eric Monfroy Miroslaw Truszczynski Eric de la Clergerie Frank Morawietz Hudson Turner Pierangelo Dell’Acqua J. J. Moreno Navarro Silvio Valentini Marc Denecker Hector Munoz-Avila Ruben Vandeginste Alexander Dikovsky Hiroshi Nakashima W. J. van Hoeve Mireille Ducass´e Dana Nau Bert Van Nuffelen Lyndon Drake Ilkka Niemela Sofie Verbaeten Wolfgang Faber Fatma Ozcan Christine Vrain Francois Fages Gerald Penn Enea Zaffanella G´erard Ferrand Enrico Pontelli Carlo Zaniolo M. Garcia de la Banda Ant´onio Porto Jean-Daniel Zucker Ulrich Geske Paulo Quaresma Roberto Giacobazzi Christian R´etor´e Sponsors The Association for Logic Programming, the University of Cyprus, Cyprus Telecommunications Authority, and IBM. Table of Contents Invited Speakers Solving the Multiplication Constraint in Several Approximation Spaces ... 1 A. Colmerauer Is Logic Really Dead or Only Just Sleeping?........................... 2 R. Kowalski Design of Syntactic Program Transformations by Abstract Interpretation of Semantic Transformations ................ 4 P. Cousot X-tegration – Some Cross-Enterprise Thoughts ........................ 6 A. Gupta Tutorials Building Real-Life Applications with Prolog ........................... 7 J. Wielemaker Natural Language Tabular Parsing ................................... 8 E´. Villemonte de la Clergerie A Close Look at Constraint-Based Concurrency........................ 9 K. Ueda Probabilistic Databases and Logic Programming ....................... 10 V.S. Subrahmanian Conference Papers Understanding Memory Management in Prolog Systems ................ 11 L.F. Castro, V.S. Costa PALS: An Or-Parallel Implementation of Prolog on Beowulf Architectures ........................................... 27 K. Villaverde, E. Pontelli, H. Guo, G. Gupta On a Tabling Engine That Can Exploit Or-Parallelism.................. 43 R. Rocha, F. Silva, V.S. Costa Revisiting the Cardinality Operator and Introducing the Cardinality-Path Constraint Family ................ 59 N. Beldiceanu, M. Carlsson X Table of Contents Optimizing Compilation of Constraint Handling Rules .................. 74 C. Holzbaur, M. Garc´ıa de la Banda, D. Jeffery, P.J. Stuckey Building Constraint Solvers with HAL................................ 90 M. Garc´ıa de la Banda, D. Jeffery, K. Marriott, N. Nethercote, P.J. Stuckey, C. Holzbaur PracticalAspectsforaWorkingCompileTimeGarbageCollectionSystem for Mercury ....................................................... 105 N. Mazur, P. Ross, G. Janssens, M. Bruynooghe Positive Boolean Functions as Multiheaded Clauses .................... 120 J.M. Howe, A. King Higher-Precision Groundness Analysis ................................ 135 M. Codish, S. Genaim, H. Søndergaard, P.J. Stuckey Speculative Beats Conservative Justification........................... 150 H.-F. Guo, C.R. Ramakrishnan, I.V. Ramakrishnan Local and Symbolic Bisimulation Using Tabled Constraint Logic Programming .......................... 166 S. Basu, M. Mukund, C.R. Ramakrishnan, I.V. Ramakrishnan, R. Verma A Simple Scheme for Implementing Tabled Logic Programming Systems Based on Dynamic Reordering of Alternatives ......................... 181 H.-F. Guo, G. Gupta Fixed-Parameter Complexity of Semantics for Logic Programs ........... 197 Z. Lonc, M. Truszczyn´ski Ultimate Well-Founded and Stable Semantics for Logic Programs with Aggregates.................................. 212 M. Denecker, N. Pelov, M. Bruynooghe Alternating Fixed Points in Boolean Equation Systems as Preferred Stable Models .......................................... 227 K. Narayan Kumar, C.R. Ramakrishnan, S.A. Smolka Fages’ Theorem for Programs with Nested Expressions ................. 242 E. Erdem, V. Lifschitz Semantics of Normal Logic Programs with Embedded Implications ....... 255 F. Orejas, E. Pasarella, E. Pino A Multi-adjoint Logic Approach to Abductive Reasoning................ 269 J. Medina, M. Ojeda-Aciego, P. Vojta´ˇs