Autonomous Categories Book

1 Introduction 1

2 Basic Concepts 7

2.1 From Propositional to First Order Logic 7

2.2 Quantification 8

2.2.1 Semantics 9

2.2.2 Meaning 11

2.3 More on Quantification 12

2.3.1 Quantifier Scope and Prefixes 12

2.3.2 Skolemization 14

2.3.3 Quantifier Rank 15

2.3.4 Relativization 17

2.4 Games 18

2.5 More Semantics 19

2.5.1 Expressive Power of FOL 22

2.5.2 Finite and Infinite Models 22

3 Generalized Quantifiers 25

3.1 Introduction 25

3.2 Generalized Quantifiers 25

3.3 Another view 30

3.4 Basic Complexity 33

4 QLGQ: A Query Language with Generalized Quantifiers 37

4.1 Introduction: GQs in Query languages 37

4.2 QLGQ 38

4.2.1 Syntax of QLGQ 39

4.2.2 Semantics of QLGQ 41

4.2.3 Remarks on Syntax 42

4.3 Safety and Domain Independence 44

4.3.1 Relation to other languages 49

4.4 Generalized Quantifiers and SQL 50

5 Implementation and Optimization of Standard GQs 55

5.1 Languages to Define GQs 55

5.2 Translating and Optimizing QLGQ 60

5.3 The Interpreter 60

5.3.1 Complex Queries 66

5.4 Optimization 67

5.4.1 Optimization on RA Expressions 67

5.4.2 Optimization using GQ Properties 67

5.5 Application to SQL 69

5.6 Monadic vs. Polyadic Quantification 71

6 Quantifier Prefixes 73

6.1 Introduction 73

6.1.1 Linear and Non-linear Prefixes 74

6.1.2 Henkin Prefixes and Generalized Quantifiers 76

6.2 Linear and Non-Linear Prefixes in QLGQ 77

6.3 Cumulation 81

6.4 Branching 82

6.5 Linear Prefixes 85

6.5.1 Algebraic Translation 87

7 Cooperative Query Answering 91

7.1 Introduction 91

7.2 Cooperative Query Answering 91

7.3 Cooperative Query Answering with QLGQ 94

7.3.1 Presuppositions 94

7.3.2 ConstructingExplanations and Justifications 97

7.3.3 Relaxed Queries 100

7.3.4 Expressing and Using Constraints 103

7.4 Further Research in CQA 105

8 Generalized Quantifiers and Natural Language 107

8.1 Introduction 107

8.2 Question Answering 107

8.3 GQs in Natural Language Analysis 110

8.3.1 Combining Quantifiers 114

8.4 QLGQ in QA 116

8.5 CQA, QA and GQs 120

8.6 Challenges 122

9 Extensions 127

9.1 Datalog-like Languages 127

9.1.1 Aggregates 127

9.1.2 Fixpoint 128

9.1.3 Higher Order Variables 131

9.2 Distributed Quantification 134

9.2.1 Quantification and Distributed Databases 135

9.2.2 Computing Distributed Quantification 139

9.3 Other Data Models 143

10 Conclusion 149

References 151