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)

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)

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)

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.

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.

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)

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.

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 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.

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)

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 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].

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 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)

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

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)

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 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)

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)

Prof. Ruth Barcan Marcus created quantified modal logic in 1946. She extended the Lewis calculus S2 to cover quantification. Quantified modal logic became an essential tool for the rigorous study of natural language in the hands of R. Montague in the late sixties. Some complex phenomena cannot be properly handled at the level of sentences. Recent researches in formal semantics have concentrated on discourse and led to a rich amount of results. Logical theories introduced for the logical study of programs (...) play an important role in these developments. We shall present a detailed account of the connection between dynamic logic and “static” logic. The core of the paper will be the translation of dynamic logic into S5. Developping an insight due to Prof. J. van Eijck, We shall offer a simplified version of the latter translation. The paper also relates to P. Gärdenfors' Knowledge in Flux. (shrink)

In 1985, van den Dries showed that the theory of the reals with a predicate for the integer powers of two admits quantifier elimination in an expanded language, and is hence decidable. He gave a model-theoretical argument, which provides no apparent bounds on the complexity of a decision procedure. We provide a syntactical argument that yields a procedure that is primitive recursive, although not elementary.

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)

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)

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)

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.

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)

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.

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 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 here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not (...) always true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]. (shrink)

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.

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)

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.

The phenomenon of the quantified self, which is especially addressed by sociology and medical humanities, is still quite disregarded by philosophy. Yet, the philosophical issues it raises are various and meaningful, from the realm of epistemology to the realm of ethics. Moreover, it may be read as a key symptom to investigate the complex technological era in which we live, starting from the meaning of contemporary technology itself from a philosophical perspective. I shall focus on one of the epistemological issues (...) raised by the phenomenon of the quantified self by arguing that it may be read in terms of epistemological anarchism, which also leads to other epistemological issues, such as a possibly detectable crisis of the notions of knowledge in general and science in particular as founded on the relationship between particularity and universality, as well as between reality and ideality. I shall select cases that are peculiarly representative of the founding epistemological stance I shall focus on. Yet, the reason why they deserve special attention is that they are also representative of an increasingly widespread attitude characterising not only the community of the quantified self but also, at least to some extent, anyone of us who may happen to use technologies to try to self-diagnose. (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)