Dynamic-Epistemic Logic of Questions and Inquiry [PhD Thesis]

1 Introduction and Motivation 1
1.1 Brief History of Approaches to Questions . . . . . . . . . . . . . . 2
1.2 Main Topics in the DELQ Approach . . . . . . . . . . . . . . . . 6
1.3 Comparisons with Alternative Approaches . . . . . . . . . . . . . 11
2 Dynamic Epistemic Logic of Questions 15
2.1 Basic Logical System for DELQ . . . . . . . . . . . . . . . . . . . 15
2.1.1 Issue-Epistemic Models . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Information and Issues: Language and Semantics . . . . . 16
2.1.3 Static Logic of Information and Issues . . . . . . . . . . . 19
2.2 Dynamic Logic of Issue Management . . . . . . . . . . . . . . . . 20
2.2.1 Basic Actions of Issue Management . . . . . . . . . . . . . 20
2.2.2 Issue Management: Language and Semantics . . . . . . . 24
2.2.3 Dynamic Logic of Informational Issues . . . . . . . . . . . 25
2.3 Multi-Agent Extensions for DELQ . . . . . . . . . . . . . . . . . . 27
2.3.1 Static Multi-Agent Logic of Information and Issues . . . . 27
2.3.2 Agent-specic Questioning with Preconditions . . . . . . . 28
2.3.3 Dynamic Language, Logic, and Some Design Issues . . . . 30
2.4 Product Update for Multi-Agent DELQ . . . . . . . . . . . . . . . 31
2.4.1 A simple Motivating Example . . . . . . . . . . . . . . . . 32
2.4.2 Product Update for Questions . . . . . . . . . . . . . . . . 33
2.4.3 Dynamic Logics for Product Update . . . . . . . . . . . . 37
2.5 Temporal Protocols in DELQ . . . . . . . . . . . . . . . . . . . . 37
2.6 Long Term Protocols in Inquiry . . . . . . . . . . . . . . . . . . . 40
2.7 Appendix A: Background Denitions . . . . . . . . . . . . . . . . 44
2.8 Appendix B: Proofs of Main Results . . . . . . . . . . . . . . . . 47
3 Implementing Questioning Dynamics 49
3.1 A DEMo-like Implementation for DELQ . . . . . . . . . . . . . . . 49
3.1.1 The Syntax.lhs Module . . . . . . . . . . . . . . . . . . . 51
3.1.2 The Structures.lhs Module . . . . . . . . . . . . . . . . 53
3.1.3 The BinaryRel.lhs Module . . . . . . . . . . . . . . . . . 62
3.1.4 The Semantics.lhs Module . . . . . . . . . . . . . . . . . 63
3.1.5 The Upgrade.lhs Module . . . . . . . . . . . . . . . . . . 64
3.1.6 The DELQ.lhs Module . . . . . . . . . . . . . . . . . . . . 67
3.2 Illustrations using the Implementation . . . . . . . . . . . . . . . 69
4 Games with Questioning Moves 85
4.1 Brief History of Epistemic Games . . . . . . . . . . . . . . . . . . 86
4.1.1 Knowledge Games with Epistemic Moves . . . . . . . . . . 86
4.1.2 Time-stamped Questions in Communication . . . . . . . . 86
4.1.3 Public Announcement Games . . . . . . . . . . . . . . . . 87
4.2 Question-Answer Games . . . . . . . . . . . . . . . . . . . . . . . 88
4.3 Questioning Games with Oracles . . . . . . . . . . . . . . . . . . 94
4.3.1 Bayesian Games . . . . . . . . . . . . . . . . . . . . . . . . 103
4.4 Extensive Questioning Games . . . . . . . . . . . . . . . . . . . . 105
4.4.1 Some Preliminary Notions . . . . . . . . . . . . . . . . . . 105
4.4.2 Denitions of Main Notions . . . . . . . . . . . . . . . . . 109
4.4.3 Examples and Illustrations . . . . . . . . . . . . . . . . . . 112
4.4.4 Imperfect Information in EQGs . . . . . . . . . . . . . . . 115
4.4.5 Strategies and Solution Concepts . . . . . . . . . . . . . . 116
4.5 Strategic Abilities in Questioning . . . . . . . . . . . . . . . . . . 118
4.5.1 Describing Strategic Abilities . . . . . . . . . . . . . . . . 118
4.5.2 Conclusions and Further Research . . . . . . . . . . . . . . 121
4.6 Appendix A: Background Denitions . . . . . . . . . . . . . . . . 121
4.7 Appendix B: Proofs of Main Results . . . . . . . . . . . . . . . . 122
5 Implementing Questioning Games 125
5.1 Implementing Questioning Games . . . . . . . . . . . . . . . . . . 125
5.1.1 The QAGames.lhs Question-Answer Games Module . . . . 126
5.1.2 The PAGs.lhs Extension Module . . . . . . . . . . . . . . 130
5.2 Illustrations using the Implementation . . . . . . . . . . . . . . . 132
5.2.1 Counting Strategies . . . . . . . . . . . . . . . . . . . . . . 133
5.2.2 Computing the Outcomes . . . . . . . . . . . . . . . . . . 135
5.2.3 Counting Goals . . . . . . . . . . . . . . . . . . . . . . . . 139
5.3 Birelational Coarsest Partition Problem . . . . . . . . . . . . . . . 143
6 Querying Strategies and Probabilities 149
6.0.1 Introduction and Motivations . . . . . . . . . . . . . . . . 149
6.1 Querying Strategies in Solving Games . . . . . . . . . . . . . . . 149
6.1.1 The Location Game and its Applications . . . . . . . . . . 150
6.1.2 Solving LG and Computing Solutions Eciently . . . . . . 151
6.2 Computing NEp in LGl by QSb . . . . . . . . . . . . . . . . . . . 153
6.2.1 Solving LG by Querying Local Properties . . . . . . . . . . 153
6.2.2 Ecient Solutions as Cycles of Prole Fragments . . . . . 158
6.3 Characterizing NEp in LGl by BOc . . . . . . . . . . . . . . . . . 160
6.3.1 Local Properties Oracle Characterizing NEp . . . . . . . . 161
6.3.2 Generalizing Fragment Cycle Solution to LGl . . . . . . . 163
6.3.3 Concluding Remarks and Further Topics . . . . . . . . . . 165
6.4 Probabilistic Extensions . . . . . . . . . . . . . . . . . . . . . . . 165
6.4.1 General Probabilistic DELs . . . . . . . . . . . . . . . . . 165
6.4.2 Questioning-Related Probabilistic DELs . . . . . . . . . . 167
6.5 Minimizing under Probabilistic Bisimulation . . . . . . . . . . . . 169
6.6 Appendix A: Background Denitions . . . . . . . . . . . . . . . . 175
6.7 Appendix B: Proofs of Main Results . . . . . . . . . . . . . . . . 176
7 Implementing Querying Strategies and Probability 181
7.1 Implementation for Questioning Actions . . . . . . . . . . . . . . 181
7.2 Implementation and Illustrative Examples . . . . . . . . . . . . . 181
7.2.1 Haskell Implementation . . . . . . . . . . . . . . . . . . . 181
7.2.2 Alloy Analyzer Implementation . . . . . . . . . . . . . . . 184
7.3 Implementing Probabilistic Extensions . . . . . . . . . . . . . . . 195
7.3.1 The Probability.lhs Module . . . . . . . . . . . . . . . 196
7.3.2 The QPRO.lhs Module . . . . . . . . . . . . . . . . . . . . 199
7.3.3 Issue-Probabilistic Minimal Model . . . . . . . . . . . . . . 211
7.3.4 The Probabilistic Component . . . . . . . . . . . . . . . . 218
8 Conclusions and Outlook 221
8.1 General Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 221
8.2 Future Research and Outlook . . . . . . . . . . . . . . . . . . . . 224
Bibliography 227
Abstract 237
Acknowledgments 239