From the back cover: This book gives a comprehensive overview of central topics in finite model theory - expressive power of logics, descriptive complexity, and zero-one laws - together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the interaction with finite model theory. The underlying
Finite Model Theory and Its Applications by Erich Graedel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, and Scott Weinstein Springer, 2007, 437 pages, hardcover, ISBN: 978-3-540-00428-8. (Series: Texts in Theoretical Computer Science. An EATCS Series) theme of the book is the use of first-order, second-order, fixed-point, and infinitary logic, as well as various fragments of and hierarchies within these logics, to gain insight into phenomena and problems in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissi games, as a powerful way to analyze the expressive power of logics, and illustrates how sophisticated notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the applications of finite model theory to database theory and artificial intelligence. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the applications of logic to computer science. Table of contents: 1.Unifying Themes in Finite Model Theory 2.On the Expressive Power of Logics on Finite Models 3.Finite Model Theory and Descriptive Complexity 4.Logic and Random Structures 5.Embedded Finite Models and Constraint Databases 6.A Logical Approach to Constraint Satisfaction 7.Local Variations on a Loose Theme: Modal Logic and Decidability To order, see http://www.springer.com/978-3-540-00428-8