Preface......Page 7
Contents of the Book and Organization of the Material......Page 8
Acknowledgements......Page 11
Contents......Page 13
Abbreviations and Notation......Page 17
1.1 Introduction and Motivation......Page 19
1.2 State Estimation and Event Inference......Page 20
1.3 Examples of Applications......Page 22
1.4 Book Coverage......Page 28
1.5 Comments and Further Reading......Page 29
References......Page 31
2.1 Set Theory......Page 33
2.2 Relations......Page 35
2.3 Alphabets, Strings, and Languages......Page 36
2.4 Miscellaneous Notation......Page 40
References......Page 41
3.2.1 Finite Automata......Page 42
3.2.2 Languages......Page 60
3.3.1 Finite Automata Without Silent Transitions......Page 64
3.3.2 Finite Automata with Silent Transitions......Page 72
3.3.3 Unobservable Reach......Page 82
References......Page 84
4.1 Introduction and Motivation......Page 86
4.2.1 State Estimation in DFA Without Silent Transitions......Page 90
4.2.2 State Estimation in DFA with Silent Transitions......Page 92
4.3 Intuitive Discussion on Current-State Estimation......Page 95
4.4.1 State Mappings and State Trajectories......Page 99
4.4.2 Induced State Mappings......Page 104
4.4.3 Induced State Trajectories......Page 106
4.4.4 Tracking Induced State Trajectories via Trellis Diagrams......Page 108
4.5 State Estimation......Page 114
4.5.1 Current-State Estimation......Page 117
4.5.2 Delayed-State EstimationβSmoothing......Page 119
4.5.3 Initial-State Estimation......Page 123
4.6 Extensions to Nondeterministic Finite Automata......Page 125
4.7 Observation Equivalence......Page 128
4.8 Complexity of Recursive State Estimation......Page 131
4.9 Comments and Further Reading......Page 132
References......Page 133
5.1 Introduction and Motivation......Page 135
5.1.2 Testing of Digital Circuits......Page 138
5.1.3 Fault Diagnosis......Page 139
5.1.4 State-Based Notions of Opacity......Page 145
5.2 Current-State Isolation Using the Current-State Estimator......Page 146
5.3 Delayed-State Isolation Using the Delayed-State Estimator......Page 152
5.4 Initial-State Isolation Using the Initial-State Estimator......Page 161
5.5 Comments and Further Reading......Page 168
References......Page 169
6.1 Introduction and Motivation......Page 170
6.2 Notions of Detectability......Page 171
6.2.1 Detectability......Page 173
6.2.2 Initial-State and D-Delayed-State Detectability......Page 178
6.3 Verification of Detectability......Page 179
6.4 Verification of Strong Detectability Using the Detector......Page 181
6.5 Extensions to K-Detectability and Verification Using the K-Detector......Page 183
6.5.1 K-Detectability......Page 184
6.5.2 Verification of K-Detectability......Page 185
6.6 Synchronizing, Homing, and Distinguishing Sequences......Page 187
6.7 Comments and Further Reading......Page 195
References......Page 196
7.1 Introduction and Motivation......Page 199
7.2.1 Problem Formulation: Fault Inference from a Sequence of Observations......Page 200
7.2.2 Reduction of Fault Diagnosis to State Isolation......Page 206
7.3 Verification of Diagnosability......Page 218
7.3.1 Diagnoser Construction......Page 220
7.3.2 Verifier Construction......Page 224
7.4 Comments and Further Reading......Page 232
References......Page 235
8.1 Introduction and Motivation......Page 238
8.2 Language-Based Opacity......Page 242
8.3.1 Current-State Opacity......Page 244
8.3.2 Initial-State Opacity......Page 251
8.3.3 Delayed-State Opacity......Page 256
8.4 Complexity Considerations......Page 257
8.5 Comments and Further Reading......Page 258
References......Page 261
9.1 Introduction and Motivation......Page 263
9.2 System Modeling and Observation Architecture......Page 264
9.3 Decentralized Information Processing......Page 266
9.4 Totally Ordered Versus Partially Ordered Sequences of Observations......Page 270
9.5 Case I: Partial-Order-Based Estimation......Page 274
9.5.1 Simplified Setting: Two Observation Sites......Page 275
9.5.2 General Setting: Multiple Observation Sites......Page 280
9.6 Case II: Set Intersection-Based Estimation......Page 284
9.7 Case III: Processing of Local Decisions......Page 286
9.8 Examples......Page 287
9.9 Synchronization Strategies......Page 294
9.9.1 Synchronizing Automata......Page 295
9.9.2 Limitations of Finite Memory Observers......Page 298
9.10.1 Verification of Diagnosability......Page 300
9.10.2 Verification of Detectability......Page 308
9.11 Comments and Further Reading......Page 313
References......Page 315
10.1 Introduction and Motivation......Page 316
10.2 System Modeling and Observation Architecture......Page 317
10.3 Distributed Information Processing......Page 319
10.4 Synchronization Strategies......Page 322
10.5 Distributed Protocols with a Coordinator......Page 326
10.5.1 Run-Time Execution of Case II Distributed Protocol with a Coordinator......Page 328
10.5.2 Verification of Case II Distributed Diagnosability with a Coordinator......Page 334
10.6 Distributed Protocols Without a Coordinator......Page 339
10.6.1 Run-Time Execution of Case II Distributed Protocol Without a Coordinator......Page 340
10.6.2 Verification of Case II Distributed Diagnosability Without a Coordinator......Page 347
10.7 Comments and Further Reading......Page 351
References......Page 352
Index......Page 354