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

Sun Mar 29 00:34:36 UTC 2009

LINGUIST List: Vol-20-1130. Sat Mar 28 2009. ISSN: 1068 - 4875.

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

Moderators: Anthony Aristar, Eastern Michigan U <aristar at linguistlist.org>
            Helen Aristar-Dry, Eastern Michigan U <hdry at linguistlist.org>

Reviews: Randall Eggert, U of Utah  
       <reviews at linguistlist.org> 

Homepage: http://linguistlist.org/

The LINGUIST List is funded by Eastern Michigan University, 
and donations from subscribers and publishers.

Editor for this issue: Evelyn Richter <evelyn at linguistlist.org>
================================================================  

To post to LINGUIST, use our convenient web form at
http://linguistlist.org/LL/posttolinguist.html.

===========================Directory==============================  

1)
Date: 26-Mar-2009
From: Jakub Szymanik < j.szymanik at uva.nl >
Subject: Quantifiers in TIME and SPACE: Computational complexity of generalized quantifiers in natural language

-------------------------Message 1 ---------------------------------- 
Date: Sat, 28 Mar 2009 20:26:41
From: Jakub Szymanik [j.szymanik at uva.nl]
Subject: Quantifiers in TIME and SPACE: Computational complexity of generalized quantifiers in natural language

E-mail this message to a friend:
http://linguistlist.org/issues/emailmessage/verification.cfm?iss=20-1130.html&submissionid=211046&topicid=14&msgnumber=1

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(s):
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!
-----------------------------------------------------------
LINGUIST List: Vol-20-1130	