* * * * * * * * * * * * * * * * * * * * * * * *
LINGUIST List logo Eastern Michigan University Wayne State University *
* People & Organizations * Jobs * Calls & Conferences * Publications * Language Resources * Text & Computer Tools * Teaching & Learning * Mailing Lists * Search *
* *
LINGUIST List 20.1130

Sat Mar 28 2009

Diss: Comp Ling/Semantics: Szymanik: 'Quantifiers in TIME and SPACE...'

Editor for this issue: Evelyn Richter <evelynlinguistlist.org>

To post to LINGUIST, use our convenient web form at http://linguistlist.org/LL/posttolinguist.html.
        1.    Jakub Szymanik, Quantifiers in TIME and SPACE: Computational complexity of generalized quantifiers in natural language

Message 1: Quantifiers in TIME and SPACE: Computational complexity of generalized quantifiers in natural language
Date: 26-Mar-2009
From: Jakub Szymanik <j.szymanikuva.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

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!


There are many ways to donate to LINGUIST!

You can donate right now using our secure credit card form at  

Alternatively you can also pledge right now and pay later. To do so, go to:

For all information on donating and pledging, including information on how to 
donate by check, money order, or wire transfer, please visit:

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

Please report any bad links or misclassified data

LINGUIST Homepage | Read LINGUIST | Contact us

NSF Logo

While the LINGUIST List makes every effort to ensure the linguistic relevance of sites listed
on its pages, it cannot vouch for their contents.