This book constitutes the thoroughly refereed post-proceedings of the Joint ERCIM/Compulog-Net Workshop on New Trends in Constraints held in Paphos, Cyprus, Greece in October 1999. The 12 revised full research papers presented together with four surveys by leading researchers were carefully reviewed. The book is divided in topical sections on constraint propagation and manipulation, constraint programming, and rule-based constraint programming.
Lecture Notes in Artificial Intelligence Subseries of Lecture Notes in Computer Science Edited by J. G. Carbonell and J. Siekmann Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen 1865 3 Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Singapore Tokyo Krzysztof R. Apt Antonis C. Kakas Eric Monfroy Francesca Rossi (Eds.) New Trends in Constraints Joint ERCIM/Compulog Net Workshop Paphos, Cyprus, October 25-27, 1999 Selected Papers 13 Series Editors Jaime G. Carbonell,Carnegie Mellon University, Pittsburgh, PA, USA J¨org Siekmann, University of Saarland, Saarbr¨ucken, Germany Volume Editors Krzysztof R. Apt Eric Monfroy CWI, Kruislaan 413, 1090 GB Amsterdam, The Netherlands E-mail:{K.R.Apt/Eric.Monfroy}@cwi.nl Antonis C. Kakas University of Cyprus, Department of Computer Science 75 Kallipoleos Str., 1678 Nicosia, Cyprus E-mail:
[email protected] Francesca Rossi University of Padua, Department of Pure and Applied Mathematics Via G. B. Belzoni 7, 35131 Padua, Italy E-mail:
[email protected] Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme New trends in constraints : joint ERCIM Compulog Net workshop, Paphos, Cyprus, October 1999 ; selected papers / Krysztof R. Apt . . . (ed.). - Berlin ; Heidelberg ; New York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Singapore ; Tokyo : Springer, 2000 (Lecture notes in computer science ; Vol. 1865 : Lecture notes in artificial intelligence) ISBN 3-540-67885-9 CR Subject Classification (1998): D.1, D.3.2-3, I.2.3-4, F.3.2, F.4.1, I.2.8 ISBN 3-540-67885-9 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH © Springer-Verlag Berlin Heidelberg 2000 Printed in Germany Typesetting: Camera-ready by author, data conversion by PTP-Berlin, Stefan Sossna Printed on acid-free paper SPIN 10722264 06/3142 543210 Preface Constraint programming is a higly declarative and relatively new approach to computing in which the programming process consists mainly of stating a set of requirements (the constraints) and solving them via general as well as domaindependent methods. In the last decade, constraint programming has evolved from a basic research idea to a powerful programming paradigm, that is increasingly used to model and solve many hard real-life problems. Many areas of computer science have taken advantage of the p