Search

Program construction is about turning specifications of computer software into implementations. Recent research aimed at improving the process of program construction exploits insights from abstract algebraic tools such as lattice theory, fixpoint calculus, universal algebra, category theory, and allegory theory.This textbook-like tutorial presents, besides an introduction, eight coherently written chapters by leading authorities on ordered sets and complete lattices, algebras and coalgebras, Galois connections and fixed point calculus, calculating functional programs, algebra of program termination, exercises in coalgebraic specification, algebraic methods for optimization problems, and temporal algebra.

AMAST's goal is to advance awareness of algebraic and logical methodology as part of the fundamental basis of software technology. Ten years and seven conferences after the start of the AMAST movement, I believe we are attaining this. The movement has propagated throughout the world, assembling many enthusiastic specialists who have participated not only in the conferences, which are now annual, but also in the innumerable other activities that AMAST promotes and supports. We are now facing the Seventh International Conference on Algebraic Methodology and Software Technology (AMAST'98). The previous meetings were held in Iowa City, USA (1989 and 1991), in Enschede, The Netherlands (1993), in Montreal, Canada (1995), in Munich, Germany (1996), and in Sydney, Australia (1997). This time it is Brazil's turn, in a very special part of this colorful country – Amazonia. Thus, “if we have done more it is by standing on the shoulders of giants.” The effort started by Teodor Rus, Arthur Fleck, and William A. Kirk at AMAST'89 was consolidated in AMAST'91 by Teodor Rus, Maurice Nivat, Charles Rattray, and Giuseppe Scollo. Then came modular construction of the building, wonderfully carried out by Giuseppe Scollo, Vangalur Alagar, Martin Wirsing, and Michael Johnson, as Program Chairs of the AMAST conferences held between 1993 and 1997.

The AMAST movement was initiated in 1989 with the First International C- ference on Algebraic Methodology and Software Technology (AMAST), held on May 21{23in Iowa City, Iowa,and aimed at setting the development of software technology on a mathematical basis. The virtue of the software technology en- sioned by AMAST is the capability to produce software that has the following properties: (a) it is correct and its correctness can be proved mathematically, (b) it is safe, such that it can be used in the implementation of critical systems, (c) it is portable, i. e., it is independent of computing platforms and language generations, and (d) it is evolutionary, i. e., it is self-adaptable and evolves with the problem domain. Ten years later a myriad of workshops, conferences, and researchprogramsthat sharethe goalsof the AMAST movementhaveoccurred. This can be taken as proof that the AMAST vision is right. However, often the myriad of workshops, conferences, and research programs lack the clear obj- tives and the coordination of their goals towards the software technology en- sioned by AMAST. This can be taken as a proof that AMAST is still necessary.

This volume contains the proceedings of AMAST 2002, the 9th International Conference on Algebraic Methodology and Software Technology, held during September 9–13, 2002, in Saint-Gilles-les-Bains, R´eunion Island, France. The major goal of the AMAST conferences is to promote research that may lead to setting software technology on a?rm mathematical basis. This goal is achieved through a large international cooperation with contributions from both academia and industry. Developing a software technology on a mathematical basis p- duces software that is: (a) correct, and the correctness can be proved mathem- ically, (b) safe, so that it can be used in the implementation of critical systems, (c) portable, i. e., independent of computing platforms and language generations, (d) evolutionary, i. e., it is self-adaptable and evolves with the problem domain. All previous AMAST conferences, which were held in Iowa City (1989, 1991), Twente (1993), Montreal (1995), Munich (1996), Sydney (1997), Manaus (1999), and Iowa City (2000), made contributions to the AMAST goals by reporting and disseminating academic and industrial achievements within the AMAST area of interest. During these meetings, AMAST attracted an international following among researchers and practitioners interested in software technology, progr- ming methodology, and their algebraic, and logical foundations.

This book constitutes the refereed proceedings of the 5th Workshop on Algorithm Engineering, WAE 2001, held in Aarhus, Denmark, in August 2001. The 15 revised full papers presented were carefully reviewed and selected from 25 submissions. Among the topics addressed are implementation, experimental testing, and fine-tuning of discrete algorithms; novel use of discrete algorithms in other disciplines; empirical research on algorithms and data structures; and methodological issues regarding the process of converting user requirements into efficient algorithmic solutions and implemenations.

This volume contains the papers presented at the 12th Annual Conference on Algorithmic Learning Theory (ALT 2001), which was held in Washington DC, USA, during November 25–28, 2001. The main objective of the conference is to provide an inter-disciplinary forum for the discussion of theoretical foundations of machine learning, as well as their relevance to practical applications. The conference was co-located with the Fourth International Conference on Discovery Science (DS 2001). The volume includes 21 contributed papers. These papers were selected by the program committee from 42 submissions based on clarity, signi?cance, o- ginality, and relevance to theory and practice of machine learning. Additionally, the volume contains the invited talks of ALT 2001 presented by Dana Angluin of Yale University, USA, Paul R. Cohen of the University of Massachusetts at Amherst, USA, and the joint invited talk for ALT 2001 and DS 2001 presented by Setsuo Arikawa of Kyushu University, Japan. Furthermore, this volume includes abstracts of the invited talks for DS 2001 presented by Lindley Darden and Ben Shneiderman both of the University of Maryland at College Park, USA. The complete versions of these papers are published in the DS 2001 proceedings (Lecture Notes in Arti?cial Intelligence Vol. 2226).

This volume contains the papers presented at the 13th Annual Conference on Algorithmic Learning Theory (ALT 2002), which was held in Lub ¨ eck (Germany) during November 24–26, 2002. The main objective of the conference was to p- vide an interdisciplinary forum discussing the theoretical foundations of machine learning as well as their relevance to practical applications. The conference was colocated with the Fifth International Conference on Discovery Science (DS 2002). The volume includes 26 technical contributions which were selected by the program committee from 49 submissions. It also contains the ALT 2002 invited talks presented by Susumu Hayashi (Kobe University, Japan) on “Mathematics Based on Learning”, by John Shawe-Taylor (Royal Holloway University of L- don, UK) on “On the Eigenspectrum of the Gram Matrix and Its Relationship to the Operator Eigenspectrum”, and by Ian H. Witten (University of Waikato, New Zealand) on “Learning Structure from Sequences, with Applications in a Digital Library” (joint invited talk with DS 2002). Furthermore, this volume - cludes abstracts of the invited talks for DS 2002 presented by Gerhard Widmer (Austrian Research Institute for Arti?cial Intelligence, Vienna) on “In Search of the Horowitz Factor: Interim Report on a Musical Discovery Project” and by Rudolf Kruse (University of Magdeburg, Germany) on “Data Mining with Graphical Models”. The complete versions of these papers are published in the DS 2002 proceedings (Lecture Notes in Arti?cial Intelligence, Vol. 2534). ALT has been awarding the E.

This volume contains all the papers presented at the Ninth International Con- rence on Algorithmic Learning Theory (ALT'98), held at the European education centre Europ¨aisches Bildungszentrum (ebz) Otzenhausen, Germany, October 8{ 10, 1998. The Conference was sponsored by the Japanese Society for Arti cial Intelligence (JSAI) and the University of Kaiserslautern. Thirty-four papers on all aspects of algorithmic learning theory and related areas were submitted, all electronically. Twenty-six papers were accepted by the program committee based on originality, quality, and relevance to the theory of machine learning. Additionally, three invited talks presented by Akira Maruoka of Tohoku University, Arun Sharma of the University of New South Wales, and Stefan Wrobel from GMD, respectively, were featured at the conference. We would like to express our sincere gratitude to our invited speakers for sharing with us their insights on new and exciting developments in their areas of research. This conference is the ninth in a series of annual meetings established in 1990. The ALT series focuses on all areas related to algorithmic learning theory including (but not limited to): the theory of machine learning, the design and analysis of learning algorithms, computational logic of/for machine discovery, inductive inference of recursive functions and recursively enumerable languages, learning via queries, learning by arti cial and biological neural networks, pattern recognition, learning by analogy, statistical learning, Bayesian/MDL estimation, inductive logic programming, robotics, application of learning to databases, and gene analyses.

The papers in this volume were presented at the Fourth Italian Conference on Algorithms and Complexity (CIAC 2000). The conference took place on March 1-3, 2000, in Rome (Italy), at the conference center of the University of Rome \La Sapienza'. This conference was born in 1990 as a national meeting to be held every three years for Italian researchers in algorithms, data structures, complexity, and parallel and distributed computing. Due to a signi cant participation of foreign reaserchers, starting from the second conference, CIAC evolved into an international conference. In response to the call for papers for CIAC 2000, there were 41 subm- sions, from which the program committee selected 21 papers for presentation at the conference. Each paper was evaluated by at least three program committee members. In addition to the selected papers, the organizing committee invited Giorgio Ausiello, Narsingh Deo, Walter Ruzzo, and Shmuel Zaks to give plenary lectures at the conference. We wish to express our appreciation to all the authors of the submitted papers, to the program committee members and the referees, to the organizing committee, and to the plenary lecturers who accepted our invitation.

The papers in this volume were selected for presentation at the Eleventh Annual International Symposium on Algorithms and Computation (ISAAC 2000), held on 18{20 December, 2000 at the Institute of Information Science, Academia Sinica, Taipei, Taiwan. Previous meetings were held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), and Chennai (1999). Submissions to the conference this year were conducted entirely electro- cally. Thanks to the excellent software developed by the Institute of Information Science, Academia Sinica, we were able to carry out virtually all communication via the World Wide Web. In response to the call for papers, a total of 87 extended abstracts were submitted from 25 countries. Each submitted paper was handled by at least three program committee members, with the assistance of a number of external reviewers, as indicated by the referee list found in the proceedings. There were many more acceptable papers than there was space available in the symposium program, which made the program committee's task extremely di cult. Finally 46 papers were selected for presentation at the Symposium. In addition to these contributed papers, the conference also included two invited presentations by Dr. Jean-Daniel Boissonnat, INRIA Sophia-Antipolis, France and Professor Jin-Yi Cai, University of Wisconsin at Madison, Wisconsin, USA. It is expected that most of the accepted papers will appear in a more complete form in scienti c journals.

The papers in this volume were presented at the Sixth Workshop on Algorithms and Data Structures (WADS'99). The workshop took place August 11 - 14, 1999, in Vancouver, Canada. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT'88 and WADS'89. In response to the program committee's call for papers, 71 papers were submitted. From these submissions, the program committee selected 32 papers for presentation at the workshop. In addition to these submitted papers, the program committee invited the following researchers to give plenary lectures at the workshop: C. Leiserson, N. Magnenat-Thalmann, M. Snir, U. Vazarani, and 1. Vitter. On behalf of the program committee, we would like to express our appreciation to the six plenary lecturers who accepted our invitation to speak, to all the authors who submitted papers to W ADS'99, and to the Pacific Institute for Mathematical Sciences for their sponsorship. Finally, we would like to express our gratitude to all the people who reviewed papers at the request of the program committee. August 1999 F. Dehne A. Gupta J.-R. Sack R. Tamassia VI Conference Chair: A. Gupta Program Committee Chairs: F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia Program Committee: A. Andersson, A. Apostolico, G. Ausiello, G. Bilardi, K. Clarkson, R. Cleve, M. Cosnard, L. Devroye, P. Dymond, M. Farach-Colton, P. Fraigniaud, M. Goodrich, A.

This book constitutes the refereed proceedings of the 9th Annual European Symposium on Algorithms, ESA 2001, held in Aarhus, Denmark, in August 2001.The 41 revised full papers presented together with three invited contributions were carefully reviewed and selected from 102 submissions. The papers are organized in topical sections on caching and prefetching, online algorithms, data structures, optimization and approximation, sequences, scheduling, shortest paths, geometry, distributed algorithms, graph algorithms, pricing, broadcasting and multicasting, graph labeling and graph drawing, and graphs.

The 7th Annual European Symposium on Algorithms (ESA'99) is held in Prague, Czech Republic, July 16-18, 1999. This continued the tradition of the meetings which were held in – 1993 Bad Honnef (Germany) – 1994 Utrecht (Netherlands) – 1995 Corfu (Greece) – 1996 Barcelona (Spain) – 1997 Graz (Austria) – 1998 Venice (Italy) (The proceedingsof previousESA meetings were publishedas Springer LNCS v- umes 726, 855, 979, 1136, 1284, 1461.) In the short time of its history ESA (like its sister meeting SODA) has become a popular and respected meeting. The call for papers stated that the “Symposium covers research in the use, design, and analysis of ef?cient algorithms and data structures as it is carried out in c- puter science, discrete applied mathematics and mathematical programming. Papers are solicited describing original results in all areas of algorithmic research, including but not limited to: Approximation Algorithms; Combinatorial Optimization; Compu- tional Biology; Computational Geometry; Databases and Information Retrieval; Graph and Network Algorithms; Machine Learning; Number Theory and Computer Algebra; On-line Algorithms; Pattern Matching and Data Compression; Symbolic Computation.

We are pleased to present the proceedings of the Second Workshop on Al- rithms in Bioinformatics (WABI 2002), which took place on September 17-21, 2002 in Rome, Italy. The WABI workshop was part of a three-conference me- ing, which, in addition to WABI, included the ESA and APPROX 2002. The three conferences are jointly called ALGO 2002, and were hosted by the F- ulty of Engineering, University of Rome “La Sapienza”. Seehttp://www.dis. uniroma1.it/˜algo02 for more details. The Workshop on Algorithms in Bioinformatics covers research in all areas of algorithmic work in bioinformatics and computational biology. The emphasis is on discrete algorithms that address important problems in molecular biology, genomics,andgenetics,thatarefoundedonsoundmodels,thatarecomputati- ally e?cient, and that have been implemented and tested in simulations and on real datasets. The goal is to present recent research results, including signi?cant work in progress, and to identify and explore directions of future research. Original research papers (including signi?cant work in progress) or sta- of-the-art surveys were solicited on all aspects of algorithms in bioinformatics, including, but not limited to: exact and approximate algorithms for genomics, genetics, sequence analysis, gene and signal recognition, alignment, molecular evolution, phylogenetics, structure determination or prediction, gene expression and gene networks, proteomics, functional genomics, and drug design.

This book constitutes the refereed proceedings of the Third International Workshop on Ant Algorithms, ANTS 2002, held in Brussels, Belgium in September 2002.The 17 revised full papers, 11 short papers, and extended poster abstracts presented were carefully reviewed and selected from 52 submissions. The papers deal with theoretical and foundational aspects and a variety of new variants of ant algorithms as well as with a broad variety of optimization applications in networking and operations research. All in all, this book presents the state of the art in research and development in the emerging field of ant algorithms

This volume contains the proceedings of the 19th annual International Conference on Application and Theory of Petri Nets. The aim of the Petri net conference is to create a forum for the dissemination of the latest results in the application and theory of Petri nets. It always takes place in the last week of June. Typically there are 150 - 200 participants. About one third of these come from industry while the rest are from universities and research institutions. The conferences and a number of other activities are coordinated by a steering committee with the following members: G. Balbo (Italy), J. Billington (Australia), G. DeMichelis(Italy),C. Girault(France),K. Jensen (Denmark), S. Kumagai (Japan), T. Murata (USA), C. A. Petri (Germany; honorary member), W. Reisig (Germany), G. Roucairol (France), G. Rozenberg (The Netherlands; chairman), M. Silva (Spain). The 19th conference has been organized for the rst time in Portugal, by the Department of Electrical Engineering of the Faculty of Sciences and Technology of the New University of Lisbon, together with the Center for Intelligent Robotics of UNINOVA. It takes place in Lisbon at the same time as EXPO'98, the last world exhibition of the 20th century.

This book constitutes the joint refereed proceedings of six workshops, EvoWorkshops 2003, held together with EuroGP 2003 in Essex, UK in April 2003. The 63 revised full papers presented were carefully reviewed and selected from a total of 109 submissions. In accordance with the six workshops covered, the papers are organized in topical sections on bioinformatics, combinatorial optimization, image analysis and signal processing, evolutionary music and art, evolutionary robotics, and scheduling and timetabling.

This book constitutes the thoroughly refereed post-proceedings of the International Workshop on Graph Transformation with Industrial Relevance, AGTIVE'99, held in Kerkrade, The Netherlands, in June 1999.The 28 revised full papers presented went through an iterated process of reviewing and revision. Also included are three invited papers, 10 tool demonstrations, a summary of a panel discussion, and lists of graph transformation systems and books on graph transformations. The papers are organized in sections on modularization concepts, distributed systems modeling, software architecture: evolution and reengineering, visual graph transformation languages, visual language modeling and tool development, knowledge modeling, image recognition and constraint solving, process modeling and view integration, and visualization and animation tools.

This book constitutes the refereed proceedings of the 19th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-13, held in Honolulu, Hawaii, USA in November 1999.The 42 revised full papers presented together with six invited survey papers were carefully reviewed and selected from a total of 86 submissions. The papers are organized in sections on codes and iterative decoding, arithmetic, graphs and matrices, block codes, rings and fields, decoding methods, code construction, algebraic curves, cryptography, codes and decoding, convolutional codes, designs, decoding of block codes, modulation and codes, Gröbner bases and AG codes, and polynomials.

This book is based on material presented at the international summer school on Applied Semantics that took place in Caminha, Portugal, in September 2000. We aim to present some recent developments in programming language research, both in semantic theory and in implementation, in a series of graduate-level lectures. The school was sponsored by the ESPRIT Working Group 26142 on Applied Semantics(APPSEM),whichoperatedbetweenApril1998andMarch2002.The purpose of this working group was to bring together leading reseachers, both in semantic theory and in implementation, with the speci?c aim of improving the communication between theoreticians and practitioners. TheactivitiesofAPPSEMwerestructuredintonineinterdisciplinarythemes: A: Semantics for object-oriented programming B: Program structuring C: Integration of functional languages and proof assistants D: Veri?cation methods E: Automatic program transformation F: Games, sequentiality, and abstract machines G: Types and type inference in programming H: Semantics-based optimization I: Domain theory and real number computation These themes were identi?ed as promising for pro?table interaction between semantic theory and practice, and were chosen to contribute to the following general topics: – description of existing programming language features; – design of new programming language features; – implementation and analysis of programming languages; – transformation and generation of programs; – veri?cation of programs. The chapters in this volume give examples of recent developments covering a broad range of topics of interest to APPSEM.

The Evolution Arti?cielle cycle of conferences was originally initiated as a forum for the French-speaking evolutionary computation community. Previous EA m- tings were held in Toulouse (EA'94), Brest (EA'95, LNCS 1063), Nˆ?mes (EA'97, LNCS 1363), Dunkerque (EA'99, LNCS 1829), and?nally, EA 2001 was hosted by the Universit´e de Bourgogne in the small town of Le Creusot, in an area of France renowned for its excellent wines. However, the EA conferences have been receiving more and more papers from the international community: this conference can be considered fully internat- nal, with 39submissions from non-francophonic countries on all?ve continents, out of a total of 68. Out of these 68 papers, only 28 were presented orally (41%) due to the formula of the conference (single session with presentations of 30 minutes) that all participants seem to appreciate a lot. The Organizing Committee wishes to thank the members of the International Program Committee for their hard work (mainly due to the large number of submissions) and for the service they rendered to the community by ensuring the high scienti?c content of the papers presented. Actually, the overall quality of the papers presented was very high and all 28 presentations are included in this volume, grouped in 8 sections which more or less re?ect the organization of the oral session: 1. Invited Paper: P. Bentley gave a great talk on his classi?cation of int- disciplinary collaborations, and showed us some of his work with musicians and biologists.

In many ways, our immune systems are as complex as our brains. They learn, predict, remember and adapt, protecting us from the maelstrom of pathogens that infect us daily. Computer Science frequently takes inspiration from the seemingly endless capabilities of natural systems. It should therefore be no s- prise that, like the?eld of Arti?cial Neural Networks inspired from brains, we now have a vigorous?eld of research known as Arti?cial Immune Systems (AIS), inspired by our own immune systems. Although still relatively new, the previous 10 years has seen the paradigm of AIS rapidly establish itself as an important biological metaphor. Researchers all over the world fruitfully exploit “immunological ideas” in many di?erent ways to provide mechanisms for tackling a wide variety of applications. In this volume we present the proceedings of ICARIS 2003, the 2nd Int- national Conference on Arti?cial Immune Systems. This was the second int- national conference entirely dedicated to the?eld, and followed the extremely successful?rst conference held in Canterbury, UK in 2002. The number and - versityofpapersinthisyear'sconferenceisatributetotheever-growingnumber ofresearchersinthearea,andrepresentativeofthesolidfoundationofworkthat now exists in this area. The range of topics considered is wide. For example, at one end of the spectrum we see a selection of papers providing a necessary t- oretical grounding for the?eld. At the other end, we have an exciting range of applications to real-world problems, covering, for example, job-shop scheduling and fault detection in refrigeration systems.

This book constitutes the refereed proceedings of the joint International Conference on Artificial Neural Networks and International Conference on Neural Information Processing, ICANN/ICONIP 2003, held in Istanbul, Turkey, in June 2003. The 138 revised full papers were carefully reviewed and selected from 346 submissions. The papers are organized in topical sections on learning algorithms, support vector machine and kernel methods, statistical data analysis, pattern recognition, vision, speech recognition, robotics and control, signal processing, time-series prediction, intelligent systems, neural network hardware, cognitive science, computational neuroscience, context aware systems, complex-valued neural networks, emotion recognition, and applications in bioinformatics.

This book is based on the papers presented at the International Conference on Arti?cial Neural Networks, ICANN 2001, from August 21–25, 2001 at the - enna University of Technology, Austria. The conference is organized by the A- trian Research Institute for Arti?cal Intelligence in cooperation with the Pattern Recognition and Image Processing Group and the Center for Computational - telligence at the Vienna University of Technology. The ICANN conferences were initiated in 1991 and have become the major European meeting in the?eld of neural networks. From about 300 submitted papers, the program committee selected 171 for publication. Each paper has been reviewed by three program committee m- bers/reviewers. We would like to thank all the members of the program comm- tee and the reviewers for their great e?ort in the reviewing process and helping us to set up a scienti?c program of high quality. In addition, we have invited eight speakers; three of their papers are also included in the proceedings. We would like to thank the European Neural Network Society (ENNS) for their support. We acknowledge the?nancial support of Austrian Airlines, A- trian Science Foundation (FWF) under the contract SFB 010, Austrian Society ¨ for Arti?cial Intelligence (OGAI), Bank Austria, and the Vienna Convention Bureau. We would like to express our sincere thanks to A. Flexer, W. Horn, K. Hraby, F. Leisch, C. Schittenkopf, and A. Weingessel. The conference and the proceedings would not have been possible without their enormous contri- tion.

The International Conferences on Arti?cial Neural Networks, ICANN, have been held annually since 1991 and over the years have become the major European meeting in neural networks. This proceedings volume contains all the papers presented at ICANN 2002, the 12th ICANN conference, held in August 28– 30, 2002 at the Escuela T´ecnica Superior de Inform´atica of the Universidad Aut´onoma de Madrid and organized by its Neural Networks group. ICANN 2002 received a very high number of contributions, more than 450. Almost all papers were revised by three independent reviewers, selected among the more than 240 serving at this year's ICANN, and 221 papers were?nally selected for publication in these proceedings (due to space considerations, quite a few good contributions had to be left out). I would like to thank the Program Committee and all the reviewers for the great collective e?ort and for helping us to have a high quality conference.

This book constitutes the refereed proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP 2000, held in Geneva, Switzerland in July 2000. The 69 revised full papers presented together with nine invited contributions were carefully reviewed and selected from a total of 196 extended abstracts submitted for the two tracks on algorithms, automata, complexity, and games and on logic, semantics, and programming theory. All in all, the volume presents an unique snapshot of the state-of-the-art in theoretical computer science.

The refereed proceedings of the 30th International Colloquium on Automata, Languages and Programming, ICALP 2003, held in Eindhoven, The Netherlands in June/July 2003. The 84 revised full papers presented together with six invited papers were carefully reviewed and selected from 212 submissions. The papers are organized in topical sections on algorithms, process algebra, approximation algorithms, languages and programming, complexity, data structures, graph algorithms, automata, optimization and games, graphs and bisimulation, online problems, verification, the Internet, temporal logic and model checking, graph problems, logic and lambda-calculus, data structures and algorithms, types and categories, probabilistic systems, sampling and randomness, scheduling, and geometric problems.

A central aim and ever-lasting dream of computer science is to put the development of hardware and software systems on a mathematical basis which is both firm and practical. Such a scientific foundation is needed especially for the construction of reactive programs, like communication protocols or control systems. For the construction and analysis of reactive systems an elegant and powerful theory has been developed based on automata theory, logical systems for the specification of nonterminating behavior, and infinite two-person games. The 19 chapters presented in this multi-author monograph give a consolidated overview of the research results achieved in the theory of automata, logics, and infinite games during the past 10 years. Special emphasis is placed on coherent style, complete coverage of all relevant topics, motivation, examples, justification of constructions, and exercises.

The First CADE in the Third Millennium This volume contains the papers presented at the Eighteenth International C- ference on Automated Deduction (CADE-18) held on July 27–30th, 2002, at the University of Copenhagen as part of the Federated Logic Conference (FLoC 2002). Despite a large number of deduction-related conferences springing into existence at the end of the last millennium, the CADE conferences continue to be the major forum for the presentation of new research in all aspects of automated deduction. CADE-18 was sponsored by the Association for Auto- ted Reasoning, CADE Inc., the Department of Computer Science at Chalmers University, the Gesellschaft fur ¨ Informatik, Safelogic AB, and the University of Koblenz-Landau. There were 70 submissions, including 60 regular papers and 10 system - scriptions. Each submission was reviewed by at least?ve program committee members and an electronic program committee meeting was held via the Int- net. The committee decided to accept 27 regular papers and 9 system descr- tions. One paper switched its category after refereeing, thus the total number of system descriptions in this volume is 10. In addition to the refereed papers, this volume contains an extended abstract of the CADE invited talk by Ian Horrocks, the joint CADE/CAV invited talk by Sharad Malik, and the joint CADE-TABLEAUX invited talk by Matthias Baaz. One more invited lecture was given by Daniel Jackson.