상세정보

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.

정보제공 :

CONTENTS
Preface = xi
1 Introduction and Overview = 1
 1.1 The Muddy Children Puzzle = 3
 1.2 An Overview of the Book = 7
2 A Model for Knowledge = 15
 2.1 The Possible-Worlds Model = 15
 2.2 Common Knowledge and Distributed Knowledge = 23
 2.3 The Muddy Children Revisited = 24
 2.4 The Properties of Knowledge = 30
 2.5 An Event-Based Approach = 36
3 Completeness and Complexity = 47
 3.1 Completeness Results = 48
 3.2 Decidability = 62
 3.3 Incorporating Common Knowledge = 66
 3.4 Incorporating Distributed Knowledge = 69
 3.5 The Complexity of the Validity Problem = 71
 3.6 NP-Completeness Results for S5 and KD45 = 74
 3.7 The First-Order Logic of Knowledge = 76
  3.7.1 First-Order Logic = 77
  3.7.2 First-Order Modal Logic = 80
  3.7.3 Assumptions on Domains = 81
  3.7.4 Properties of Knowledge in Relational Kripke Structures = 83
4 Knowledge in Multi-Agent Systems = 103
 4.1 Runs and Systems = 103
 4.2 Incorporating Knowledge = 110
 4.3 Incorporating Time = 114
 4.4 Examples of Systems = 116
  4.4.1 Knowledge Bases = 116
  4.4.2 Game Trees = 123
  4.4.3 Synchronous Systems = 127
  4.4.4 PerfectRecall = 128
  4.4.5 Message-Passing Systems = 131
  4.4.6 Asynchronous Message-Passing Systems = 133
 4.5 Knowledge Gain in A.M.P. Systems = 136
5 Protocols and Programs = 153
 5.1 Actions = 153
 5.2 Protocols and Contexts = 157
 5.3 Programs = 168
 5.4 Specifications = 170
6 Common Knowledge and Agreement = 175
 6.1 Coordinated Attack = 176
 6.2 Agreeing to Disagree = 184
 6.3 Simultaneous Byzantine Agreement = 190
 6.4 Nonrigid Sets and Common Knowledge = 197
 6.5 Attaining SBA = 201
 6.6 Attaining Common Knowledge = 207
  6.6.1 Clean Rounds = 207
  6.6.2 Waste = 209
  6.6.3 Computing Common Knowledge = 212
 6.7 Detailed Proofs = 214
7 Knowledge-Based Programming = 233
 7.1 Knowledge-Based Programs = 233
 7.2 Getting Unique Representations = 239
 7.3 Knowledge Bases Revisited = 251
 7.4 A Knowledge-Based Program for SBA = 255
 7.5 Strong Correctness = 259
 7.6 The Sequence-Transmission Problem = 262
 7.7 Proving Strong Correctness of ST = 269
8 Evolving Knowledge = 281
 8.1 Properties of Knowledge and Time = 281
 8.2 Synchrony and Perfect Recall = 285
 8.3 Knowledge and Time in A.M.P. Systems = 289
 8.4 Knowledge and Time in $$L^{oa}_n$$ ($$\Phi$$ = 290
 8.5 A Closer Look at Axiom OA$$_{n,\Phi}$$ = 295
9 Logical Omniscience = 309
 9.1 Logical Omniscience = 310
 9.2 Explicit Representation of Knowledge = 313
  9.2.1 The Syntactic Approach = 314
  9.2.2 The Semantic Approach = 316
  9.2.3 Discussion = 320
 9.3 Nonstandard Logic = 321
  9.3.1 Nonstandard Structures = 321
  9.3.2 Strong Implication = 325
  9.3.3 A Payoff: Querying Knowledge Bases = 329
  9.3.4 Discussion = 331
 9.4 Impossible Worlds = 332
 9.5 Awareness = 337
 9.6 Local Reasoning = 342
 9.7 Concluding Remarks = 347
10 Knowledge and Computation = 363
 10.1 Knowledge and Action Revisited = 363
 10.2 Algorithmic Knowledge = 366
  10.2.1 Algorithmic Systems = 366
  10.2.2 Properties of Algorithmic Knowledge = 370
 10.3 Examples = 371
 10.4 Algorithmic Programs = 374
  10.4.1 Algorithmic Programming = 374
  10.4.2 Algorithmic Knowledge and Complexity = 376
  10.4.3 Implementing Knowledge-Based Programs = 378
11 Common Knowledge Revisited = 385
 11.1 Common Knowledge as a Conjunction = 386
 11.2 Common Knowledge and Simultaneity = 388
  11.2.1 Common Knowledge and Uncertainty = 388
  11.2.2 Simultaneous Events = 391
 11.3 Temporal Imprecision = 395
 11.4 The Granularity of Time = 397
 11.5 Common Knowledge as a Fixed Point = 402
  11.5.1 Fixed Points = 402
  11.5.2 Downward Continuity and Infinite Conjunctions = 409
 11.6 Approximations of Common Knowledge = 411
  11.6.1 $$\varepsilon$$- and Eventual Common Knowledge = 412
  11.6.2 Applications to Coordinated Attack = 415
  11.6.3 Timestamped Common Knowledge = 418
  11.6.4 Other Approximations of Common Knowledge = 421
 11.7 Discussion = 421
Bibliography = 429
Index = 449
Symbol Index = 475