Finite model theory and its applications. (Q703863): Difference between revisions

As Chang and Keisler state in their classic text, model theory is ``the branch of mathematical logic which deals with the relation between a formal language and its interpretations''. In particular finite model theory, the study of finite interpretations of logical formulae, has found many applications in computer science in fields as diverse as computational complexity theory and database theory. And, what is more, finite model theory, its focus and set of available techniques, have grown with its applications in computer science and combinatorics. This volume contains, after an introductory first chapter (by S.~Weinstein), six chapters that have their origin in tutorials presented at the University of Pennsylvania during a workshop in April 1999. Therefore, the book is not meant to be a textbook on finite model theory but a selection of tutorial chapters highlighting some of the fascinating applications of the field in computer science. The contents of the chapters can be briefly summarized as follows: As already said, the first chapter serves as an introduction and discusses some common themes of the chapters to follow. Chapter 2 (by Ph.~Kolaitis) presents a study of the expressive power of logics on finite structures. It discusses a wealth of differently powerful logical languages (first- and second-order logics, logics with fixed-point operators, infinitary logics and their existential fragments) and the tools needed to characterize their classes of finite models (such as Ehrenfeucht-Fraïssé games). Chapter 3 (by E.~Grädel) studies the relationship between finite model theory and computational complexity. Starting with Fagin's Theorem, it presents logics capturing complexity classes, with a particular emphasis on fixed-point logics. Chapter 4 (by J.~Spencer) discusses 0-1 laws for first-order logic and related phenomena in the theory of random graphs. Chapter 5 (by L.~Libkin) looks at relational data over infinite sets. So-called ``constraint databases'' contain finite representations of infinite sets. This chapter studies related definability questions. Chapter 6 (by Ph.~Kolaitis and M.~Vardi) presents applications of definability theory in the area of ``constraint satisfaction problems'', a topic that has become of utmost importance in many areas of computer science (artificial intelligence, database theory, operations research) because of its unifying view of specifying many algorithmic questions. Definability questions in finite model theory here serve as a common framework for understanding many issues in this subject. The final chapter of the volume (by M.~Marx and Y.~Venema) introduces the reader to ``modal logic''. It puts an emphasis on decidability and complexity issues, in particular of the satisfiability problem for different modal systems. Every chapter has its own list of bibliographic references. The book ends with a common 7 pages index.