- 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
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.
Hintikka's thesis revisited.Nina Gierasimczuk & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:273.
Analytics
Added to PP
2012-03-18
Downloads
29 (#135,560)
6 months
11 (#1,140,922)
2012-03-18
Downloads
29 (#135,560)
6 months
11 (#1,140,922)
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.
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.
Semantic bounds for everyday language.Marcin Mostowski & Jakub Szymanik - 2012 - Semiotica 2012 (188):363-372.
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-6686886f5-2nz2h uwo