Jakub Szymanik was kind enough to send me a surprise gift - a copy of his Quantifiers in TIME and SPACE (his dissertation published by ILLC). I've just discovered it in my mailbox. Thanks, Jakub! It seems fun and I look forward to reading it! Meanwhile, here is the abstract:
In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories.
We argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Then, we discuss the influence of computational complexity theory on cognitive tasks to motivate technical considerations which follow.
First, we study computational complexity of quantifier iteration, cumulation, resumption, branching and Ramseyification. Then we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents and establish a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. We argue that this difference should be acknowledged in the Strong Meaning hypothesis.
Moreover, we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics.
Theoretical discussion is followed by the empirical investigations. We study the statement known as Hintikka's thesis: that the semantics of sentences like 'Most boys and most girls hate each other' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading.
Finally, we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model.
In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science.
Comments