A critical survey of the fundamental philosophical issues in the logic and formal ontology of space, with special emphasis on the interplay between mereology (the theory of parthood relations), topology (broadly understood as a theory of qualitative spatial relations such as continuity and contiguity), and the theory of spatial location proper.

We propose in this paper to construct modal logics based on mathematical morphology. The contribution of this paper is twofold. First we show that mathematical morphology can be used to define modal operators in the context of normal modal logics. We propose definitions of modal operators as algebraic dilations and erosions, based on the notion of adjunction. We detail the particular case of morphological dilations and erosions, and of there compositions, as opening and closing. An extension to the fuzzy case (...) is also proposed. Then we show how this can be interpreted for spatial reasoning by using qualitative symbolic representations of spatial relationships (topological and metric ones) derived from mathematical morphology. This allows to establish some links between numerical and symbolic representations of spatial knowledge. (shrink)

Although the computational properties of the Region Connection Calculus RCC-8 are well studied, reasoning with RCC-8 entails several representational problems. This includes the problem of representing arbitrary spatial regions in a computational framework, leading to the problem of generating a realization of a consistent set of RCC-8 constraints. A further problem is that RCC-8 performs reasoning about topological space, which does not have a particular dimension. Most applications of spatial reasoning, however, deal with two- or three-dimensional space. Therefore, a consistent (...) set of RCC-8 constraints might not be realizable within the desired dimension. In this paper we address these problems and develop a canonical model of RCC-8 which allows a simple representation of regions with respect to a set of RCC-8 constraints, and, further, enables us to generate realizations in any dimension d = 1. For three-and higher-dimensional space this can also be done for internally connected regions. (shrink)

Say that space is ‘gunky’ if every part of space has a proper part. Traditional theories of gunk, dating back to the work of Whitehead in the early part of last century, modeled space in the Boolean algebra of regular closed subsets of Euclidean space. More recently a complaint was brought against that tradition in Arntzenius and Russell : Lebesgue measure is not even finitely additive over the algebra, and there is no countably additive measure on the algebra. Arntzenius advocated (...) modeling gunk in measure algebras instead—in particular, in the algebra of Borel subsets of Euclidean space, modulo sets of Lebesgue measure zero. But while this algebra carries a natural, countably additive measure, it has some unattractive topological features. In this paper, we show how to construct a model of gunk that has both nice rudimentary measure-theoretic and topological properties. We then show that in modeling gunk in this way we can distinguish between finite dimensions, and that nothing in lost in terms of our ability to identify points as locations in space. (shrink)

We introduce the bimodal logic , which is the extension of Bennett’s bimodal logic by Grzegorczyk’s axiom □→p)→p and show that the lattice of normal extensions of the intuitionistic modal logic WS5 is isomorphic to the lattice of normal extensions of , thus generalizing the Blok–Esakia theorem. We also introduce the intuitionistic modal logic WS5.C, which is the extension of WS5 by the axiom →, and the bimodal logic , which is the extension of Shehtman’s bimodal logic by Grzegorczyk’s axiom, (...) and show that the lattice of normal extensions of WS5.C is isomorphic to the lattice of normal extensions of. (shrink)

We show how mereotopological notions can be expressed by extending intuitionistic propositional logic with propositional quantification and a strong modal operator. We first prove completeness for the logics wrt Kripke models; then we trace the correspondence between Kripke models and topological spaces that have been enhanced with an explicit notion of expressible region. We show how some qualitative spatial notions can be expressed in topological terms. We use the semantical and topological results in order to show how in some extensions (...) of the logics it is possible to express connectedness, non-emptiness and a set of jointly exhaustive, pairwise disjoint, binary relations that play a significant role in qualitative spatial reasoning. (shrink)

We prove that S4 is complete with respect to Boolean combinations of countable unions of convex subsets of the real line, thus strengthening a 1944 result of McKinsey and Tarski 45 141). We also prove that the same result holds for the bimodal system S4+S5+C, which is a strengthening of a 1999 result of Shehtman 369).

We propose a logic for reasoning about metric spaces with the induced topologies. It combines the 'qualitative' interior and closure operators with 'quantitative' operators 'somewhere in the sphere of radius r.' including or excluding the boundary. We supply the logic with both the intended metric space semantics and a natural relational semantics, and show that the latter (i) provides finite partial representations of (in general) infinite metric models and (ii) reduces the standard '∈-definitions' of closure and interior to simple constraints (...) on relations. These features of the relational semantics suggest a finite axiomatisation of the logic and provide means to prove its EXPTIME-completeness (even if the rational numerical parameters are coded in binary). An extension with metric variables satisfying linear rational (in)equalities is proved to be decidable as well. Our logic can be regarded as a 'well-behaved' common denominator of logical systems constructed in temporal, spatial, and similarity-based quantitative and qualitative representation and reasoning. Interpreted on the real line (with its Euclidean metric), it is a natural fragment of decidable temporal logics for specification and verification of real-time systems. On the real plane, it is closely related to quantitative and qualitative formalisms for spatial representation and reasoning, but this time the logic becomes undecidable. (shrink)

We propose and investigate a uniform modal logic framework for reasoning about topology and relative distance in metric and more general distance spaces, thus enabling the comparison and combination of logics from distinct research traditions such as Tarski’s for topological closure and interior, conditional logics, and logics of comparative similarity. This framework is obtained by decomposing the underlying modal-like operators into first-order quantifier patterns. We then show that quite a powerful and natural fragment of the resulting first-order logic can be (...) captured by one binary operator comparing distances between sets and one unary operator distinguishing between realised and limit distances . Due to its greater expressive power, this logic turns out to behave quite differently from both and conditional logics. We provide finite axiomatisations and ExpTime-completeness proofs for the logics of various classes of distance spaces, in particular metric spaces. But we also show that the logic of the real line is not recursively enumerable. This result is proved by an encoding of Diophantine equations. (shrink)

We prove that S4 is complete with respect to Boolean combinations of countable unions of convex subsets of the real line, thus strengthening a 1944 result of McKinsey and Tarski 45 141). We also prove that the same result holds for the bimodal system S4+S5+C, which is a strengthening of a 1999 result of Shehtman 369).

ABSTRACT A spatial logic is a modal logic of which the models are the mathematical models of space. Successively considering the mathematical models of space that are the incidence geometry and the projective geometry, we will successively establish the language, the semantical basis, the axiomatical presentation, the proof of the decidability and the proof of the completeness of INC, the modal multilogic of incidence geometry, and PRO, the modal multilogic of projective geometry.

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)

Contact relations have been studied in the context of qualitative geometry and physics since the early 1920s, and have recently received attention in qualitative spatial reasoning. In this paper, we present a sound and complete proof system in the style of Rasiowa and Sikorski (1963) for relation algebras generated by a contact relation.