Non-Classical Spatial Logics

Non-classical logics can be used in order to encode spatial notions; this may result in useful simplifications of the reasoning, especially (but not only) in case the appropriate logic is decidable.

Decidable encodings for RCC.

Propositional intuitionistic logic and the S4/S5 modal logic can be both used in order to give an encoding to the RCC8 relations and their algebra (see 1, 2, 3, 4).

Modal logic for spatial vagueness.

A multi-modal propositional system based on S5 can be used in order to model aspects of spatial knowledge related to vagueness and to the egg-yolk theory for regions with indeterminate boundaries (see 1, 2).

Paraconsistent logic and granularity.

Logic based on bi-Heyting algebras admit a form of paraconsistent negation, that can be important for modelling aspects of spatial knowledge related to difference in granularity (see 1, 2).

Logic for connectedness.

Intuitionistic second-order propositional logic can be used to express a form of topological connectedness, in order to represent the property of being all of one piece (see 1, 2).

Relevant Links

A past project undertaken at Leeds looked at the application of decidable non-classical spatial logics to reasoning about physical systems:
  • Logical Theories and Decision Procedures for Reasoning about Phyiscal Systems, EPSRC project GR/K65041 (August 1995 - December 1998).

    • Key Publications

  • Determining Consistency of Topological Relations
    B. Bennett
    Constraints, vol. 3 (1998).
    [BibTeX] [PostScript] [gzipped PostScript]

  • Logical Representations for Automated Reasoning about Spatial Relationships
    B. Bennett
    PhD thesis (1997, University of Leeds).
    [BibTeX] [gzipped PostScript]

  • Modal Logics for Qualitative Spatial Reasoning
    B. Bennett
    Bulletin of the Interest Group in Pure and Applied Logic (IGPL), vol. 4, n.1 (1996).
    [BibTeX]

  • Spatial Reasoning with Propositional Logics
    B. Bennett
    Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference (KR94), edited by Doyle, J and Sandewall, E and Torasso, P, Morgan Kaufmann, San Francisco, CA., (1994).
    [BibTeX] [PostScript] [gzipped PostScript]

  • Multi-Dimensional Modal Logic as a Framework for Spatio-Temporal Reasoning
    B. Bennett, A. G. Cohn, F. Wolter and M. Zakharyaschev
    Applied Intelligence, 17 (3), pp 239-251, (2002).
    [BibTeX] [PostScript] [gzipped PostScript]
    [ DOI (link to official publication)]

  • Boolean Connection Algebras: A New Approach to the Region-Connection Calculus
    J. G. Stell
    Artificial Intelligence, 122 , pp 111-136, (2000).
    [BibTeX]

  • The Representation of Discrete Multi-resolution Spatial Knowledge
    J.G. Stell
    Proc. KR2000, A.G. Cohn, F. Giunchiglia, B. Selman (Eds.), Morgan Kaufmann Pub. (2000).

  • The Algebraic Structure of Sets of Regions
    J.G. Stell, M.F. Worboys
    Proc. COSIT'97, S.C. Hirtle A.U. Frank (Eds.), LNCS vol. 1329 (1997).

  • Spatial Reasoning with Intuitionistic Logic
    P. Torrini
    PhD report (May 2001; revised version of the extended abstract presented at ARW2001)
    [PostScript]

  • Spatial Reasoning with Intuitionistic Logic (slides)
    P. Torrini
    presented at the IRR seminar (AI - Division of Informatics, University of Edinburgh, May 2001)
    [PostScript]

  • Mereotopology in 2nd-Order and Modal Extensions of Intuitionistic Propositional Logic
    P. Torrini, J. G. Stell and B. Bennett
    Journal of Applied Non-Classical Logics, 12 , pp 495-525, (2002).
    [BibTeX] [PDF]