We propose a framework that makes space for both non-indexical contextualism and assessment-sensitivity. Such pluralism is motivated by considering possible variance in judgments about retraction. We conclude that the proposed pluralism, instead of problematizing, vindicates defining truth of a proposition w.r.t. a context of utterance and a context of assessment. To implement this formally, we formalize initialization of parameters by contexts. Then, a given parameter, depending on a speaker's judgment, can get initialized by either the context of utterance or the (...) context of assessment. An upshot of the proposal is that one need not exclusively espouse one of non-indexical contextualism or assessment-sensitivity about a particular class of expressions, for instance predicates of personal taste, in language; one can be pluralist in this sense. (This manuscript is part of an ongoing research project). (shrink)

A probabilistic Chomsky–Schützenberger hierarchy of grammars is introduced and studied, with the aim of understanding the expressive power of generative models. We offer characterizations of the distributions definable at each level of the hierarchy, including probabilistic regular, context-free, (linear) indexed, context-sensitive, and unrestricted grammars, each corresponding to familiar probabilistic machine classes. Special attention is given to distributions on (unary notations for) positive integers. Unlike in the classical case where the "semi-linear" languages all collapse into the regular languages, using analytic tools (...) adapted from the classical setting we show there is no collapse in the probabilistic hierarchy: more distributions become definable at each level. We also address related issues such as closure under probabilistic conditioning. (shrink)

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 learning that can (...) make good on this hypothesis are few and far between. We propose a model of learning — back-propagation through a recurrent neural network — which can make good on this promise. In particular, we discuss the universals of monotonicity, quantity, and conservativity and perform computational experiments of training such a network to learn to verify quantifiers. Our results are able to explain monotonicity and quantity quite well. We suggest that conservativity may have a different source than the other universals. (shrink)

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 effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, to (...) be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. -/- We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition. (shrink)

This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (shrink)

We use imperatives to refute a naïve analysis of update potentials (force-operators attaching to sentences), arguing for a dynamic analysis of imperative force as restrictable, directed, and embeddable. We propose a dynamic, non-modal analysis of conditional imperatives, as a counterpoint to static, modal analyses. Our analysis retains Kratzer's analysis of if-clauses as restrictors of some operator, but avoids typing it as a generalized quantifier over worlds (against her), instead as a dynamic force operator. Arguments for a restrictor treatment (but against (...) a quantificational treatment) are mustered, and we propose a novel analysis of update on conditional imperatives (and an independently motivated revision of the standard ordering-semantics for root modals that makes use of it). Finally, we argue that imperative force is embeddable under an operation much like dynamic conjunction. (shrink)

This paper surveys the common approach to quantification and generalised quantification in formal linguistics and philosophy of language. We point out how this general setting departs from empirical linguistic data, and give some hints for a different view based on proof theory, which on many aspects gets closer to the language itself. We stress the importance of Hilbert's oper- ator epsilon and tau for, respectively, existential and universal quantifications. Indeed, these operators help a lot to construct semantic representation close to (...) natural language, in particular with quantified noun phrases as individual terms. We also define guidelines for the design of the proof rules corresponding to generalised quantifiers. (shrink)

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to investigate semantic (...) distinctions between quantified reciprocal sentences. We show a computational dichotomy<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of the formal<br>semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science. (shrink)

The semantic automata framework, developed originally in the 1980s, provides computational interpretations of generalized quantifiers. While recent experimental results have associated structural features of these automata with neuroanatomical demands in processing sentences with quantifiers, the theoretical framework has remained largely unexplored. In this paper, after presenting some classic results on semantic automata in a modern style, we present the first application of semantic automata to polyadic quantification, exhibiting automata for iterated quantifiers. We also discuss the role of semantic automata in (...) linguistic theory and offer new empirical predictions for sentence processing with embedded quantifiers. (shrink)

Quantifier expressions like “many” and “at least” are part of a rich repository of words in language representing magnitude information. The role of numerical processing in comprehending quantifiers was studied in a semantic truth value judgment task, asking adults to quickly verify sentences about visual displays using numerical or proportional quantifiers. The visual displays were composed of systematically varied proportions of yellow and blue circles. The results demonstrated that numerical estimation and numerical reference information are fundamental in encoding the meaning (...) of quantifiers in terms of response times and acceptability judgments. However, a difference emerges in the comparison strategies when a fixed external reference numerosity is used for numerical quantifiers, whereas an internal numerical criterion is invoked for proportional quantifiers. Moreover, for both quantifier types, quantifier semantics and its polarity biased the response direction. Overall, our results indicate that quantifier comprehension involves core numerical and lexical semantic properties, demonstrating integrated processing of language and numbers. (shrink)

Natural languages vary in their quantity expressions, but the variation seems to be constrained by general properties, so-calleduniversals. Their explanations have been sought among constraints of human cognition, communication, complexity, and pragmatics. In this article, we apply a state-of-the-art language coordination model to the semantic domain of quantities to examine whether two quantity universals—monotonicity and convexity—arise as a result of coordination. Assuming precise number perception by the agents, we evolve communicatively usable quantity terminologies in two separate conditions: a numeric-based condition (...) in which agents communicate about a number of objects and a quotient-based condition in which agents communicate about the proportions. We find out that both universals take off in all conditions but only convexity almost entirely dominates the emergent languages. Additionally, we examine whether the perceptual constraints of the agents can contribute to the further development of universals. We compare the degrees of convexity and monotonicity of languages evolving in populations of agents with precise and approximate number sense. The results suggest that approximate number sense significantly reinforces monotonicity and leads to further enhancement of convexity. Last but not least, we show that the properties of the evolved quantifiers match certain invariance properties from generalized quantifier theory. (shrink)

This paper explores the question of what makes diagrammatic representations effective for human logical reasoning, focusing on how Euler diagrams support syllogistic reasoning. It is widely held that diagrammatic representations aid intuitive understanding of logical reasoning. In the psychological literature, however, it is still controversial whether and how Euler diagrams can aid untrained people to successfully conduct logical reasoning such as set-theoretic and syllogistic reasoning. To challenge the negative view, we build on the findings of modern diagrammatic logic and introduce (...) an Euler-style diagrammatic representation system that is designed to avoid problems inherent to a traditional version of Euler diagrams. It is hypothesized that Euler diagrams are effective not only in interpreting sentential premises but also in reasoning about semantic structures implicit in given sentences. To test the hypothesis, we compared Euler diagrams with other types of diagrams having different syntactic or semantic properties. Experiment compared the difference in performance between syllogistic reasoning with Euler diagrams and Venn diagrams. Additional analysis examined the case of a linear variant of Euler diagrams, in which set-relationships are represented by one-dimensional lines. The experimental results provide evidence supporting our hypothesis. It is argued that the efficacy of diagrams in supporting syllogistic reasoning crucially depends on the way they represent the relational information contained in categorical sentences. (shrink)

The semantic automata framework, developed originally in the 1980s, provides computational interpretations of generalized quantifiers. While recent experimental results have associated structural features of these automata with neuroanatomical demands in processing sentences with quantifiers, the theoretical framework has remained largely unexplored. In this paper, after presenting some classic results on semantic automata in a modern style, we present the first application of semantic automata to polyadic quantification, exhibiting automata for iterated quantifiers. We also discuss the role of semantic automata in (...) linguistic theory and offer new empirical predictions for sentence processing with embedded quantifiers. (shrink)

We provide a computational model of semantic alignment among communicating agents constrained by social and cognitive pressures. We use our model to analyze the effects of social stratification and a local transmission bottleneck on the coordination of meaning in isolated dyads. The analysis suggests that the traditional approach to learning—understood as inferring prescribed meaning from observations—can be viewed as a special case of semantic alignment, manifesting itself in the behaviour of socially imbalanced dyads put under mild pressure of a local (...) transmission bottleneck. Other parametrizations of the model yield different long-term effects, including lack of convergence or convergence on simple meanings only. (shrink)

The verification of a sentence against a visual display in experimental conditions reveals a procedure that is driven solely by the properties of the linguistic input and not by the properties of the context (the set-up of the visual display) or extra-linguistic cognition (operations executed to obtain the truth value). This procedure, according to the Interface Transparency Thesis (ITT) (Lidz et al. in Nat Lang Semant 19(3):227–256, 2011), represents the meaning of an expression at the interface with the ‘conceptual-intentional’ system (...) (Chomsky in The minimalist program. MIT Press, Cambridge, 1995). My experiments provide support for the ITT by replicating in Polish and in Bulgarian the findings of Lidz et al. (Nat Lang Semant 19(3):227–256, 2011) for the English quantifier most. We also obtain new evidence that participants are prompted to switch between verification procedures by a change in the linguistic input (a different superlative quantifier entailed by most), but not by a change in the visual input. Thus, the motivation for the subconscious switch in procedures is not to maximize efficiency. Participants use the procedure associated with each quantifier, and in effect, the same display is verified differently depending on which information the visual system is instructed to use by the semantic representation of the sentence. (shrink)

The paper is concerned with the psychological relevance of a logical model for deductive reasoning. We propose a new way to analyze logical reasoning in a deductive version of the Mastermind game implemented within a popular Dutch online educational learning system (Math Garden). Our main goal is to derive predictions about the difficulty of Deductive Mastermind tasks. By means of a logical analysis we derive the number of steps needed for solving these tasks (a proxy for working memory load). Our (...) model is based on the analytic tableaux method, known from proof theory. We associate the difficulty of Deductive Mastermind game-items with the size of the corresponding logical trees obtained by the tableaux method. We derive empirical hypotheses from this model. A large group of students (over 37 thousand children, 5–12 years of age) played the Deductive Mastermind game, which gave empirical difficulty ratings of all 321 game-items. The results show that our logical approach predicts these item ratings well, which supports the psychological relevance of our model. (shrink)

Among the readings available for NL sentences, those where two or more sets of entities are independent of one another are particularly challenging from both a theoretical and an empirical point of view. Those readings are termed here as ‘Independent Set (IS) readings'. Standard examples of such readings are the well-known Collective and Cumulative Readings. (Robaldo, 2011) proposes a logical framework that can properly represent the meaning of IS readings in terms of a set-Skolemization of the witness sets. One of (...) the main assumptions of Robaldo's logical framework, drawn from (Schwarzschild, 1996), is that pragmatics plays a crucial role in the identification of such witness sets. Those are firstly identified on pragmatic grounds, then logical clauses are asserted on them in order to trigger the appropriate inferences. In this paper, we present the results of an experimental analysis that appears to confirm Robaldo's hypotheses concerning the pragmatic identification of the witness sets. (shrink)

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-hard). In particular, we (...) investigate the impact of assuming information structures to be partition-based (rather than arbitrary relational structures) on the complexity of various problems. We focus on the tractability of concrete epistemic tasks and not on epistemic logics describing them. (shrink)

Given current data, only a few binary Boolean operators are expressed in lexically simple fashion in the world's languages: and, or, nor. These do not occur in every combination, for example, nor is not observed by itself. To explain these cross‐linguistic patterns, we propose an encoding of Boolean operators as update procedures to accept or reject information in a context. We define a measure of conceptual simplicity for such updates, on which attested operators are conceptually simpler than the remaining Booleans. (...) Moreover, we show that language evolution selects for the attested lexical inventories by minimizing the complexity of using a lexical inventory compositionally to convey precise information. (shrink)

This paper gives an overview of the common approach to quantification and generalised quantification in formal linguistics and philosophy of language. We point out how this usual general framework represents a departure from empirical linguistic data. We briefly sketch a different idea for proof theory which is closer to the language itself than standard approaches in many aspects. We stress the importance of Hilbert’s operators—the epsilon-operator for existential and tau-operator for universal quantifications. Indeed, these operators are helpful in the construction (...) of a semantic representation which is close to natural language in particular with quantified noun phrases as individual terms. We also define guidelines for the design of proof rules corresponding to generalized quantifiers. (shrink)

We report two experiments which tested whether cognitive capacities are limited to those functions that are computationally tractable (PTIME-Cognition Hypothesis). In particular, we investigated the semantic processing of reciprocal sentences with generalized quantifiers, i.e., sentences of the form Q dots are directly connected to each other, where Q stands for a generalized quantifier, e.g. all or most. Sentences of this type are notoriously ambiguous and it has been claimed in the semantic literature that the logically strongest reading is preferred (Strongest (...) Meaning Hypothesis). Depending on the quantifier, the verification of their strongest interpretations is computationally intractable whereas the verification of the weaker readings is tractable. We conducted a picture completion experiment and a picture verification experiment to investigate whether comprehenders shift from an intractable reading to a tractable reading which should be dispreferred according to the Strongest Meaning Hypothesis. The results from the picture completion experiment suggest that intractable readings occur in language comprehension. Their verification, however, rapidly exceeds cognitive capacities in case the verification problem cannot be solved using simple heuristics. In particular, we argue that during verification, guessing strategies are used to reduce computational complexity. (shrink)

In this paper, we study natural language constructions which were first examined by Barwise: The richer the country, the more powerful some of its officials. Guided by Barwise’s observations, we suggest that conceivable interpretations of such constructions express the existence of various similarities between partial orders such as homomorphism or embedding. Semantically, we interpret the constructions as polyadic generalized quantifiers restricted to finite models. We extend the results obtained by Barwise by showing that similarity quantifiers are not expressible in elementary (...) logic over finite models. We also investigate whether the proposed readings are sound from the cognitive perspective. We prove that almost all similarity quantifiers are intractable. This leads us to first-order variants, which only approximate the strong readings, but are cognitively more plausible. Driven by the question of ambiguity, we recall Barwise’s argumentation in favour of strong readings, enriching it with some arguments of our own. Given that Barwise-like sentences are indeed ambiguous, we use a generalized Strong Meaning Hypothesis to derive predictions for their verification. Finally, we propose a hypothesis according to which conflicting pressures of communication and cognition might give rise to an ambiguous construction, provided that different semantic variants of the construction withstand different pressures involved in its usage. (shrink)

In this study, Knauff and Johnson-Laird's visual impedance hypothesis is applied to the domain of external representations and diagrammatic reasoning. We show that the use of real objects and augmented real objects can control human interpretation and reasoning about conditionals. As participants made inferences, they also moved objects corresponding to premises. Participants who moved real objects made more invalid inferences than those who moved AR objects and those who did not manipulate objects. Our results showed that real objects impeded conditional (...) reasoning, but AR objects did not. These findings are explained by the fact that real objects may over-specify a single state that exists, while AR objects suggest multiple possibilities. (shrink)

A special kind of substitution on languages called iteration is presented and studied. These languages arise in the application of semantic automata to iterations of generalized quantifiers. We show that each of the star-free, regular, and deterministic context-free languages are closed under iteration and that it is decidable whether a given regular or determinstic context-free language is an iteration of two such languages. This result can be read as saying that the van Benthem/Keenan ‘Frege Boundary’ is decidable for large subclasses (...) of natural language quantifiers. We also determine the state complexity of iteration of regular languages. (shrink)

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. (shrink)