Complexity of Modal Logics [PhD Thesis]

Cover ......Page 1
Dankwoord ......Page 4
Table of contents ......Page 5
1 Introduction ......Page 6
2.1 A Bit of Modal Logic ......Page 10
2.2 A Bit of Complexity ......Page 15
2.3 Tiling Problems ......Page 23
2.4 Towards General Modal Complexity Results ......Page 25
3.1 Introduction ......Page 28
3.2 Upper Bound Transfer ......Page 29
3.3 The Power of the Join ......Page 35
3.4 Classification ......Page 41
3.5 The Complexity of the General Join ......Page 48
3.6 The Structure of the Join of Frames ......Page 53
4.1 Introduction ......Page 56
4.2 Upper Bounds ......Page 57
4.3 Lower Bounds ......Page 63
4.4 Classification ......Page 65
5.1 Introduction ......Page 72
5.2 Attribute Value Logic ......Page 73
5.3 Complexity Results for L, LN and LKR ......Page 81
5.4 The Universal Modality ......Page 85
5.5 The Master Modality ......Page 95
5.6 Concluding Remarks ......Page 99
6.1 Introduction ......Page 102
6.2 Syntax and Semantics ......Page 103
6.3 From Points to Intervals ......Page 105
6.4 Forcing Models to be Gridlike ......Page 106
6.5 Variations on a Theme by Ladner and Reif ......Page 114
6.6 A Generic Reduction from Linear to Branching Time ......Page 120
Bibliography ......Page 124
Samenvatting ......Page 130