Advances in Computing Science Advisory Board R. F. Albrecht, Innsbruck Z. Bubnicki, Wroclaw R. E. Burkard, Graz A. G. Butkovskiy, Moscow C. Cap, Zurich M. Dal Cin, Erlangen W Hackbusch, Kiel G. Johnson, Fort Collins W Kreutzer, Christchurch W. G. Kropatsch, Wien 1. Lovrec, Zagreb G. Nemeth, Budapest H. J. Steuer, Wien Y. Takahara, Chiba W. Tornig, Darmstadt 1. Troch, Wien H. P. Zima, Wien C.Brink W. Kahl G. Schmidt (eds.) Relational Methods in Computer Science Springer-Verlag Wien GmbH Prof. Dr. Chris Brink Department of Mathematics and Applied Mathematics, University of Cape Town, Cape Town, South Africa Dr. Wolfram Kahl Prof. Dr. Gunther Schmidt Fakultiit fiir Informatik, Universitiit der Bundeswehr Munchen, Neubiberg, Federal Republic of Germany This work is subject to copyright. An rights are reserved, whether the whole or part of the material is concemed, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machines or similar means, and storage in data banks. © 1997 Springer-Verlag Wien Originally published by Springer-Verlag Wien New York in 1997 Typesetting: Camera ready by authors Graphic design: Ecke Bonk Printed on acid-free and chlorine-free bleached paper With 30 Figures ISSN 1433-0113 ISBN 978-3-211-82971-4 ISBN 978-3-7091-6510-2 (eBook) DOI 10.1007/978-3-7091-6510-2 Advances in Computing Science Springer Wien New York presents the new book series "Advances in Computing Sci ence". Its title has been chosen to emphasize its scope: "computing science" comprises all aspects of science and mathematics relating to the computing process, and has thus a much broader meaning than implied by the term "computer science". The series is ex pected to include contributions from a wide range of disciplines including, for example, numerical analysis, discrete mathematics and system theory, natural sciences, engi neering, information science, electronics, and naturally, computer science itself. Contributions in the form of monographs or collections of articles dealing with ad vances in any aspect of the computing process or its application, are welcome. They must be concise, theoretically sound and written in English; they may have resulted, e.g., from research projects, advanced workshops and conferences. The publications (of the series) should address not only the specialist in a particular field but also a more general scien tific audience. An International Advisory Board which will review papers before publication will guarantee the high standard of volumes published within this series. If you are interested in submitting work for this series please contact us: Springer-Verlag Editorial Department Sachsenplatz 4-6 A-1200Wien Austria Tel.: x4311/33024l51532 Facsimile: x43/11330242665 email: [email protected] The Publisher We dedicate this book to the memory of Ernst Schroder (1841-1902), in celebration of the first centenary of his Algebra und Logik der Relative of 1895 Preface The calculus of relations has been an important component of the development of logic and algebra since the middle of the nineteenth century, when Augustus De Morgan observed that since a horse is an animal we should be able to infer that the head of a horse is the head of an animal. For this, Aristotelian syllogistic does not suffice: We require relational reasoning. George Boole, in his Mathematical Analysis of Logic of 1847, initiated the treatment of logic as part of mathematics, specifically as part of algebra. Quite the opposite conviction was put forward early this century by Bertrand Russell and Alfred North Whitehead in their Principia Mathematica (1910 - 1913): that mathematics was essentially grounded in logic. Logic thus developed in two streams. On the one hand algebraic logic, in which the calculus of relations played a particularly prominent part, was taken up from Boole by Charles Sanders Peirce, who wished to do for the "calculus of relatives" what Boole had done for the calculus of sets. Peirce's work was in turn taken up by Schroder in his Algebra und Logik der Relative of 1895 (the third part of a massive work on the algebra of logic). Schroder's work, however, lay dormant for more than 40 years, until revived by Alfred Tarski in his seminal paper "On the calculus of binary relations" of 1941 (actually his presidential address to the Association for Symbolic Logic). Tarski's paper is still often referred to today as the best introduction to the calculus of relations. It gave rise to a whole field of study, that of relation algebras, and more generally Boolean algebras with operators. These formed part of the study of algebraic logic, which in its modern form overlaps with universal algebra, model theory, nonclassical logics, and more recently program semantics and program development. In the other stream of development, the theory of relations was accorded a key role in Principia Mathematica. This important work defined much of the subsequent development of logic in the 20th century, completely eclipsing for some time the development of algebraic logic. In this stream of development, relational calculus and relational methods appear with the development of universal algebra in the 1930's, and again with model theory from the 1950's onwards. In so far as these disciplines in turn overlapped with the development of category theory, relational methods sometimes appear in this context as well. It is fair to say that the role of the calculus of relations in the interaction between algebra and logic is by now well understood and appreciated, and that relational methods are part of the toolbox of the mathematician and the logician. Over the past twenty years relational methods have however also become of fun damental importance in computer science. For example, much of the theory of x Preface nonclassical logics was used (though sometimes re-invented) in the new so-called program logics. These arose from the realisation that a program may be thought of as an input-output relation over some state space: an accessibility relation, in the sense of modal logic, saying that from a given initial state certain final states are ac cessible. Not every relation over a state space can be thought of as a program, but any relation can be thought of as a specification of a program. This point of view, that the calculus of relations is fundamental to programs, was clearly enunciated by the Oxford group of Tony Hoare in an influential paper on "Laws of program ming" in 1987. Also during the 1980's, much of the equational theory of relation algebras were already being applied to program semantics and program develop ment. For example, the book Relations and Graphs by Schmidt and Str6hlein (in German, 1989; in English, 1993) started from the basis of programs as graphs with Boolean matrices. On the other hand, a topic such as relational databases was an essentially new development, owing little to previous mathematical work on or with relations. Thus computer science, as the new application field for relational methods, has both drawn from and contributed to previous logico/mathematical work; this is a sign of healthy development. However, the role of relational methods within computer science is not yet as well-known or well-understood as it is in logic and mathematics. It is the aim of this book to help address this situation, by giving an overview of relational methods in computer science. We have not tried to give an exhaustive survey - indeed, part of what we claim is that the topic is already too large for an exhaustive survey to fit into one volume. We hope, however, that the topics included will suffice to convey an impression of the power and wide-ranging applicability of relational methods. Just as we have attempted to bring together under one heading various dis parate endeavours in using relational methods in computer science, so we have also attempted to bring together the researchers involved. It became clear to us in the early 1990's that a core group of researchers using or working on relational methods was turning up repeatedly at various specialist conferences. It seemed a good idea, therefore, to organise a meeting specifically on relational methods, so as to give all those who developed or used them in some area of computer science a chance to meet and talk across disciplinary boundaries. The outcome of this idea was the International Seminar on Relational Methods in Computer Science (later known as RelMiCS 1), held as Seminar 9403 at SchloB Dagstuhl in the Saarland in January 1994. We gratefully acknowledge the assistance of the Internationales Begegnungs- und Forschungszentrum fur Informatik in organising and funding this Seminar. In our preface to the Seminar Report we said: Since the mid-1970's it has become clear that the calculus of relations is a fundamental conceptual and methodological tool in computer science just as much as in mathematics. A number of seemingly distinct areas ofresearch have in fact this much in common that their concepts and/or techniques come from the calculus of relations. However, it has also become clear that many opportunities for cross-pollination are being lost simply because there was no organised forum of discussion between Preface xi researchers who, though they use the same concepts and methods, nonetheless perceive themselves as working in different fields. The aim of this Dagstuhl Seminar was, therefore, to bring together researchers from various subdisciplines of computer science and math ematics, all of whom use relational methods in their work, and to en courage the creation of an active network continuing after the Seminar to exchange ideas and results. This has become a manifesto of sorts for what is now known as the RelMiCS Group. The idea of producing this book first originated at Dagstuhl, where a number of authors were recruited. Some subsequent organisational work was done from Cape Town and Miinchen, but the book only really took shape in Rio de Janeiro: first at a planning session in July 1994, then at the RelMiCS 2 meeting in July 1995. We are pleased to acknowledge our indebtedness to Armando Haeberer for or ganising these extremely pleasant and productive events. We gratefully acknowl edge the financial assistance of CNPq (Conselho Nacional de Desenvolvimento Cientffico e Tecnologico) for the planning session of July 1994, and of FAPERJ (Funda~ao de Amparo it Pesquisa do Estado do Rio de Janeiro) and IBM Brazil for RelMiCS 2 in July 1995. It gave us the chance to "workshop" the contents of the book so as to increase the homogeneity of notation and terminology that we felt was desirable. In consequence, this is a multi-author book. However, though each chapter is written by a different set of authors, it has been our intention that the book should be more than just a collection of papers: it should have unity of style and presentation. In this way we hope that the spirit of bringing together topics and researchers is reflected also in the structure of the book itself. Chapter 1 sets out the background material needed in the rest of the book, and the notation to be used. The problem of proliferation of different notations and terminology has been an impediment to communication about relational methods between various groups of researchers; it seems justified, therefore, to try, at least in a book like this, for a measure of coherence. After Chapt. 1, which forms the introductory Part I of the book, there are four more parts. Part II deals with current versions of algebras of relations, Part III with applications to logic, Part IV with applications to programming, and Part V with other application areas. For lack of space the Bibliography only contains works actually referred to in the text; a more comprehensive bibliography on the calculus of relations and its applications is available electronically. Acknowledgements. In the original submissions for this book almost all au thors acknowledged an indebtedness to other authors; we cover this by making here a blanket acknowledgement of thanks for mutual cooperation. We personally owe a large debt of thanks to Thomas Str6hlein, who undertook and carried out the arduous task of assembling a bibliography of relational methods based on submis sions from several coauthors. The bibliography at the end of this book is a small subset of this comprehensive bibliography. In addition, we gratefully acknowledge work done on the manuscript by Arne Bayer, Thomas Gritzner, and Peter Kempf. xii Preface We are grateful to Rudolf Albrecht for establishing contact with the publishers. Of course our largest debt is to the authors who actually wrote the book, and who submitted themselves with good grace to the editorial requirements we imposed on them. With over 30 contributors to this book we believe it possible that some errors may remain; for these we crave the indulgence of the reader, and would be pleased to receive feedback. October 1996 Chris Brink Wolfram Kahl, Gunther Schmidt University of Cape Town Universitiit der Bundeswehr Munchen