On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus

The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question for the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the ``Region Connection Calculus'''' RCC-8. We extend Bennett''s encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.

• Publication year

  1999

• Venue

  Artificial Intelligence

• Publication date

  1999-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0004-3702(99)00002-8
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Efficient Methods for Qualitative Spatial Reasoning

  2001cited by this paper
• Foundations of Spatioterminological Reasoning with Description Logics

  1998cited by this paper
• Combining Topological and Qualitative Size Constraints for Spatial Reasoning

  1998cited by this paper
• Efficient Methods for Qualitative Spatial Reasoning

  1998cited by this paper
• When does a Composition Table Provide a Complete and TractableProof Procedure for a Relational Constraint Language ?

  1997cited by this paper
• Qualitative Spatial Representation and Reasoning Techniques

  1997cited by this paper
• Combining multiple representations in a spatial reasoning system

  1997cited by this paper
• Logical representations for automated reasoning about spatial relationships

  1997influential reference
• A Complete Classification of Tractability in RCC-5

  1997cited by this paper
• Modal Logics for Qualitative Spatial Reasoning

  1996influential reference
• Computational Properties of Qualitative Spatial Reasoning: First Results

  1995cited by this paper
• Topological Inference

  1995influential reference
• Handbook of Logic in Artificial Intelligence and Logic Programming, Volume2, Deduction Methodologies

  1994cited by this paper
• Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra

  1994cited by this paper
• On binary constraint problems

  1994cited by this paper
• Complexity and algorithms for reasoning about time: a graph-theoretic approach

  1993cited by this paper
• Vitra guide: multimodal route descriptions for computer assisted vehicle navigation

  1993cited by this paper
• A Spatial Logic based on Regions and Connection

  1992influential reference
• Qualitative Simulation Based on a Logical Formalism of Space and Time

  1992cited by this paper
• Computing Transivity Tables: A Challenge For Automated Theorem Provers

  1992cited by this paper
• Reasoning about Binary Topological Relations

  1991cited by this paper
• Constraint propagation algorithms for temporal reasoning: a revised report

  1989cited by this paper
• Constraint Satisfaction

  1985influential reference
• The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems

  1985cited by this paper
• Proof Methods for Modal and Intuitionistic Logics

  1983cited by this paper
• Maintaining knowledge about temporal intervals

  1983cited by this paper
• The complexity of satisfiability problems

  1978cited by this paper
• The Correspondence Theory

  1978cited by this paper
• Consistency in Networks of Relations

  1977influential reference
• An Introduction to Modal Logic

  1977cited by this paper
• Unit Refutations and Horn Sets

  1974cited by this paper
• Networks of constraints: Fundamental properties and applications to picture processing

  1974influential reference
• The complexity of theorem-proving procedures

  1971cited by this paper
• Basic modal logic

  1967cited by this paper
• Exploring Naive Topology : modelling the force pump

  year unknowncited by this paper

• A Logical–Algebraic Approach to Revising Formal Ontologies: Application in Mereotopology

  2024cites this paper
• Querying large-scale knowledge graphs using Qualitative Spatial Reasoning

  2024cites this paper
• A Paraconsistency Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning

  2023cites this paper
• Block Algebra-Based Consistency Checking With Cardinal Direction Relations in 3D Space

  2023influential citation
• General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs

  2022cites this paper
• E(cid:14)cient Methods for Qualitative Spatial Reasoning

  2022influential citation
• Spatial concept learning and inference on geospatial polygon data

  2022cites this paper
• HyperQuaternionE: A hyperbolic embedding model for qualitative spatial and temporal reasoning

  2022cites this paper
• Computational Short Cuts in Infinite Domain Constraint Satisfaction

  2022influential citation
• Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms

  2021cites this paper
• Complexity of Infinite-Domain Constraint Satisfaction

  2021influential citation
• Data-driven agriculture for rural smallholdings

  2020cites this paper
• Extended Distributive Contact Lattices and Extended Contact Algebras

  2020cites this paper
• A spatio-temporalisation of ALC(D) and its translation into alternating automata augmented with spatial constraints

  2020cites this paper
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

  2020cites this paper
• A Generalised Approach for Encoding and Reasoning with Qualitative Theories in Answer Set Programming

  2020cites this paper
• Relational Representation Theorems for Extended Contact Algebras

  2020cites this paper
• Buchi automata augmented with spatial constraints: simulating an alternating with a nondeterministic and deciding the emptiness problem for the latter

  2020cites this paper
• Contact Join-semilattices

  2020cites this paper
• Network satisfaction for symmetric relation algebras with a flexible atom

  2020cites this paper
• Distributive contact join-semilattices

  2020cites this paper
• Lower Bounds and Faster Algorithms for Equality Constraints

  2020cites this paper
• Dynamic spatio‐temporal logic based on RCC‐8

  2020cites this paper
• TextMap: A general purpose visualization system

  2020cites this paper
• On the computational realization of formal ontologies: Formalizing an ontology of instantiation in spacetime using Isabelle/HOL as a case study

  2019cites this paper
• Representing and reasoning fuzzy spatio- temporal knowledge with description logics: A survey

  2019cites this paper
• Representation theorems for extended contact algebras based on equivalence relations

  2019cites this paper
• Hardness of Network Satisfaction for Relation Algebras with Normal Representations

  2019cites this paper
• Une approche SAT incrémentale pour raisonner efficacement sur les réseaux de contraintes qualitatives

  2019cites this paper
• The TextMap General Purpose Visualization System: Core Mechanism and Case Study

  2019cites this paper
• On the Utility of Neighbourhood Singleton-Style Consistencies for Qualitative Constraint-Based Spatial and Temporal Reasoning

  2019cites this paper
• Qualitatively correct bintrees: an efficient representation of qualitative spatial information

  2019cites this paper
• Constants and finite unary relations in qualitative constraint reasoning

  2018cites this paper
• Qualitative spatial reasoning on topological relations by combining the semantic web and constraint satisfaction

  2018cites this paper
• Qualitative Representation and Reasoning over Direction Relations across Different Frames of Reference

  2018cites this paper
• An Incremental SAT-Based Approach to Reason Efficiently on Qualitative Constraint Networks

  2018cites this paper
• Why are CSPs Based on Partition Schemes Computationally Hard?

  2018cites this paper
• Infinite RCC 8 Networks

  2017influential citation
• A Model-Theoretic View on Qualitative Constraint Reasoning

  2017influential citation
• Finitariness of Elementary Unification in Boolean Region Connection Calculus

  2017cites this paper
• The Philosophy of Geo-Ontologies

  2017cites this paper
• Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning

  2017influential citation
• Algorithmic Contributions to Qualitative Constraint-based Spatial and Temporal Reasoning. (Contributions Algorithmiques au Raisonnement Spatial et Temporel basé sur des Contraintes Qualitatives)

  2017influential citation
• A qualitative inference method for prediction of geographic process using spatial and temporal relations

  2017cites this paper
• Qualitative Spatial Representations

  2017cites this paper
• Towards Applying the OPRA Theory to Shape Similarity

  2017cites this paper
• Relations Between Spatial Calculi About Directions and Orientations (Extended Abstract)

  2017cites this paper
• Un modèle pour raisonner sur les relations entre régions indéterminées

  2017influential citation
• Qualitative spatial and temporal representation and reasoning : efficiency in time and space

  2017influential citation
• Querying incomplete information in RDF with SPARQL

  2016cites this paper
• Semantic-driven modeling and reasoning for enhanced safety of cyber-physical systems

  2016influential citation
• Polynomial Realization of ORD-Horn Constraints

  2016influential citation
• Defining Relations: A General Incremental Approach with Spatial Temporal Case Studies

  2016cites this paper
• An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks

  2016cites this paper
• Efficiently Characterizing Non-Redundant Constraints in Large Real World Qualitative Spatial Networks

  2015influential citation
• On the use and effect of graph decomposition in qualitative spatial and temporal reasoning

  2015cites this paper
• From Snapshots to Processes Description – Spatiotemporal Modelling using RDF Datasets and Formal Ontologies

  2015cites this paper
• Relations Between Spatial Calculi About Directions and Orientations

  2015influential citation
• Drawing Interactive Euler Diagrams from Region Connection Calculus Specifications

  2015influential citation
• Shape Similarity Based on the Qualitative Spatial Reasoning Calculus eOPRAm

  2015cites this paper
• A Simple Decomposition Scheme for Large Real World Qualitative Constraint Networks

  2015cites this paper
• Spatial reasoning with RCC8 and connectedness constraints in Euclidean spaces

  2014cites this paper
• On Redundant Topological Constraints (Extended Abstract)

  2014cites this paper
• Crossing the Boundary - Two Benchmarks for Qualitative Spatial Reasoning Bridging Relative Directions and Mereotopology

  2014cites this paper
• Spatial Reasoning with Place Information on the Semantic Web

  2014cites this paper
• A Path-Consistency based Algorithm for Anomaly Detection of Spatial Constraints in GeoXACML Policies

  2014cites this paper
• Reasoning about Topological and Cardinal Direction Relations Between 2-Dimensional Spatial Objects

  2014cites this paper
• A Qualitative Spatio-Temporal Framework Based on Point Algebra

  2014cites this paper
• On redundant topological constraints

  2014influential citation
• Extraction, analyse et utilisation de relations spatiales entre objets d'intérêt pour une analyse d'images de télédétection guidée par des connaissances du domaine

  2014cites this paper
• Realizing RCC8 networks using convex regions

  2014influential citation
• ІНЖЕНЕРІЯ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ No4(8) 2011

  2014cites this paper
• On the identification and establishment of topological spatial relations by autonomous systems

  2014cites this paper
• A Concise Horn Theory for RCC8

  2014cites this paper
• Modelowanie dynamicznych zjawisk w planowaniu przestrzennym z wykorzystaniem ontologii formalnych

  2014cites this paper
• Drawing Euler Diagrams from Region Connection Calculus Specifications with Local Search

  2014cites this paper
• Wnioskowanie czasowo-przestrzenne w systemie Question Answering

  2014cites this paper
• Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning

  2014cites this paper
• Computational pragmatics : time, space and discourse. (Phénomènes contextuels en TAL: temps, espace et discours)

  2014cites this paper
• CHOROS 2: Improving the Performance of Qualitative Spatial Reasoning in OWL

  2014cites this paper
• Qualitative shape representation based on the qualitative relative direction and distance calculus eOPRAm

  2014cites this paper
• Decomposition and tractability in qualitative spatial and temporal reasoning

  2013cites this paper
• Constraint Satisfaction : Algorithms and Complexity Course Notes

  2013cites this paper
• A model for the 3Drelative orientation based on TPCC，Journal of Information & Computational Science

  2013cites this paper
• Geospatial optimization problems

  2013cites this paper
• A Vocabulary of Topological and Containment Relations for a Practical Biological Ontology

  2013cites this paper
• A survey of qualitative spatial representations

  2013cites this paper
• Qualitative constraint satisfaction problems: An extended framework with landmarks

  2013cites this paper
• Ontology Driven Analysis of Spatio-temporal Phenomena, Aimed At Spatial Planning And Environmental Forecasting

  2013cites this paper
• Qualitative Spatio-Temporal Representation and Reasoning : Trends and Future Directions

  2013cites this paper
• Inferring intentions through state representations in cooperative human-robot environments

  2013cites this paper
• On Finding Approximate Solutions of Qualitative Constraint Networks

  2013cites this paper
• An ontological analysis of vague motion verbs, with an application to event recognition

  2013cites this paper
• An implementation of a temporal and spatial extension of RDF and SPARQL on top of MonetDB - phase I

  2012cites this paper
• Knowledge representation and reasoning for qualitative spatial change

  2012influential citation
• Reasoning about visibility

  2012influential citation
• A semi-dynamical approach for solving qualitative spatial constraint satisfaction problems

  2012influential citation
• Direction Relations Reasoning Based on Constraint Satisfaction Problems

  2012cites this paper
• Extending the Stream Reasoning in DyKnow with Spatial Reasoning in RCC-8

  2012cites this paper
• Spatial reasoning with augmented points: Extending cardinal directions with local distances

  2012influential citation