Leonid Libkin

Erich Grädel

Scott Weinstein

Moshe Y. Vardi

Joel Spencer

Phokion G. Kolaitis

Maarten Marx

Yde Venema

Finite model theory,as understoodhere, is an areaof mathematicallogic that has developed in close connection with applications to computer science, in particular the theory of computational complexity and database theory. One of the fundamental insights of mathematical logic is that our understanding of mathematical phenomena is enriched by elevating the languages we use to describe mathematical structures to objects of explicit study. If mathematics is the science of patterns, then the media through which we discern patterns, as well as the structures in which we discern them, command our attention. It isthis aspect oflogicwhichis mostprominentin model theory,“thebranchof mathematical logic which deals with the relation between a formal language and its interpretations”. No wonder, then, that mathematical logic, and ?nite model theory in particular, should ?nd manifold applications in computer science: from specifying programs to querying databases, computer science is rife with phenomena whose understanding requires close attention to the interaction between language and structure. This volume gives a broadoverviewof some central themes of ?nite model theory: expressive power, descriptive complexity, and zero–one laws, together with selected applications to database theory and arti?cial intelligence, es- cially constraint databases and constraint satisfaction problems. The ?nal chapter provides a concise modern introduction to modal logic,which emp- sizes the continuity in spirit and technique with ?nite model theory.

Finite Model Theory and Its Applications

The study of random graphs was begun in the 1960s and now has a comprehensive literature. This excellent book by one of the top researchers in the field now joins the study of random graphs (and other random discrete objects) with mathematical logic. The methodologies involve probability, discrete structures and logic, with an emphasis on discrete structures.

The Strange Logic of Random Graphs

Paul Erdös

Probabilistic Methods in combinatorics

Persi Diaconis

David Aldous

J. Michael Steele

Discrete probability theory and the theory of algorithms have become close partners over the last ten years, though the roots of this partnership go back much longer. The papers in this volume address the latest developments in this active field. They are from the IMA Workshops "Probability and Algorithms" and "The Finite Markov Chain Renaissance." They represent the current thinking of many of the world's leading experts in the field. Researchers and graduate students in probability, computer science, combinatorics, and optimization theory will all be interested in this collection of articles. The techniques developed and surveyed in this volume are still undergoing rapid development, and many of the articles of the collection offer an expositionally pleasant entree into a research area of growing importance.

Discrete Probability and Algorithms

Donald A. Dawson

Bernard Maisonneuve

CONTENTS: D.D. Dawson: Measure-valued Markov Processes.- B. Maisonneuve: Processus de Markov: Naissance, Retournement, Regeneration.- J. Spencer: Nine lectures on Random Graphs.

Ecole d'Ete de Probabilites de Saint-Flour XXI - 1991

Joel Spencer

About

Books

Join the club