Computational complexity of the semantics of some natural language constructions

Annals of Pure and Applied Logic 127 (1-3):219--227 (2004)
Abstract
We consider an example of a sentence which according to Hintikka's claim essentially requires for its logical form a Henkin quantifier. We show that if Hintikka is right then recognizing the truth value of the sentence in finite models is an NP-complete problem. We discuss also possible conclusions from this observation.
Keywords bibtex-import   quantifiers
Categories (categorize this paper)
DOI 10.1016/j.apal.2003.11.016
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 31,396
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
On Branching Quantifiers in English.Jon Barwise - 1979 - Journal of Philosophical Logic 8 (1):47 - 80.
Quantifiers Vs. Quantification Theory.Jaakko Hintikka - 1973 - Dialectica 27 (3‐4):329-358.

Add more references

Citations of this work BETA
A Remark on Collective Quantification.Juha Kontinen & Jakub Szymanik - 2008 - Journal of Logic, Language and Information 17 (2):131-140.

View all 6 citations / Add more citations

Similar books and articles
Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non--Classical Logics 8 (1-2):107--121.
Generalized Quantifiers and Natural Language.Jon Barwise & Robin Cooper - 1981 - Linguistics and Philosophy 4 (2):159--219.
Fragments of Language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.
Henkin Quantifiers.M. Krynicki & M. Mostowski - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers. pp. 193--263.
Quantifiers Definable by Second Order Means.M. Mostowski - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers. pp. 181--214.
Quantifiers, Some Problems and Ideas.M. Krynicki & M. Mostowski - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers. pp. 1--21.
Ambigous Quantifiers.M. Krynicki & M. Mostowski - 1999 - In E. Orłowska (ed.), Logic at Work. Heidelberg. pp. 548--565.
Added to PP index
2012-03-18

Total downloads
11 ( #450,048 of 2,225,985 )

Recent downloads (6 months)
1 ( #426,905 of 2,225,985 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature