- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
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.Author's Profile
Other Versions
No versions found
My notes
Similar books and articles
Computational complexity of some Ramsey quantifiers in finite models.Marcin Mostowski & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:281--282.
Henkin quantifiers and the definability of truth.Tapani Hyttinen & Gabriel Sandu - 2000 - Journal of Philosophical Logic 29 (5):507-527.
Henkin Quantifiers and Complete Problems.Andreas Blass & Yuri Gurevich - 1986 - Annals of Pure and Applied Logic 32:1--16.
Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2009 - Dissertation, University of Amsterdam
On second-order generalized quantifiers and finite structures.Anders Andersson - 2002 - Annals of Pure and Applied Logic 115 (1--3):1--32.
Equilibrium semantics of languages of imperfect information.Merlijn Sevenster & Gabriel Sandu - 2010 - Annals of Pure and Applied Logic 161 (5):618-631.
Decidability problems in languages with Henkin quantifiers.Michał Krynicki & Marcin Mostowski - 1992 - Annals of Pure and Applied Logic 58 (2):149-172.
Complexity of syntactical tree fragments of Independence-Friendly logic.Fausto Barbero - 2021 - Annals of Pure and Applied Logic 172 (1):102859.
Branching Quantification v. Two-way Quantification.Nina Gierasimczuk & Jakub Szymanik - 2009 - Journal of Semantics 26 (4):329-366.
Fragments of language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.
Analytics
Added to PP
2012-03-18
Downloads
41 (#549,457)
6 months
10 (#418,198)
2012-03-18
Downloads
41 (#549,457)
6 months
10 (#418,198)
Historical graph of downloads
Author's Profile
Citations of this work
Comprehension of Simple Quantifiers: Empirical Evaluation of a Computational Model.Jakub Szymanik & Marcin Zajenkowski - 2010 - Cognitive Science 34 (3):521-532.
Semantic bounds for everyday language.Marcin Mostowski & Jakub Szymanik - 2012 - Semiotica 2012 (188):363-372.
Forms of Luminosity: Epistemic Modality and Hyperintensionality in Mathematics.David Elohim - 2017 - Dissertation, Arché, University of St Andrews
Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2010 - Linguistics and Philosophy 33 (3):215-250.
References found in this work
On branching quantifiers in English.Jon Barwise - 1979 - Journal of Philosophical Logic 8 (1):47 - 80.
Comments on Jaakko Hintikka's paper “Quantifiers vs. Quantification theory”.Erik Stenius - 1976 - Dialectica 30 (1):67-88.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-648784bb4d-72rpk uwo