Change search
ReferencesLink to record
Permanent link

Direct link
Computational complexity of polyadic lifts of generalized quantifiers in natural language
Stockholm University, Faculty of Humanities, Department of Philosophy.
2010 (English)In: Linguistics and Philosophy, ISSN 0165-0157, E-ISSN 1573-0549, Vol. 33, no 3, 215-250 p.Article in journal (Refereed) Published
Abstract [en]

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to investigate semantic distinctions between quantified reciprocal sentences. We show a computational dichotomy between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility of revising the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of formal semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science.

Place, publisher, year, edition, pages
2010. Vol. 33, no 3, 215-250 p.
Keyword [en]
Generalized quantifier theory, Computational complexity, Polyadic quantification, Multi-quantifier sentences, Strong Meaning Hypothesis
National Category
URN: urn:nbn:se:su:diva-68175DOI: 10.1007/s10988-010-9076-zISI: 000287362800003OAI: diva2:472195
authorCount :1Available from: 2012-01-03 Created: 2012-01-03 Last updated: 2012-01-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Szymanik, Jakub
By organisation
Department of Philosophy
In the same journal
Linguistics and Philosophy

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 55 hits
ReferencesLink to record
Permanent link

Direct link