Description
Book SynopsisThis book provides an introduction to formal methods based on temporal logic, describing techniques for testing and developing complex computational systems. It starts with a full introduction to the subject and then goes into more detail, covering the basics of temporal logics in order to give the reader a firm basis on which to progress further.
Trade Review“The strength of the book is the nice mixture of a pleasant to read and gentle presentation of the underlying concepts together with detailed tool descriptions (focused on a user's point of view). This book is perfectly suited for a course at senior undergraduate or beginning graduate level.” (Zentralblatt MATH, 1 December 2012)
"I highly recommend this book, both for formal methods in general and for temporal logic in particular. It will remain within my easy reach for a long time." (Computing Reviews, 1 December 2011)
Table of ContentsPreface vii
1 Introduction 1
1.1 Aims of the book 2
1.2 Why temporal logic? 3
1.3 What is temporal logic? 4
1.4 Structure of the book 6
2 Temporal logic 9
2.1 Intuition 10
2.2 Syntactic aspects 12
2.3 Semantics 14
2.4 Reactive system properties 22
2.5 What is temporal logic? 25
2.6 Normal form 28
2.7 Büchi automata and temporal logic 29
2.8 Advanced topics 37
2.9 Final exercises 47
3 Specification 49
3.1 Describing simple behaviours 49
3.2 A semantics of imperative programs 53
3.3 Linking specifications 60
3.4 Advanced topics 74
3.5 Final exercises 82
3.6 Where to next? 83
4 Deduction 85
4.1 Temporal proof 85
4.2 Clausal temporal resolution 87
4.3 The TSPASS system 108
4.4 Advanced topics 122
4.5 Final exercises 127
5 Model checking 129
5.1 Algorithmic verification 129
5.2 Automata-theoretic model checking 135
5.3 The Spin system 143
5.4 Advanced topics 171
5.5 Final exercises 181
6 Execution 185
6.1 From specifications to programs 185
6.2 MetateM: executing temporal formulae 188
6.3 The Concurrent MetateM system 211
6.4 Advanced topics 233
7 Selected applications 243
7.1 Model checking programs 243
7.2 Security protocol analysis 246
7.3 Recognizing temporal patterns 251
7.4 Parameterized systems 255
7.5 Reasoning with intervals 260
7.6 Planning 264
8 Summary 267
A Review of classical logic 269
A.1 Introduction 269
A.2 Propositional logic 271
A.3 Normal forms 276
A.4 Propositional resolution 279
A.5 Horn clauses 286
A.6 First-order logic 288
B Solutions to exercises 307
References 321
Index 349
