Date: 26-Mar-2009
From: Jakub Szymanik <j.szymanik uva.nl>
Subject: Quantifiers in TIME and SPACE: Computational complexity of generalized quantifiers in natural language
 E-mail this message to a friend
Institution: Institute for Logic, Language and Computation
Program: Logic & Language
Dissertation Status: Completed
Degree Date: 2009
Author: Jakub Szymanik
Dissertation Title: Quantifiers in TIME and SPACE: Computational complexity of generalized quantifiers in natural language
Linguistic Field(s):
Cognitive Science
Computational Linguistics
Philosophy of Language
Psycholinguistics
Semantics
Dissertation Director:
Marcin Mostowski
Theo A. Janssen
Johan van Benthem
Dissertation 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.
This Year the LINGUIST List hopes to raise $60,000. This money will go to help
keep the List running by supporting all of our Student Editors for the coming year.
See below for donation instructions, and don't forget to check out our Fund Drive
2009 LINGUIST List Restaurant and join us for a delightful treat!
http://linguistlist.org/fund-drive/2009/
There are many ways to donate to LINGUIST!
You can donate right now using our secure credit card form at
https://linguistlist.org/donation/donate/donate1.cfm
Alternatively you can also pledge right now and pay later. To do so, go to:
https://linguistlist.org/donation/pledge/pledge1.cfm
For all information on donating and pledging, including information on how to
donate by check, money order, or wire transfer, please visit:
http://linguistlist.org/donate.html
The LINGUIST List is under the umbrella of Eastern Michigan University and as such
can receive donations through the EMU Foundation, which is a registered 501(c) Non
Profit organization. Our Federal Tax number is 38-6005986. These donations can be
offset against your federal and sometimes your state tax return (U.S. tax payers
only). For more information visit the IRS Web-Site, or contact your financial advisor.
Many companies also offer a gift matching program, such that they will match any
gift you make to a non-profit organization. Normally this entails your contacting
your human resources department and sending us a form that the EMU Foundation fills
in and returns to your employer. This is generally a simple administrative procedure
that doubles the value of your gift to LINGUIST, without costing you an extra penny.
Please take a moment to check if your company operates such a program.
Thank you very much for your support of LINGUIST!
-----------------------------------------------------------------------------------------
Read more issues|LINGUIST home page|Top of issue
|
