We refine the constructions of Ferrante-Rackoff and Solovay on iterated definitions in first-order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier-free case and in the case of purely existential or universal quantifiers, we show (...) that Ω quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao-Håstad switching lemma. (shrink)

In this paper we continue the study of the theories IΔ n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class of theories such that IΔ n+1 (T) is Π n+2 –axiomatizable. In particular, IΔ n+1 (IΔ n+1 ) gives an axiomatization of Th Π n+2 (IΔ n+1 ) and is not finitely axiomatizable. This fact relates the fragment IΔ n+1 (IΔ n+1 ) (...) to induction rule for Δ n+1 –formulas. Our arguments, involving a construction due to R. Kaye (see [9]), provide proofs of Parsons’ conservativeness theorem (see [16]) and (a weak version) of a result of L.D. Beklemishev on unnested applications of induction rules for Π n+2 and Δ n+1 formulas (see [2]). (shrink)

In “Complex Demonstratives: A Quantificational Account” (MIT Press 2001) (henceforth CD), I argued that complex demonstratives are quantifiers. Many philosophers had held that demonstratives, both simple and complex, are referring terms. Since the publication of CD various objections to the account of complex demonstratives I defended in it have been raised. In the present work, I lay out these objections and respond to them.

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

The satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly.

The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to (...) the problem of computational complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (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)

We study the computational complexity of reciprocal sentences with quantified antecedents. We observe a computational dichotomy between different interpretations of reciprocity, and shed some light on the status of the so-called Strong Meaning Hypothesis.

We study the computational complexity of the model checking problem for quantifier-free dependence logic ${(\mathcal{D})}$ formulas. We characterize three thresholds in the complexity: logarithmic space (LOGSPACE), non-deterministic logarithmic space (NL) and non-deterministic polynomial time (NP).

We shall be concerned with two natural expansions of the quantifier-free ‘polynomial’ probability logic of Fagin et al. (A logic for reasoning about probabilities, Inform Comput, 1990; 87:78–128). One of these, denoted by ${\textsf{QPL}}^{\textrm{e}}$, is obtained by adding quantifiers over arbitrary events, and the other, denoted by $\underline{{\textsf{QPL}}}^{\textrm{e}}$, uses quantifiers over propositional formulas—or equivalently, over events expressible by such formulas. The earlier proofs of the complexity lower bound results for ${\textsf{QPL}}^{\textrm{e}}$ and $\underline{{\textsf{QPL}}}^{\textrm{e}}$ relied heavily on multiplication, and therefore (...) on the polynomiality of the basic parts. We shall obtain the same lower bounds for natural fragments of ${\textsf{QPL}}^{\textrm{e}}$ and $\underline{{\textsf{QPL}}}^{\textrm{e}}$ in which only linear combinations of a very special form are allowed. Also, it will be studied what happens if we add quantifiers over reals. (shrink)

This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.

The following result is an approximation to the answer of the question of Kokorin about decidability of a quantifier-free theory of field of rational numbers. Let Q0 be a subset of the set of all rational numbers which contains integers 1 and −1. Let be a set containing Q0 and closed by the functions of addition, subtraction and multiplication. For example coincides with Q0 if Q0 is the set of all binary rational numbers or the set of all decimal (...) rational numbers. It is clear that , where Z is the set of all integers and Q is the set of all rational numbers. A negationless theory uses only conjunction and disjunction as logical connectives. Let T be a quantifier-free negationless elementary theory of signature , where Pol is the list of all polynomials with rational coefficients from Q0 in which exponent of the polynomials and rational coefficients are written in binary number system. Theorem 1. Theory T is NP-hard and if is everywhere dense then the theory T is decidable by an algorithm which belongs to EXPTIME. The set of all rational numbers or the set of all binary rational numbers may be taken instead of . The quantifier-free negationless theory of the field of rational numbers may be regarded as a base of constructive mathematics. (shrink)

We prove that PTIME generalized quantifiers are closed under Boolean operations, iteration, cumulation and resumption. -/- .

We prove that the sets of standard tautologies of predicate Product Logic and of predicate Basic Logic, as well as the set of standard-satisfiable formulas of predicate Basic Logic are not arithmetical, thus finding a rather satisfactory solution to three problems proposed by Hájek in [H01].

We say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M' over the same vocabulary if Φ is true on M but false on M'. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M'. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M'. We prove that every n-element structure M is identifiable by a (...) formula with quantifier rank less than (1- 1/2k)n+k²-k+4 and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than (1-1/2k²+2)n+k quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than n-√ n+k²+k quantifiers suffice to identify M and, as long as we keep the number of universal quantifiers bounded by a constant, at total n-O(√ n) quantifiers are necessary. (shrink)

This paper investigates the effects of (surface) DP-internal quantifying expressions on semantic interpretation. In particular, I investigate two syntactic constructions in which an adjective takes scope out of its embedding DP, thus raising an interesting question for strict compositionality. Regarding the first construction, I follow Larson (1999) and assume that the adjective incorporates into the determiner of its DP, forming a complex quantifier [D+A]. I present new evidence in favor of this analysis. Since Larson's semantic analysis of complex quantifiers (...) [D+A] makes a wrong prediction, I propose an alternative, empirically more adequate analysis that treats D+A compounds as pluractional quantifiers in the sense of Lasersohn (1995). Finally, I turn to the second construction, arguing that – despite superficial similarities to the first construction - it should not be analyzed in terms of complex quantifier formation, but in terms of LF-movement of the adjective to Spec,DP. The discussion suggests that there is more than one way for DP-internal modifiers to take DP-external scope in natural language. (shrink)

This paper generalizes Muddy Children puzzle to account for a large class of possible public announcements with various quantifiers. We identify conditions for solvability of the extended puzzle, with its classical version as a particular case. The characterization suggests a novel way of modeling multi-agent epistemic reasoning. The framework is based on the concept of number triangle. The advantage of our approach over more general formalizations in epistemic logics, like Dynamic Epistemic Logic, is that it gives models of linear size (...) w.r.t. the number of agents. Therefore, it is computationally plausible for modeling agents’ internal perspective. (shrink)

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 the possible meanings and the inferential (...) power of quantifier expressions by logical means. The classic version was developed in the 1980s, at the interface of linguistics, mathematics and philosophy. Before this volume, advances in "classic" generalized quantifier theory mainly focused on logical questions and their applications to linguistics, this volume adds a computational component, the third pillar of language use and logical activity. This book is essential reading for researchers in linguistics, philosophy, cognitive science, logic, AI, and computer science. (shrink)

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of (...) modal systems and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely. (shrink)

This paper argues for a different logical form for complex demonstratives, given that the quantificational account is correct. In itself that is controversial, but two aspects will be assumed. Firstly, there are arguments to believe that complex demonstratives have quantificational uses. Specifically, there are syntactic arguments. Secondly, a uniform semantics is preferable to a semantics of ambiguity. Given this, the proposed logical forms for complex demonstratives that are prevalent do not respect a fundamental property of quantifiers: permutation invariance. The reason (...) for this is the attempt to retain, in the logical forms proposed, the strong intuitions of reference that uses of complex demonstratives display. The paper suggests that the directly referential intuitions surrounding complex demonstratives cannot be taken to be part of the semantics of the expression. There appears to be no need to do so, either. The paper defends the new logical form against various objections. (shrink)

Hyperbolic geometry can be axiomatized using the notions of order andcongruence (as in Euclidean geometry) or using the notion of incidencealone (as in projective geometry). Although the incidence-based axiomatizationmay be considered simpler because it uses the single binary point-linerelation of incidence as a primitive notion, we show that it issyntactically more complex. The incidence-based formulation requires some axioms of the quantifier-type forallexistsforall, while the axiom system based on congruence and order can beformulated using only forallexists-axioms.

Perceptual tasks such as object matching, mammogram interpretation, mental rotation, and satellite imagery change detection often require the assignment of correspondences to fuse information across views. We apply techniques developed for machine translation to the gaze data recorded from a complex perceptual matching task modeled after fingerprint examinations. The gaze data provide temporal sequences that the machine translation algorithm uses to estimate the subjects' assumptions of corresponding regions. Our results show that experts and novices have similar surface behavior, such as (...) the number of fixations made or the duration of fixations. However, the approach applied to data from experts is able to identify more corresponding areas between two prints. The fixations that are associated with clusters that map with high probability to corresponding locations on the other print are likely to have greater utility in a visual matching task. These techniques address a fundamental problem in eye tracking research with perceptual matching tasks: Given that the eyes always point somewhere, which fixations are the most informative and therefore are likely to be relevant for the comparison task? (shrink)

We show that plane hyperbolic geometry, expressed in terms of points and the ternary relation of collinearity alone, cannot be expressed by means of axioms of complexity at most ∀∃∀, but that there is an axiom system, all of whose axioms are ∀∃∀∃ sentences. This remains true for Klingenberg's generalized hyperbolic planes, with arbitrary ordered fields as coordinate fields.

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of (...) modal systems and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely. (shrink)

Extending previous results from work on the complexity of cut elimination for the sequent calculus LK, we discuss the role of quantifier alternations and develop a measure to describe the complexity of cut elimination in terms of quantifier alternations in cut formulas and contractions on such formulas.

Quantified modal logic has reputation for complexity. Completeness results for the various systems appear piecemeal. Different tactics are used for different systems, and success of a given method seems sensitive to many factors, including the specific combination of choices made for the quantifiers, terms, identity, and the strength of the underlying propositional modal logic. The lack of a unified framework in which to view QMLs and their completeness properties puts pressure on those who develop, apply, and teach QML to (...) work with the simplest systems, namely those that adopt the Barcan Formulas and predicate logic rules for the quantifiers. In these systems, the quantifier ranges over a fixed domain of possible individuals, so advocates of these logics are sometimes called possibilists. A literature has grown up rationalizing the choice of possibilist logics despite ordinary intuitions that the resulting theorems are too strong.Williamson even takes the view that the complications to be faced within the weaker logics “are a warning sign of philosophical error”. It is the purpose of this paper to show that abandonment of the weaker QMLs is excessively fainthearted, since most QMLs can be given relatively simple formulations within one general framework. Given the straightforward nature of the systems and their completeness results, the purported complications evaporate, along with any philosophical warnings one might have associated with them. (shrink)

In economic researches, much effort was devoted to the problem of how to increase the economics of countries. However, the development of a country may fluctuate a lot due to international and domestic problems. Thus, we should also evaluate the robustness of countries against unexpected economic recessions. In this paper, we use perturbation to quantify the robustness of countries using two renowned algorithms: method of reflections and fitness-complexity method. The robustness characterizes the stability of countries’ competitiveness against economic recessions. (...) The experiments in the international trade networks show that FCM could characterize the robustness better than MR. High fitness countries of FCM have strong robustness against economic crises, which enlarges the application fields of FCM. Additionally, we simulate the trade conflict between USA and China. The simulation results show that China suffers much in the trade conflict, while USA loses very little and has strong robustness in this conflict. (shrink)

The goal of this paper is to show that the information carried by a structural representation can be decomposed into the information carried by its component parts. In particular, the relations between the components of a structural representation carry quantifiable information about the relations between components of their signifieds. It follows that the information carried by cognitive structural representations, including cognitive maps, can in principle be quantified and decomposed. This is perhaps surprising given that the formal tools of communication theory (...) have typically only been applied to simpler representation-like states without significant structure, such as detectors or indicators. In the final section I consider using computational complexity theory to capture the processing advantages afforded by structural representation. (shrink)

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as "every coalition satisfying property P can achieve φ" and "there exists a coalition C satisfying property P such that C can achieve φ". We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it is (...) nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

Cognition is context-sensitive, as the same sensory information is processed differently depending on its context (e.g., on its probabilistic association with goal-directed actions and their outcomes). Despite this, the concept of context in studies of higher-order cognitive processes, like cognitive control, is often simplified to nominal stimulus categories (like a target vs. distractor). Here we propose that quantifying contextual information to model cognitive demands is (1) fruitful as it can provide novel insight into the nature of cognitive control, (2) accessible (...) as simple probability models offer a tool for quantifying context and (3) analytically useful as a fine-grained quantification of context can be entered into more complex models as regressors that allow a direct way of appropriately exploring many of the defining tenants of cognitive control (e.g., rapidly changing trial-by-trial neural dynamics). Here, we briefly describe the logic of using context-sensitive measures of cognitive control and highlight recent studies from this approach using simple information theory metrics. (shrink)

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

This dissertation investigates the ways in which natural language restricts the domains of quantifiers. Adverbs of quantification are analyzed as quantifying over situations. The domain of quantifiers is pragmatically constrained: apparent processes of "semantic partition" are treated as pragmatic epiphenomena. The introductory Chapter 1 sketches some of the background of work on natural language quantification and begins the analysis of adverbial quantification over situations. Chapter 2 develops the central picture of "semantic partition" as a side-effect of pragmatic processes of anaphora (...) resolution. I argue that the apparent effects of topic/focus articulation and presuppositional information on the interpretation of quantifiers are not the result of a direct and local mechanism of sentence grammar. Instead, I develop an analysis where the link is established via the anaphoric dependence of quantifier domains on the discourse context. Chapter 3 discusses the analysis of conditional clauses as quantifier restrictors, concentrating on the question whether conditional clauses restrict quantifiers directly or indirectly. A treatment is explored which has if-clauses constrain the value of the hidden domain variable of the restricted quantifier. Chapter 4, on unless-clauses, and Chapter 5, on only if- and even if-clauses, present some issues in the compositional analysis of complex conditional clauses. These chapters significantly expand the data coverage of the theory of A-quantification. Building on previous work of mine on exceptives, I analyze unless-clauses as exceptive operators on A-quantifiers. The analysis of only if-clauses, treated as conditional clauses that combine if with the focus adverb only, unearthes some interesting new properties. Chapter 6, finally, examines the phenomenon of donkey-anaphora in the light of the results of the previous chapters. I show that a solution to the proportion problem may become possible once we combine the situation-semantic approach to adverbial quantification with the pragmatic theory developed in Chapter 2 and further elaborated in the analysis of donkey anaphora in complex conditionals. (shrink)

Information‐theoretic complexity metrics, such as Surprisal (Hale, 2001; Levy, 2008) and Entropy Reduction (Hale, 2003), are linking hypotheses that bridge theorized expectations about sentences and observed processing difficulty in comprehension. These expectations can be viewed as syntactic derivations constrained by a grammar. However, this expectation‐based view is not limited to syntactic information alone. The present study combines structural and non‐structural information in unified models of word‐by‐word sentence processing difficulty. Using probabilistic minimalist grammars (Stabler, 1997), we extend expectation‐based models to (...) include frequency information about noun phrase animacy. Entropy reductions derived from these grammars faithfully reflect the asymmetry between subject and object relatives (Staub, 2010; Staub, Dillon, & Clifton, 2017), as well as the effect of animacy on the measured difficulty profile (Lowder & Gordon, 2012; Traxler, Morris, & Seely, 2002). Visualizing probability distributions on the remaining alternatives at particular parser states allows us to explore new, linguistically plausible interpretations for the observed processing asymmetries, including the way that expectations about the relativized argument influence the processing of particular types of relative clauses (Wagers & Pendleton, 2016). (shrink)

An application of the Method of Analysis of Relational Complexity (MARC) to suppositional reasoning in the knight-knave task is outlined. The task requires testing suppositions derived from statements made by individuals who either always tell the truth or always lie. Relational complexity (RC) is defined as the number of unique entities that need to be processed in parallel to arrive at a solution. A selection of five ternary and five quaternary items were presented to 53 psychology students using (...) a pencil and paper format. A computer-administered version was presented to 50 students. As predicted, quaternary problems were associated with higher error rates and longer response times than ternary problems. The computer-administered form was more difficult than the pencil and paper version of the test. These differences are discussed in terms of RC theory and alternative processing accounts. Together, they indicate that the relational complexity metric is a useful and parsimonious way to quantify complexity of reasoning tasks. (shrink)

Comparative quantifiers, such as more than three books, cannot take scope over any quantifier in subject position if they occupy object position. This is clearly different from the behavior of other quantifiers (e.g., universal quantifiers). This paper argues that this scope puzzle is due to a more complex internal structure of comparative quantifiers than other quantifiers. In the decompositional approach that I pursue, comparative quantifiers are decomposed into two generalized quantifiers (i.e., in the case above, the comparative operator er (...) than three and the DP many books). In this approach, obligatory narrow scope of comparative quantifiers in object position is a consequence of the interplay of the independently motivated principles of grammar that also constrain other quantifiers. On the basis of the scope puzzle, I specifically argue for two constraints on Scope Shifting Operations (SSOs) a locality condition on SSOs and Scope Economy, proposed by Fox (2000), which prohibits SSOs that have no effect on semantic interpretation. Thus, I argue that the apparently peculiar facts of comparative quantifiers are, in fact, additional evidence for the core properties of SSOs. (shrink)

Some things look more complex than others. For example, a crenulate and richly organized leaf may seem more complex than a plain stone. What is the nature of this experience—and why do we have it in the first place? Here, we explore how object complexity serves as an efficiently extracted visual signal that the object merits further exploration. We algorithmically generated a library of geometric shapes and determined their complexity by computing the cumulative surprisal of their internal skeletons—essentially (...) quantifying the “amount of information” within each shape—and then used this approach to ask new questions about the perception of complexity. Experiments 1–3 asked what kind of mental process extracts visual complexity: a slow, deliberate, reflective process (as when we decide that an object is expensive or popular) or a fast, effortless, and automatic process (as when we see that an object is big or blue)? We placed simple and complex objects in visual search arrays and discovered that complex objects were easier to find among simple distractors than simple objects are among complex distractors—a classic search asymmetry indicating that complexity is prioritized in visual processing. Next, we explored the function of complexity: Why do we represent object complexity in the first place? Experiments 4–5 asked subjects to study serially presented objects in a self‐paced manner (for a later memory test); subjects dwelled longer on complex objects than simple objects—even when object shape was completely task‐irrelevant—suggesting a connection between visual complexity and exploratory engagement. Finally, Experiment 6 connected these implicit measures of complexity to explicit judgments. Collectively, these findings suggest that visual complexity is extracted efficiently and automatically, and even arouses a kind of “perceptual curiosity” about objects that encourages subsequent attentional engagement. (shrink)