Books
Lectures in Game Theory for Computer Scientists
K. Apt and E. Grädel (Eds.)
Cambridge University Press, 2011
Games provide mathematical models for interaction. Numerous tasks in computer science can be formulated in game-theoretic terms. This fresh and intuitive way of thinking through complex issues reveals underlying algorithmic questions and clarifies the relationships between different domains. This collection of lectures, by specialists in the field, provides an excellent introduction to various aspects of game theory relevant for applications in computer science that concern program design, synthesis, verification, testing and design of multi-agent or distributed systems. Originally devised for a Spring School organised by the GAMES Networking Programme in 2009, these lectures have since been revised and expanded, and range from tutorials concerning fundamental notions and methods to more advanced presentations of current research topics. This volume is a valuable guide to current research on game-based methods in computer science for undergraduate and graduate students. It will also interest researchers working in mathematical logic, computer science and game theory.
Logic and Automata: History and Perspectives
J. Flum, E. Grädel, and Th. Wilke (Eds.)
Texts in Logic and Games, Amsterdam University Press, 2007
Mathematical logic and automata theory are two scientific disciplines with a close relationship that is not only fundamental for many theoretical results but also forms the basis of a coherent methodology for the verification and synthesis of computing systems. We take the occasion of the 60th birthday of Wolfgang Thomas to present a tour d'horizon on automata theory and logic. The twenty papers assembled in this volume cover many different facets of logic and automata theory, emphasize the connections to other disciplines such as complexity theory, games, algorithms, and semigroup theory, and discuss current challenges in this field.
Finite Model Theory and Its Applications
E. Grädel, Ph. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, Y. Venema, and S. Weinstein
EATCS Series: Texts in Theoretical Computer Science, Springer-Verlag, 2007
This book gives a broad overview of core topics of finite model theory: expressive power, descriptive complexity, and zero-one laws, together with selected applications to database theory and artificial intelligence, especially, constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, which emphasizes the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of, and hierarchies within, first order, second order, fixed point, and infinitary logics to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful technique for analyzing the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and tree-width, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research in finite model theory, and all readers will experience the excitement of a vibrant area of application of logic to computer science.
Read a review on this book (appeared in Computer Science Review 2 (2008), pp. 55–59)
Automata, Logics, and Infinite Games
E. Grädel, W. Thomas, and Th. Wilke (Eds.)
Lecture Notes in Compter Science, Springer-Verlag, 2002
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 Classical Decision Problem
E. Börger, E. Grädel, and Y. Gurevich
Springer-Verlag, 1997
This is the most comprehensive treatment available in book form of the classical decision problem of mathematical logic and of the role of the classical decision problem in modern computer science. A revealing analysis of the natural order of decidable and undecidable cases is given. The complete classification of the solvable and unsolvable standard cases of the classical decision problem will be of particular interest to the reader. The classification comes complete with the complexity analysis of the solvable cases, with the comprehensive treatment of the reduction method, and with the model-theoretical analysis of solvable cases. Many cases are treated here for the first time, and a great number of simple proofs and exercises have been included. The results and methods of the book are extensively used in logic, computer science and artificial intelligence.