Lecture Notes in Computer Science 3075 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos New York University, NY, USA Doug Tygar University of California, Berkeley, CA, USA MosheY. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany This page intentionally left blank Wolfgang Lenski (Ed.) Logic versus Approximation Essays Dedicated to Michael M. Richter on the Occasion of his 65th Birthday Springer eBook ISBN: 3-540-25967-8 Print ISBN: 3-540-22562-5 ©2005 Springer Science + Business Media, Inc. Print©2004Springer-Verlag Berlin Heidelberg All rights reserved No part of this eBook maybe reproducedor transmitted inanyform or byanymeans,electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America Visit Springer's eBookstore at: http://ebooks.springerlink.com and the Springer Global Website Online at: http://www.springeronline.com Preface There are prominent moments in time whenongoing scientific work is interrupted for a moment and a more general perspective is sought. The symposium on Logic Versus Approximation was one such moment, a chance to reflect on the influences of the scientific work of Michael M. Richter on the occasion of his 65th birthday. This collection is a selection of contributions to this symposium. In focussing on today’s knowledge-based systems we encounter two major paradigms of reasoning. There are on the one hand the logic-based approaches where ‘logic’ is to be understood in a rather broad sense. This approach is predo- minantly deployed in symbolic domains where numerical calculations are not the core challenge. Logic has without any doubt provided a powerfulmethodological tool. Progress in this area is mainly performed by refining the representation of structural aspects which results in a succession of models that should capture increasingly more aspects of the domain. This may be seen as an approximation process on the metalevel. There is also some weakness in the logic-based approach, though, which is due to its very foundation. The semantic theory of truth by Tarski has explicitly eliminated personal influence on the validity of truth as well as the representa- tion of dynamically changing variations of the ground terms inside the theory. It does not allow for adaptive individual behavior per se as is, for example, expli- citly required in the field of e-commerce. From a methodological point of view pragmatics is required as opposed to semantics. These aspects make it worth considering rather philosophical and foundational reflections as well. On the other hand we find approximation-oriented reasoning. Methods of this kind are mainly applied in numerical domains where approximation is part of the scientific methodology itself. Here we again distinguish two differentbasic types, discrete and continuous domains. However, from a more abstract level all these approaches do focus on si- milar topics and arise on various levels such as problem modeling, inference and problem-solving mechanisms, algorithms and mathematical methods, and mathematical relations between discrete and continuous properties, and are in- tegrated in tools and applications. Research on both kinds of reasoning in these areas has mostly been conduc- ted independently so far. Whereas approaches based on discrete or continuous domains influence each other in a sometimes surprising way, influences between these and the symbolic approach have been less intensively studied. Especially the potentialities of an integration are certainly not understood to a satisfactory degree although the primary focus from an abstract point of view is on a similar topic. It requires a unifying vision to which all parts have to contribute from their own perspectives. Scientific work is necessarily always the construction of sense. Progress is by no means arbitrary, but always guided by a quest for a still betterunderstanding VI Preface of parts of the world. Such construction processes are essentially hermeneutical ones, and an emanating coherent understanding of isolated topics is only gua- ranteed through a unifying view of a personal vision. Such a vision is especially provided by the research interests of Michael M. Richter, which have influenced the overall perspective of the symposium. In this sense his scientific work was present all the time during the symposium. Michael M. Richter has exerted a wide influence on logic and computer science. Although his productive work is widely spread there are some gene- ral interests behind them. A central interest is certainly in modelling structural aspects of reality for problem solving along with the search for adequate me- thodologies for this purpose. Michael M. Richter made significant contributions, however, to a wide variety of topics ranging from purely logical problems in mo- del theory and non-standard analysis to representation techniques in computer science that have finally emancipated themselves from their logical origins with special emphasis given to problems in artificial intelligence and knowledge-based systems. The symposium on Logic Versus Approximation brought insight into these different approaches and contributed to the emergence of a unifying perspec- tive. At the same time it reflected the variety of Michael M. Richter’s scientific interests. The contributions to this volume range from logical problems, philo- sophical considerations, applications of mathematics and computer science to real-world problems, and programming methodologies up to current challenges in expert systems. The members of the organization and program committee especially wish to thank the authors for submitting their papers and responding to the feedback provided by the referees. We also wish to express our gratitude to the FAW- Förderkreis e. V. and the empolis GmbH for their valuable support. Finally, we are very grateful to the local organization team of the International Conference and Research Center for Computer Science at Schloß Dagstuhl for their profes- sionalism in handling the local arrangements. To honor Michael M. Richter, the President of the University of Kaisers- lautern, Prof. Dr. Helmut J. Schmidt, in his diverting opening talk surveyed the creative powers of Michael M. Richter garnished with concise anecdotes on mutual personal experiences at Kaiserslautern University. To pay special tribute to the work of Michael M. Richter the scientific program of the symposium was complemented by lively and inspiring after-dinner speeches by Franz Josef Radermacher and Paul Stähly. The surroundings of the International Conference Center of Schloß Dagstuhl provided the appropriate atmosphere and greatly helped in making the symposium a scientifically intriguing, socially enjoyable, and altogether most memorable occasion. This collection is meant to capture the essence of its scientific aspects. Kaiserslautern, December 2003 Wolfgang Lenski Program and Organization Committee Althoff,Klaus-Dieter Fraunhofer IESE Kaiserslautern Bergmann, Ralph Univ. Hildesheim Lenski, Wolfgang TU Kaiserslautern Möhring, Rolf TU Berlin Radermacher, Franz Josef FAW/Univ. Ulm This page intentionally left blank Table of Contents A True Unprovable Formula of Fuzzy Predicate Logic 1 Petr Hájek The Inherent Indistinguishability in Fuzzy Systems 6 Frank Klawonn, Rudolf Kruse On Models for Quantified Boolean Formulas 18 Hans Kleine Büning, Xishun Zhao Polynomial Algorithms for MPSP Using Parametric Linear Programming 33 Babak Mougouie Discrete and Continuous Methods of Demography 43 Walter Oberschelp Computer Science between Symbolic Representation and Open Construction 59 Britta Schinzel Towards a Theory of Information 77 Wolfgang Lenski Retrieval by Structure from Chemical Data Bases 106 Thomas Kämpke Engineers Don’t Search 120 Benno Stein Randomized Search Heuristics as an Alternative to Exact Optimization 138 Ingo Wegener Approximation of Utility Functions by Learning Similarity Measures 150 Armin Stahl Knowledge Sharing in Agile Software Teams 173 Thomas Chau, Frank Maurer Logic and Approximation in Knowledge Based Systems 184 Michael M. Richter Author Index 205