The Aristotelian syllogistic cannot account for the validity of certain inferences involving relational facts. In this paper, we investigate the prospects for providing a relational syllogistic. We identify several fragments based on (a) whether negation is permitted on all nouns, including those in the subject of a sentence; and (b) whether the subject noun phrase may contain a relative clause. The logics we present are extensions of the classical syllogistic, and we pay special attention to the question of whether reductio (...) ad absurdum is needed. Thus our main goal is to derive results on the existence (or nonexistence) of syllogistic proof systems for relational fragments. We also determine the computational complexity of all our fragments. (shrink)

A spatial logic is a formal language interpreted over any class of structures featuring geometrical entities and relations, broadly construed. In the past decade, spatial logics have attracted much attention in response to developments in such diverse fields as Artificial Intelligence, Database Theory, Physics, and Philosophy. The aim of this handbook is to create, for the first time, a systematic account of the field of spatial logic. The book comprises a general introduction, followed by fourteen chapters by invited authors. Each (...) chapter provides a self-contained overview of its topic, describing the principal results obtained to date, explaining the methods used to obtain them, and listing the most important open problems. Jointly, these contributions constitute a comprehensive survey of this rapidly expanding subject. (shrink)

By a fragment of a natural language we mean a subset of thatlanguage equipped with semantics which translate its sentences intosome formal system such as first-order logic. The familiar conceptsof satisfiability and entailment can be defined for anysuch fragment in a natural way. The question therefore arises, for anygiven fragment of a natural language, as to the computational complexityof determining satisfiability and entailment within that fragment. Wepresent a series of fragments of English for which the satisfiabilityproblem is polynomial, NP-complete, EXPTIME-complete,NEXPTIME-complete (...) and undecidable. Thus, this paper represents a casestudy in how to approach the problem of determining the logicalcomplexity of various natural language constructions. In addition, wedraw some general conclusions about the relationship between naturallanguage and formal logic. (shrink)

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and finite satisfiability problems are algorithmically solvable (...) for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

This paper undertakes a re-examination of Sir William Hamilton’s doctrine of the quantification of the predicate . Hamilton’s doctrine comprises two theses. First, the predicates of traditional syllogistic sentence-forms contain implicit existential quantifiers, so that, for example, All p is q is to be understood as All p is some q . Second, these implicit quantifiers can be meaningfully dualized to yield novel sentence-forms, such as, for example, All p is all q . Hamilton attempted to provide a deductive system (...) for his language, along the lines of the classical syllogisms. We show, using techniques unavailable to Hamilton, that such a system does exist, though with qualifications that distinguish it from its classical counterpart. (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 numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite (...) satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic. (shrink)

By a fragment of a natural language, we understand a collection of sentences forming a naturally delineated subset of that language and equipped with a semantics commanding the general assent of its native speakers. By the semantic complexity of such a fragment, we understand the computational complexity of deciding whether any given set of sentences in that fragment represents a logically possible situation. In earlier papers by the first author, the semantic complexity of various fragments of English involving at most (...) transitive verbs was investigated. The present paper considers various fragments of English involving ditransitive verbs and determines their semantic complexity. (shrink)

We extend the language of the classical syllogisms with the sentence-forms “At most 1 p is a q” and “More than 1 p is a q”. We show that the resulting logic does not admit a finite set of syllogism-like rules whose associated derivation relation is sound and complete, even when reductio ad absurdum is allowed.

A topological constraint language is a formal language whose variables range over certain subsets of topological spaces, and whose nonlogical primitives are interpreted as topological relations and functions taking these subsets as arguments. Thus, topological constraint languages typically allow us to make assertions such as “region V1 touches the boundary of region V2”, “region V3 is connected” or “region V4 is a proper part of the closure of region V5”. A formula f in a topological constraint language is said to (...) be satisfiable if there exists an assignment to its variables of regions from some topological space under which φ is made true. This paper introduces a topological constraint language which, in addition to the usual mechanisms for expressing Boolean combinations of regions and their topological closures, includes primitives for bounding the number of components of a region. We call this language T CC, a rough acronym for “topological constraint language with component counting”. Our main result is that the problem of determining the satisfiability of a T CC-formula is NEXPTIME-complete. (shrink)

We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$. We show that, for (...) $m \ge 2$, this subfragment forces $\left\lfloor {m/2} \right\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$-NExpTime-hard. We further establish that, for $m \ge 3$, any satisfiable ${\cal F}{{\cal L}^m}$-formula has a model of at most -tuply exponential size, whence the satisfiability problem for this fragment is in -NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for ${\cal F}{{\cal L}^m}$ for all $m \le 4$. (shrink)

Controlled languages are regimented fragments of natural languagedesigned to make the processing of natural language more efficient andreliable. This paper defines a controlled language, E2V, whose principalgrammatical resources include determiners, relative clauses, reflexivesand pronouns. We provide a formal syntax and semantics for E2V, in whichanaphoric ambiguities are resolved in a linguistically natural way. Weshow that the expressive power of E2V is equal to that of thetwo-variable fragment of first-order logic. It follows that the problemof determining the satisfiability of a set (...) of E2V sentences is NEXPTIMEcomplete. We show that E2V can be extended in various ways withoutcompromising these complexity results; however, relaxing our policy onanaphora resolution renders the satisfiability problem for E2Vundecidable. Finally, we argue that our results have a bearing on thebroader philosophical issue of the relationship between natural andformal languages. (shrink)

We consider two‐variable, first‐order logic in which a single distinguished predicate is required to be interpreted as a transitive relation. We show that the finite satisfiability problem for this logic is decidable in triply exponential non‐deterministic time. Complexity falls to doubly exponential non‐deterministic time if the transitive relation is constrained to be a partial order.

A region-based model of physical space is one in which the primitive spatial entities are regions, rather than points, and in which the primitive spatial relations take regions, rather than points, as their relata. Historically, the most intensively investigated region-based models are those whose primitive relations are topological in character; and the study of the topology of physical space from a region-based perspective has come to be called mereotopology. This paper concentrates on a mereotopological formalism originally introduced by Whitehead, which (...) employs a single primitive binary relation C(x, y) (read: "x is in contact with y"). Thus, in this formalism, all topological facts supervene on facts about contact. Because of its potential application to theories of qualitative spatial reasoning, Whitehead's primitive has recently been the subject of scrutiny from within the Artificial Intelligence community. Various results regarding the mereotopology of the Euclidean plane have been obtained, settling such issues as expressive power, axiomatization and the existence of alternative models. The contribution of the present paper is to extend some of these results to the mereotopology of three-dimensional Euclidean space. Specifically, we show that, in a first-order setting where variables range over tame subsets of ℝ³, Whitehead's primitive is maximally expressive for topological relations; and we deduce a corollary constraining the possible region-based models of the space we inhabit. (shrink)

We consider the two‐variable fragment of first‐order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime‐complete. We further show that the corresponding problems for two‐variable first‐order logic with counting and two equivalences are both undecidable.

The fluted fragment is a fragment of first-order logic (without equality) in which, roughly speaking, the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that this fragment has the finite model property. We consider extensions of the fluted fragment with various numbers of transitive relations, as well as the equality predicate. In the presence of one transitive relation (together with equality), the finite model property is lost; nevertheless, (...) we show that the satisfiability and finite satisfiability problems for this extension remain decidable. We also show that the corresponding problems in the presence of two transitive relations (with equality) or three transitive relations (without equality) are undecidable, even for the two-variable sub-fragment. (shrink)

The relational syllogistic extends the classical syllogistic by allowing predicate phrases of the forms “rs every q”, “rs some q” and their negations, where q is a common noun and r a transitive verb. It is known that both the classical and relational syllogistic admit a finite set of syllogism-like rules whose associated derivation relation is sound and complete. In this article, we extend the classical and relational syllogistic by allowing ‘guarded’ predicate phrases of the form “rs onlyqs”, and their (...) negations. We show that, in both cases, the resulting logic is pspace-complete. It follows, on the assumption that NPTIME≠PSPACE\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {nptime}\ne \textsc {pspace}$$\end{document}, that neither extension admits a finite set of syllogism-like rules whose associated derivation relation is sound and complete, even when reductio ad absurdum is allowed. We also show that further extending these systems with noun-complementation in sentence-subjects results in logics which are exptime-complete. (shrink)

This paper employs epistemic logic to investigate the philosophical foundations of Bayesian updating in belief revision. By Bayesian updating, we understand the tenet that an agent's degrees of belief—assumed to be encoded as a probability distribution—should be revised by conditionalization on the agent's total knowledge up to that time. A familiar argument, based on the construction of a diachronic Dutch book, purports to show that Bayesian updating is the only rational belief-revision policy. We investigate the conditions under which the premises (...) of this argument might be satisfied. Specifically, we consider the case of an artificial agent whose language (of thought) features a modal operator TK, where TK ψ has the interpretation “My total knowledge is ψ”. We show that every proposition of the form TK ψis epistemically categorical: it determines, for every proposition φ in the agent's language, whether the agent knows that φ. We argue that, for certain artificial agents employing such a language, the diachronic Dutch book argument for Bayesian updating is on firm ground. (shrink)

Modal logic is one of the most widely applied logical formalisms. Systems of modal logic are being used in many disciplines, ranging from artificial intelligence, computer science, mathematics, formal grammar and semantics to philosophy. This volume presents substantial recent advances in the relational and the algorithmic treatment of modal logics. It contains papers from the fifth conference on "Advances in Modal logic," held in Manchester (UK) in September 2004. Written by leading experts in the field, the present book is indispensable (...) for any advanced student and researcher in pure and applied modal logic. (shrink)