The articles by Moshe Y. Vardi and Allen Emerson survey aspects of modal logics of finite Kripke structures, an area of research that provides the underpinnings for computer-aided verification. Vardi's article contains an exposition of complexity results for modal logics with the aim of furnishing explanations for the robust decidability of modal logic and its variants. Finally, Toni Pitassi's article presents an overview of recent developments in algebraic proof systems for the propositional calculus, an area of research in proof complexity. Although at present this fascinating area is the least well connected to finite model theory, the connections are palpable. We anticipate that Pitassi's survey will inspire researchers in finite model theory to become involved in proof complexity and thus create further bridges.
Logic has close and deep contacts to all parts of computer science.
In the realm of computation all objects being handled and structures being created are finite, or at least finitely describable. While there has been great progress, we have come a very short distance in our ultimate goal of understanding computation. Finite model theory offers a rich, elegant, and rigorous viewpoint, which is interesting in its own right and valuable in its applications to complexity, databases, computer aided verification, as well as many other areas. We hope that this small volume will suggest directions of synergy and contact for future researchers to build upon, creating connections and making discoveries that will help explain some of the many mysteries of computation. Acknowledgements We wish to thank the organizers of the Special Year in Logic and Algorithms, Eric Allender, Bob Kurshan, and Moshe Y. Vardi, for organizing and creating a very special year indeed, as well as for entrusting us with the scientific organization and management of the workshop on Finite Models and Descriptive Complexity.