Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language
Dissertation, University of Amsterdam (2009)
|Abstract||In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science.|
|Keywords||generalized quantifiers computational complexity algorithmic theory of meaning cognitive science|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Jakub Szymanik & Marcin Zajenkowski (2009). Improving Methodology of Quantifier Comprehension Experiments. Neuropsychologia 47 (12):2682--2683.
Jakub Szymanik & Marcin Zajenkowski (2009). Comprehension of Simple Quantifiers. Empirical Evaluation of a Computational Model. Cognitive Science: A Multidisciplinary Journal 34 (3):521-532.
Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. The Bulletin of Symbolic Logic 13:281--282.
Jakub Szymanik & Marcin Zajenkowski (2009). Understanding Quantifiers in Language. In N. A. Taatgen & H. van Rijn (eds.), Proceedings of the 31st Annual Conference of the Cognitive Science Society.
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
Jakub Szymanik (2009). The Computational Complexity of Quantified Reciprocals. In Peter Bosch, David Gabelaia & Jérôme Lang (eds.), Lecture Notes on Artificial Intelligence 5422, Logic, Language, and Computation 7th International Tbilisi Symposium on Logic, Language, and Computation. Springer.
Jakub Szymanik (2010). Almost All Complex Quantifiers Are Simple. In C. Ebert, G. Jäger, M. Kracht & J. Michaelis (eds.), Mathematics of Language 10/11, Lecture Notes in Computer Science 6149. Springer.
Marcin Zajenkowski, Rafał Styła & Jakub Szymanik (2011). A Computational Approach to Quantifiers as an Explanation for Some Language Impairments in Schizophrenia. Journal of Communication Disorder 44:2011.
Lauri Hella (1996). Logical Hierarchies in PTIME. Information and Computation 129 (1):1--19.
Jakub Szymanik (2010). Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language. Linguistics and Philosophy 33 (3):215-250.
Added to index2009-05-18
Total downloads27 ( #51,640 of 722,781 )
Recent downloads (6 months)1 ( #60,541 of 722,781 )
How can I increase my downloads?