Reasoning About Knowledge (Paperback)

Description

Reasoning about knowledge -- particularly the knowledge of agents who reason about the world and each other's knowledge -- was once the exclusive province of philosophers and puzzle solvers. More recently, this type of reasoning has been shown to play a key role in a surprising number of contexts, from understanding conversations to the analysis of distributed computer algorithms.

Reasoning About Knowledge is the first book to provide a general discussion of approaches to reasoning about knowledge and its applications to distributed systems, artificial intelligence, and game theory. It brings eight years of work by the authors into a cohesive framework for understanding and analyzing reasoning about knowledge that is intuitive, mathematically well founded, useful in practice, and widely applicable. The book is almost completely self-contained and should be accessible to readers in a variety of disciplines, including computer science, artificial intelligence, linguistics, philosophy, cognitive science, and game theory. Each chapter includes exercises and bibliographic notes.

Ronald Fagin is Manager of the Foundations of Computer Science Group, Computer Science Department, IBM Almaden Research Center.

Joseph Y. Halpern is Professor of Computer Science at Cornell University.

Yoram Moses is Associate Professor in the Electrical Engineering Department at Technion-Israel Institute of Technology.

Moshe Y. Vardi is Karen Ostrum George Professor in Computational Engineering and Chair of the Computer Science Department, Rice University.

Table of Contents

Preface to the Hardcover Edition xi 
 
Preface to the Paperback Edition xv
 
1 Introduction and Overview 1
 
2 A Model for Knowledge 15
 
3 Completeness and Complexity 49
 
4 Knowledge in Multi-Agent Systems 109
 
5 Protocols and Programs 163
 
6 Common Knowledge and Agreement 189
 
7 Knowledge-Based Programming 253
 
8 Evolving Knowledge 303
 
9 Logical Omniscience 333
 
10 Knowledge and Computation 391
 
11 Common Knowledge Revisited 415
 
 Bibliography 463
 
 Symbol Index 489
 
 Index 493