Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Humanities
Identifiers
URN: urn:nbn:se:su:diva-68175DOI: 10.1007/s10988-010-9076-zISI: 000287362800003OAI: oai:DiVA.org:su-68175DiVA: diva2:472195
Note
authorCount :1Available from: 2012-01-03 Created: 2012-01-03 Last updated: 2017-12-08Bibliographically 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
Humanities

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 60 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf