•  3
    Human languages vary in terms of which meanings they lexicalize, but this variation is constrained. It has been argued that languages are under two competing pressures: the pressure to be simple (e.g., to have a small lexicon) and to allow for informative (i.e., precise) communication, and that which meanings get lexicalized may be explained by languages finding a good way to trade off between these two pressures. However, in certain semantic domains, languages can reach very high levels of info…Read more
  •  11
    Questions About Quantifiers: Symbolic and Nonsymbolic Quantity Processing by the Brain
    with Arnold Kochari and Heming Strømholt Bremnes
    Cognitive Science 47 (10). 2023.
    One approach to understanding how the human cognitive system stores and operates with quantifiers such as “some,” “many,” and “all” is to investigate their interaction with the cognitive mechanisms for estimating and comparing quantities from perceptual input (i.e., nonsymbolic quantities). While a potential link between quantifier processing and nonsymbolic quantity processing has been considered in the past, it has never been discussed extensively. Simultaneously, there is a long line of resea…Read more
  •  86
    Exploring the tractability border in epistemic tasks
    with Cédric Dégremont and Lena Kurzen
    Synthese 191 (3): 371-408. 2014.
    We analyse the computational complexity of comparing informational structures. Intuitively, we study the complexity of deciding queries such as the following: Is Alice’s epistemic information strictly coarser than Bob’s? Do Alice and Bob have the same knowledge about each other’s knowledge? Is it possible to manipulate Alice in a way that she will have the same beliefs as Bob? The results show that these problems lie on both sides of the border between tractability (P) and intractability (NP-har…Read more
  •  31
    Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic
    with Iris van de Pol and Iris van Rooij
    Journal of Logic, Language and Information 27 (3): 255-294. 2018.
    Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve higher-order thinking. To investigate this we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameteri…Read more
  •  26
    Logic and Cognition: Special Issue of Best Papers of the ESSLLI 2012 Workshop
    Journal of Logic, Language and Information 22 (4): 357-362. 2013.
    The explanatory power of logic is vast and therefore it has proved a valuable tool for many disciplines, including the building-blocks of cognitive science, such as philosophy, computer science, mathematics, artificial intelligence, and linguistics. Logic has a great track record in providing interesting insights by means of formalization, and as such it is very useful in disambiguating psychological theories. Logically formalized cognitive theories are not only the source of unequivocal experim…Read more
  •  10
    Uncovering the Structure of Semantic Representations Using a Computational Model of Decision‐Making
    with Sonia Ramotowska, Shane Steinert-Threlkeld, and Leendert van Maanen
    Cognitive Science 47 (1). 2023.
    According to logical theories of meaning, a meaning of an expression can be formalized and encoded in truth conditions. Vagueness of the language and individual differences between people are a challenge to incorporate into the meaning representations. In this paper, we propose a new approach to study truth-conditional representations of vague concepts. For a case study, we selected two natural language quantifiers most and more than half. We conducted two online experiments, each with 90 native…Read more
  •  5
    Heavy Tails and the Shape of Modified Numerals
    with Fausto Carcassi
    Cognitive Science 46 (7). 2022.
    Cognitive Science, Volume 46, Issue 7, July 2022.
  •  8
    Cognitive Science, Volume 46, Issue 5, May 2022.
  •  11
  •  14
    Monotone Quantifiers Emerge via Iterated Learning
    with Fausto Carcassi and Shane Steinert-Threlkeld
    Cognitive Science 45 (8). 2021.
    Natural languages exhibit manysemantic universals, that is, properties of meaning shared across all languages. In this paper, we develop an explanation of one very prominent semantic universal, the monotonicity universal. While the existing work has shown that quantifiers satisfying the monotonicity universal are easier to learn, we provide a more complete explanation by considering the emergence of quantifiers from the perspective of cultural evolution. In particular, we show that quantifiers s…Read more
  •  33
    Conjoining Meanings: Semantics without Truth Values
    Philosophical Review 130 (1): 171-175. 2021.
  •  2
    Problems with Logical Form
    Studia Semiotyczne—English Supplement 25 85-100. 2004.
    The examination of quantifiers plays an essential role in modern linguistic theories. One of the most important issues in this respect was raised by Jaakko Hintikka, who proposed the following thesis: Certain natural language sentences require essential non-linear quantification to adequately express their logical form.
  •  5
    Computational Semantics for Monadic Quantifiers in Natural Language
    Studia Semiotyczne—English Supplement 26 105-130. 2007.
    One of the interesting problems in the theory of language is the problem of describing and explaining the mechanisms responsible for our ability to understand sentences. A description of the mechanism of linguistic competence, which we can refer to as semantic competence, is necessary for understanding the phenomenon of language. For to use a language is not only to use a certain vocabulary and grammatical rules, but most of all to associate certain meanings with certain expressions. For example…Read more
  •  60
    Learnability and Semantic Universals
    Semantics and Pragmatics. forthcoming.
    One of the great successes of the application of generalized quantifiers to natural language has been the ability to formulate robust semantic universals. When such a universal is attested, the question arises as to the source of the universal. In this paper, we explore the hypothesis that many semantic universals arise because expressions satisfying the universal are easier to learn than those that do not. While the idea that learnability explains universals is not new, explicit accounts of lea…Read more
  •  408
    Tractability and the computational mind
    with Rineke Verbrugge
    In Mark Sprevak & Matteo Colombo (eds.), The Routledge Handbook of the Computational Mind, Routledge. pp. 339-353. 2018.
    We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effecti…Read more
  •  14
    Branching Quantification v. Two-way Quantification: Articles
    Journal of Semantics 26 (4): 367-392. 2009.
    We discuss the thesis formulated by Hintikka 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…Read more
  •  80
    Quantifiers and Working Memory
    with Marcin Zajenkowski
    In Maria Aloni & Katrin Schulz (eds.), Amsterdam Colloquium 2009, LNAI 6042, Springer. 2010.
    The paper presents a study examining the role of working<br>memory in quantifier verification. We created situations similar to the<br>span task to compare numerical quantifiers of low and high rank, parity<br>quantifiers and proportional quantifiers. The results enrich and support<br>the data obtained previously in and predictions drawn from a computational<br>model.
  •  32
    On the Identification of Quantifiers' Witness Sets: A Study of Multi-quantifier Sentences
    with Livio Robaldo and Ben Meijering
    Journal of Logic, Language and Information 23 (1): 53-81. 2014.
    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 inv…Read more
  •  65
    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 r…Read more
  •  42
    Understanding Quantifiers in Language
    with Marcin Zajenkowski
    We compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and pushdown automata is psychologically relevant. Our research improves upon hypothesis and explanatory power of recent neuroimaging studies as well as provides evidence for the claim that human linguistic abilities are constrained by computational complexity.
  •  59
    A remark on collective quantification
    with Juha Kontinen
    Journal of Logic, Language and Information 17 (2): 131-140. 2008.
    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-or…Read more
  •  65
    This volume on the semantic complexity of natural language explores the question why some sentences are more difficult than others. While doing so, it lays the groundwork for extending semantic theory with computational and cognitive aspects by combining linguistics and logic with computations and cognition. -/- Quantifier expressions occur whenever we describe the world and communicate about it. Generalized quantifier theory is therefore one of the basic tools of linguistics today, studying th…Read more
  •  92
    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 tre…Read more
  •  35
    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 …Read more