Jakub Szymanik

We study a generalization of the Muddy Children puzzle by allowing public announcements with arbitrary generalized quantifiers. We propose a new concise logical modeling of the puzzle based on the number triangle representation of quantifiers. Our general aim is to discuss the possibility of epistemic modeling that is cut for specific informational dynamics. Moreover, we show that the puzzle is solvable for any number of agents if and only if the quantifier in the announcement is positively active (satises a form of variety).

We examine the verification of simple quantifiers in natural language from a computational model perspective. We refer to previous neuropsychological investigations of the same problem and suggest extending their experimental setting. Moreover, we give some direct empirical evidence linking computational complexity predictions with cognitive reality.<br>In the empirical study we compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and push-down automata is psychologically relevant. Our research improves upon hypothesis and explanatory power of recent neuroimaging studies as well as provides<br>evidence.

Natural language sentences that talk about two or more sets of entities can be assigned various readings. The ones in which the sets are independent of one another are particularly challenging from the formal point of view. In this paper we will call them ‘Independent Set (IS) readings’. Cumulative and collective readings are paradigmatic examples of IS readings. Most approaches aiming at representing the meaning of IS readings implement some kind of maximality conditions on the witness sets involved. Two kinds of maximization have been proposed in the literature: ‘Local’ and ‘Global’ maximization. In this paper, we present an online questionnaire whose results appear to support Local maximization. The latter seems to capture the proper interplay between the semantics and the pragmatics of multi-quantifier sentences, provided that witness sets are selected on pragmatic grounds

In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred interpretation, provides evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents.

The paper presents two case studies of multi-agent information exchange involving generalized quantifiers. We focus on scenarios in which agents successfully converge to knowledge on the basis of the information about the knowledge of others, so-called Muddy Children puzzle and Top Hat puzzle. We investigate the relationship between certain invariance properties of quantifiers and the successful convergence to knowledge in such situations. We generalize the scenarios to account for public announcements with arbitrary quantifiers. We show that the Muddy Children puzzle is solvable for any number of agents if and only if the quantifier in the announcement is positively active (satisfies a version of the variety condition). In order to get the characterization result, we propose a new concise logical modeling of the puzzle based on the number triangle representation of generalized quantifiers. In a similar vein, we also study the Top Hat puzzle. We observe that in this case an announcement needs to satisfy stronger conditions in order to guarantee solvability. Hence, we introduce a new property, called bounded thickness, and show that the solvability of the Top Hat puzzle for arbitrary number of agents is equivalent to the announcement being 1-thick.

We consider collective quantification in natural language. For many years the common strategy in formalizing collective quantification has been to define the meanings of collective determiners, quantifying over collections, using certain type-shifting operations. These type-shifting operations, i.e., lifts, define the collective interpretations of determiners systematically from the standard meanings of quantifiers. All the lifts considered in the literature turn out to be definable in second-order logic. We argue that second-order definable quantifiers are probably not expressive enough to formalize all collective quantification in natural language.

The paper presents an experimental evidence on differences in the sentence-picture verification under additional memory load between parity and proportional quantifiers. We asked subjects to memorize strings of 4 or 6 digits, then to decide whether a quantifier sentence is true at a given picture, and finally to recall the initially given string of numbers. The results show that: (a) proportional quantifiers are more difficult than parity quantifiers with respect to reaction time and accuracy; (b) maintaining either 4 or 6 elements in the working memory has the same effect on the processing of parity quantifiers; (c) however, in the case of proportional quantifiers subjects performed better in the verification tasks under the 6-digit load condition, and (d) even though the strings of 4 numbers were better recalled by subjects after judging parity there is no difference between quantifiers in the case of the 6-element condition. We briefly outline two alternative explanations for the observed phenomena rooted in the computational model of quantifier verification and the different theories of working memory.

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.

We discuss McMillan et al. (2005) paper devoted to study brain activity during comprehension of sentences with generalized quantifiers. According to the authors their results verify a particular computational model of natural language quantifier comprehension posited by several linguists and logicians (e. g. see van Benthem, 1986). We challenge this statement by invoking the computational difference between first-order quantifiers and divisibility quantifiers (e. g. see Mostowski, 1998). Moreover, we suggest other studies on quantifier comprehension, which can throw more light on the role of working memory in processing quantifiers

Next SectionWe discuss the thesis formulated by Hintikka (1973) that certain natural language sentences require non-linear quantification to express their meaning. We investigate sentences with combinations of quantifiers similar to Hintikka's examples and propose a novel alternative reading expressible by linear formulae. This interpretation is based on linguistic and logical observations. We report on our experiments showing that people tend to interpret sentences similar to Hintikka sentence in a way consistent with our interpretation

We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier $\sQ_1$ is definable in terms of another quantifier $\sQ_2$, the base logic being monadic second-order logic, reduces to the question if a quantifier $\sQ^{\star}_1$ is definable in $\FO(\sQ^{\star}_2,<,+,\times)$ for certain first-order quantifiers $\sQ^{\star}_1$ and $\sQ^{\star}_2$. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. In particular, we show that the monadic second-order majority quantifier $\most^1$ is not definable in second-order logic.