|
Part I Procedural Semantics |
|
|
|
1 Algorithmic Theory of Meaning |
|
|
3 | (6) |
|
|
7 | (2) |
|
2 Complexity in Linguistics |
|
|
9 | (14) |
|
2.1 Computational Complexity |
|
|
10 | (1) |
|
|
11 | (2) |
|
|
13 | (1) |
|
|
13 | (4) |
|
|
17 | (6) |
|
|
18 | (5) |
|
Part II Simple Quantifiers |
|
|
|
3 Basic Generalized Quantifier Theory |
|
|
23 | (18) |
|
3.1 Two Equivalent Concepts of Generalized Quantifiers |
|
|
25 | (2) |
|
3.2 Logic Enriched by Generalized Quantifiers |
|
|
27 | (1) |
|
3.3 Definability of Generalized Quantifiers |
|
|
27 | (3) |
|
|
30 | (6) |
|
3.4.1 Boolean Combinations of Quantifiers |
|
|
30 | (1) |
|
3.4.2 Relativization of Quantifiers |
|
|
31 | (1) |
|
3.4.3 Domain Independence |
|
|
31 | (1) |
|
|
32 | (1) |
|
|
33 | (3) |
|
|
36 | (5) |
|
|
39 | (2) |
|
4 Computing Simple Quantifiers |
|
|
41 | (10) |
|
4.1 Representation of Finite Models |
|
|
42 | (2) |
|
|
44 | (2) |
|
4.3 Characterization Results |
|
|
46 | (5) |
|
|
49 | (2) |
|
5 Cognitive Processing of Quantifiers |
|
|
51 | (36) |
|
|
54 | (3) |
|
|
54 | (2) |
|
|
56 | (1) |
|
|
57 | (4) |
|
5.2.1 Probabilistic Semantic Automata |
|
|
57 | (2) |
|
|
59 | (2) |
|
|
61 | (6) |
|
5.3.1 Neurocognitive Evidence |
|
|
61 | (1) |
|
|
62 | (1) |
|
5.3.3 Schizophrenic Patients |
|
|
63 | (2) |
|
|
65 | (1) |
|
5.3.5 Executive Resources |
|
|
65 | (2) |
|
5.4 Corpora Distributions |
|
|
67 | (2) |
|
|
68 | (1) |
|
|
69 | (7) |
|
5.5.1 Comparison with Literature |
|
|
74 | (2) |
|
5.6 Approximate Number System |
|
|
76 | (2) |
|
|
78 | (9) |
|
|
80 | (7) |
|
Part III Complex Quantifiers |
|
|
|
6 Standard Polyadic Lifts |
|
|
87 | (14) |
|
|
88 | (2) |
|
|
90 | (1) |
|
|
90 | (1) |
|
6.4 Semantic Automata for Polyadic Quantifiers |
|
|
91 | (4) |
|
6.4.1 Experimental Direction |
|
|
94 | (1) |
|
|
95 | (5) |
|
6.5.1 Classic Characterization Results |
|
|
96 | (3) |
|
6.5.2 The Frege Boundary and the Chomsky Hierarchy? |
|
|
99 | (1) |
|
|
100 | (1) |
|
|
100 | (1) |
|
7 Complexity of Polyadic Quantifiers |
|
|
101 | (22) |
|
7.1 Computational Complexity of Quantifiers |
|
|
102 | (4) |
|
7.2 PTIME Generalized Quantifiers Are Closed Under It, Cum, and Res |
|
|
106 | (2) |
|
7.3 Branching Quantifiers |
|
|
108 | (3) |
|
7.3.1 Henkin's Quantifiers |
|
|
109 | (1) |
|
7.3.2 Proportional Branching Quantifiers |
|
|
109 | (2) |
|
|
111 | (8) |
|
7.4.1 The Branching Reading of Hintikka's Sentence |
|
|
111 | (1) |
|
|
112 | (1) |
|
7.4.3 Proportional Ramsey Quantifiers |
|
|
113 | (2) |
|
7.4.4 Tractable Ramsey Quantifiers |
|
|
115 | (2) |
|
7.4.5 Intermediate Ramsey Quantifiers |
|
|
117 | (1) |
|
|
118 | (1) |
|
|
119 | (4) |
|
|
120 | (3) |
|
8 Complexity of Quantified Reciprocals |
|
|
123 | (20) |
|
8.1 Reciprocal Expressions |
|
|
124 | (4) |
|
8.1.1 Strong Meaning Hypothesis |
|
|
127 | (1) |
|
8.2 Reciprocals as Polyadic Quantifiers |
|
|
128 | (2) |
|
8.2.1 Strong Reciprocal Lift |
|
|
128 | (1) |
|
8.2.2 Intermediate Reciprocal Lift |
|
|
129 | (1) |
|
8.2.3 Weak Reciprocal Lift |
|
|
129 | (1) |
|
8.2.4 The Reciprocal Lifts in Action |
|
|
129 | (1) |
|
8.3 Complexity of Strong Reciprocity |
|
|
130 | (4) |
|
8.3.1 Counting Quantifiers in the Antecedent |
|
|
131 | (1) |
|
8.3.2 Proportional Quantifiers in the Antecedent |
|
|
132 | (1) |
|
8.3.3 Tractable Strong Reciprocity |
|
|
133 | (1) |
|
8.4 Intermediate and Weak Lifts |
|
|
134 | (2) |
|
8.5 A Complexity Perspective on the SMH |
|
|
136 | (1) |
|
|
137 | (3) |
|
8.6.1 Cognitive Difficulty |
|
|
137 | (2) |
|
8.6.2 Distribution in English |
|
|
139 | (1) |
|
|
140 | (3) |
|
|
141 | (2) |
|
|
143 | (22) |
|
|
144 | (2) |
|
9.2 Other Hintikka-Like Sentences |
|
|
146 | (1) |
|
9.3 Theoretical Discussion |
|
|
147 | (6) |
|
9.3.1 A Remark on Possible Readings |
|
|
147 | (1) |
|
9.3.2 Hintikka-Like Sentences Are Symmetric |
|
|
148 | (1) |
|
9.3.3 Inferential Arguments |
|
|
149 | (1) |
|
|
150 | (2) |
|
9.3.5 Complexity Arguments |
|
|
152 | (1) |
|
9.3.6 Theoretical Conclusions |
|
|
152 | (1) |
|
|
153 | (6) |
|
9.4.1 Experimental Hypotheses |
|
|
153 | (1) |
|
|
154 | (5) |
|
|
159 | (6) |
|
|
160 | (5) |
|
Part IV Collective Quantifiers |
|
|
|
10 Complexity of Collective Quantification |
|
|
165 | (22) |
|
10.1 Collective Quantifiers |
|
|
166 | (3) |
|
10.1.1 Collective Readings in Natural Language |
|
|
166 | (2) |
|
10.1.2 Modeling Collectivity |
|
|
168 | (1) |
|
10.2 Lifting First-Order Determiners |
|
|
169 | (5) |
|
10.2.1 The Existential Modifier |
|
|
169 | (2) |
|
10.2.2 The Neutral Modifier |
|
|
171 | (1) |
|
10.2.3 The Determiner Fitting Operator |
|
|
171 | (1) |
|
10.2.4 A Note on Collective Invariance Properties |
|
|
172 | (2) |
|
10.3 Second-Order Generalized Quantifiers |
|
|
174 | (1) |
|
10.4 Defining Collective Determiners by SOGQs |
|
|
175 | (2) |
|
10.5 Definability Theory for SOGQs |
|
|
177 | (3) |
|
|
177 | (2) |
|
10.5.2 Characterization Result |
|
|
179 | (1) |
|
|
180 | (3) |
|
10.6.1 An Undefinability Result for the SOGQ `MOST' |
|
|
180 | (1) |
|
10.6.2 Consequences of Undefinability |
|
|
181 | (2) |
|
|
183 | (4) |
|
|
184 | (3) |
|
Part V Perspectives and Conclusions |
|
|
|
|
187 | (4) |
|
|
189 | (2) |
Appendix A Mathematical Machinery |
|
191 | (18) |
Index |
|
209 | |