Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic.

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 (e.g., 'you believe that I believe that you believe'). To investigate this we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize 'order of thinking.' We prove that theory of mind reasoning, so formalized, indeed is intractable (specifically, PSPACE-complete). Using parameterized complexity we prove, however, that the 'order parameter' is not a source of intractability. We furthermore consider a set of alternative parameters and investigate which of them are sources of intractability. We discuss the implications of these results for the understanding of theory of mind.

Working memory mechanism in proportional quantifier verification.

The paper explores the cognitive mechanisms involved in the verification of sentences with proportional quantifiers (e.g., "More than half of the dots are blue"). The first study shows that the verification of proportional sentences is more demanding than the verification of sentences such as: "There are seven blue and eight yellow dots". The second study reveals that both types of sentences are correlated with memory storage, however, only proportional sentences are associated with the cognitive control. This result suggests that the cognitive mechanism underlying the verification of proportional quantifiers is crucially related to the integration process, in which an individual has to compare in memory the cardinalities of two sets. In the third study we find that the numerical distance between two cardinalities that must be compared significantly influences the verification time and accuracy. The results of our studies are discussed in the broader context of processing complex sentences.

Recursive Numeral Systems Optimize the Trade-off Between Lexicon Size and Average Morphosyntactic Complexity.

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 informativeness even if they lexicalize very few meanings in that domain. This is due to productive morphosyntax and compositional semantics, which may allow for construction of meanings which are not lexicalized. Consider the semantic domain of natural numbers: many languages lexicalize few natural number meanings as monomorphemic expressions, but can precisely convey very many natural number meanings using morphosyntactically complex numerals. In such semantic domains, lexicon size is not in direct competition with informativeness. What explains which meanings are lexicalized in such semantic domains? We will propose that in such cases, languages need to solve a different kind of trade-off problem: the trade-off between the pressure to lexicalize as few meanings as possible (i.e, to minimize lexicon size) and the pressure to produce as morphosyntactically simple utterances as possible (i.e, to minimize average morphosyntactic complexity of utterances). To support this claim, we will present a case study of 128 natural languages' numeral systems, and show computationally that they achieve a near-optimal trade-off between lexicon size and average morphosyntactic complexity of numerals. This study in conjunction with previous work on communicative efficiency suggests that languages' lexicons are shaped by a trade-off between not two but three pressures: be simple, be informative, and minimize average morphosyntactic complexity of utterances.

Most quantifiers have many meanings.

In this paper, we investigate, by means of a computational model, how individuals map quantifiers onto numbers and how they order quantifiers on a mental line. We selected five English quantifiers (few, fewer than half, many, more than half, and most) which differ in truth conditions and vagueness. We collected binary truth value judgment data in an online quantifier verification experiment. Using a Bayesian three-parameter logistic regression model, we separated three sources of individual differences: truth condition, vagueness, and response error. Clustering on one of the model's parameter that corresponds to truth conditions revealed four subgroups of participants with different quantifier-to-number mappings and different ranges of the mental line of quantifiers. Our findings suggest multiple sources of individual differences in semantic representations of quantifiers and support a conceptual distinction between different types of imprecision in quantifier meanings. We discuss the consequence of our findings for the main theoretical approaches to quantifiers: the bivalent truth-conditional approach and the fuzzy logic approach. We argue that the former approach neither can explain inter-individual differences nor intra-individual differences in truth conditions of vague quantifiers. The latter approach requires further specification to fully account for individual differences demonstrated in this study.

The Boolean Language of Thought is recoverable from learning data.

According to the Language of Thought Hypothesis (LoTH), an influential account in philosophy and cognitive science, human cognition is underlain by symbolic reasoning in a formal language. In this account, concepts are expressions in a Language of Thought, deduction is syntactic manipulation in this language, and learning is an inference of expressions in this language from data. This picture raises the question of what LoT humans have, and how to infer it from behavior. In this paper, we pave the way towards answering this question, by approaching a more fundamental question: to what extent is it possible in principle to recover the human LoT from experimental data? To answer this question, we focus on the fragment of LoT that is concerned with representing Boolean categories and simulate the recovery of the Boolean LoT from category learning experiments. Our findings show that in principle the vast majority of Boolean LoTs can be accurately recovered from experimental data. However, we find that this crucially depends on the employed experimental design. Moreover, we find evidence that LoTs with fewer operators can be recovered from category learning data faster.

Questions About Quantifiers: Symbolic and Nonsymbolic Quantity Processing by the Brain.

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 research within the field of numerical cognition on the relationship between processing exact number symbols (such as "3" or "three") and nonsymbolic quantity. This accumulated knowledge can potentially be harvested for research on quantifiers since quantifiers and number symbols are two different ways of referring to quantity information symbolically. The goal of the present review is to survey the research on the relationship between quantifiers and nonsymbolic quantity processing mechanisms and provide a set of research directions and specific questions for the investigation of quantifier processing.

Uncovering the Structure of Semantic Representations Using a Computational Model of Decision-Making.

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 English speakers. In the first experiment, we tested between-subjects variability in meaning representations. In the second experiment, we tested the stability of meaning representations over time by testing the same group of participants in two experimental sessions. In both experiments, participants performed the verification task. They verified a sentence with a quantifier (e.g., "Most of the gleerbs are feezda.") based on the numerical information provided in the second sentence, (e.g., "60% of the gleerbs are feezda"). To investigate between-subject and within-subject differences in meaning representations, we proposed an extended version of the Diffusion Decision Model with two parameters capturing truth conditions and vagueness. We fit the model to responses and reaction times data. In the first experiment, we found substantial between-subject differences in representations of most as reflected by the variability in the truth conditions. Moreover, we found that the verification of most is proportion-dependent as reflected in the reaction time effect and model parameter. In the second experiment, we showed that quantifier representations are stable over time as reflected in stable model parameters across two experimental sessions. These findings challenge semantic theories that assume the truth-conditional equivalence of most and more than half and contribute to the representational theory of vague concepts. The current study presents a promising approach to study semantic representations, which can have a wide application in experimental linguistics.

Quantifiers satisfying semantic universals have shorter minimal description length.

Despite wide variation among natural languages, there are linguistic properties thought to be universal to all or nearly all languages. Here, we consider universals at the semantic level, in the domain of quantifiers, which are given by the properties of monotonicity, quantity, and conservativity, and we investigate whether these universals might be explained by differences in complexity. First, we use a minimal pair methodology and compare the complexities of individual quantifiers using approximate Kolmogorov complexity. Second, we use a simple yet expressive grammar to generate a large collection of quantifiers and we investigate their complexities at an aggregate level in terms of both their minimal description lengths and their approximate Kolmogorov complexities. For minimal description length we find that quantifiers satisfying semantic universals are simpler: they have a shorter minimal description length. For approximate Kolmogorov complexity we find that monotone quantifiers have a lower Kolmogorov complexity than non-monotone quantifiers and for quantity and conservativity we find that approximate Kolmogorov complexity does not scale robustly. These results suggest that the simplicity of quantifier meanings, in terms of their minimal description length, partially explains the presence of semantic universals in the domain of quantifiers.

Neural Networks Track the Logical Complexity of Boolean Concepts.

The language of thought hypothesis and connectionism provide two main accounts of category acquisition in the cognitive sciences. However, it is unclear to what extent their predictions agree. In this article, we tackle this problem by comparing the two accounts with respect to a common set of predictions about the effort required to acquire categories. We find that the two accounts produce similar predictions in the domain of Boolean categorization, however, with substantial variation depending on the operators in the language of thought.

Heavy Tails and the Shape of Modified Numerals.

The pattern of implicatures of the modified numeral "more than n" depends on the roundness of n. Cummins et al. (2012) present experimental evidence for the relation between roundness and implicature patterns and propose a pragmatic account of the phenomenon. More recently, Hesse and Benz (2020) present more extensive evidence showing that implicatures also depend on the magnitude of n and propose a novel explanation based on the approximate number system (Dehaene, 1999). Despite the wealth of experimental data, no formal account has yet been proposed to characterize the full posterior distribution over numbers of a listener after hearing "more than n." We develop one such account within the Rational Speech Act framework, quantitatively reconstructing the pragmatic reasoning of a rational listener. We argue that world knowledge about the distribution of the true quantity has a substantial impact on the information conveyed by the modified numeral. We show that our pragmatic account in combination with a heavy-tailed model of the participants' prior correctly predicts various features of the experimental data from Hesse and Benz (2020).

Computational complexity explains neural differences in quantifier verification.

Different classes of quantifiers provably require different verification algorithms with different complexity profiles. The algorithm for proportional quantifiers, like 'most', is more complex than that for nonproportional quantifiers, like 'all' and 'three'. We tested the hypothesis that different complexity profiles affect ERP responses during sentence verification, but not during sentence comprehension. In experiment 1, participants had to determine the truth value of a sentence relative to a previously presented array of geometric objects. We observed a sentence-final negative effect of truth value, modulated by quantifier class. Proportional quantifiers elicited a sentence-internal positivity compared to nonproportional quantifiers, in line with their different verification profiles. In experiment 2, the same stimuli were shown, followed by comprehension questions instead of verification. ERP responses specific to proportional quantifiers disappeared in experiment 2, suggesting that they are only evoked in a verification task and thus reflect the verification procedure itself. Our findings demonstrate that algorithmic aspects of human language processing are subjected to the same formal constraints applicable to abstract machines.

Indefinite Pronouns Optimize the Simplicity/Informativeness Trade-Off.

The vocabulary of human languages has been argued to support efficient communication by optimizing the trade-off between simplicity and informativeness. The argument has been originally based on cross-linguistic analyses of vocabulary in semantic domains of content words, such as kinship, color, and number terms. The present work applies this analysis to a category of function words: indefinite pronouns (e.g., someone, anyone, no one). We build on previous work to establish the meaning space and featural make-up for indefinite pronouns, and show that indefinite pronoun systems across languages optimize the simplicity/informativeness trade-off. This demonstrates that pressures for efficient communication shape both content and function word categories. In doing so, our work aligns with several concurrent studies exploring the simplicity/informativeness trade-off in functional vocabulary. Importantly, we further argue that the trade-off may explain some of the universal properties of indefinite pronouns, thus reducing the explanatory load for linguistic theories.

Monotone Quantifiers Emerge via Iterated Learning.

Natural languages exhibit many semantic 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 satisfy the monotonicity universal evolve reliably in an iterated learning paradigm with neural networks as agents.

Ease of learning explains semantic universals.

Semantic universals are properties of meaning shared by the languages of the world. We offer an explanation of the presence of such universals by measuring simplicity in terms of ease of learning, showing that expressions satisfying universals are simpler than those that do not according to this criterion. We measure ease of learning using tools from machine learning and analyze universals in a domain of function words (quantifiers) and content words (color terms). Our results provide strong evidence that semantic universals across both function and content words reflect simplicity as measured by ease of learning.

A computational approach to quantifiers as an explanation for some language impairments in schizophrenia.

UNLABELLED: We compared the processing of natural language quantifiers in a group of patients with schizophrenia and a healthy control group. In both groups, the difficulty of the quantifiers was consistent with computational predictions, and patients with schizophrenia took more time to solve the problems. However, they were significantly less accurate only with proportional quantifiers, like more than half. This can be explained by noting that, according to the complexity perspective, only proportional quantifiers require working memory engagement. LEARNING OUTCOMES: (1) Working memory deficits can be a source of language disorders in schizophrenia. (2) Processing of proportional quantifiers, like more than half or less than half involves working memory. (3) Patients with schizophrenia are less accurate only with proportional quantifiers, like more than half. (4) This result support the computational model of quantifiers processing.

Intentional communication: computationally easy or difficult?

Human intentional communication is marked by its flexibility and context sensitivity. Hypothesized brain mechanisms can provide convincing and complete explanations of the human capacity for intentional communication only insofar as they can match the computational power required for displaying that capacity. It is thus of importance for cognitive neuroscience to know how computationally complex intentional communication actually is. Though the subject of considerable debate, the computational complexity of communication remains so far unknown. In this paper we defend the position that the computational complexity of communication is not a constant, as some views of communication seem to hold, but rather a function of situational factors. We present a methodology for studying and characterizing the computational complexity of communication under different situational constraints. We illustrate our methodology for a model of the problems solved by receivers and senders during a communicative exchange. This approach opens the way to a principled identification of putative model parameters that control cognitive processes supporting intentional communication.

Comprehension of simple quantifiers: empirical evaluation of a computational model.

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. 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, the hypotheses and explanatory power of recent neuroimaging studies as well as provides evidence for the claim that human linguistic abilities are constrained by computational complexity.