---
title: "Efficiently Characterizing Non-Redundant Constraints in Large Real World Qualitative Spatial Networks"
authors:
  - "Michael Sioutis"
  - "Sanjiang Li"
  - "Jean-François Condotta"
doi: ""
url: "https://ijcai.org/proceedings/2015/455"
pdf: "https://ijcai.org/proceedings/2015/0455.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "3229-3234"
track: "Special Track on Knowledge Representation and Reasoning"
keywords:
---

# Efficiently Characterizing Non-Redundant Constraints in Large Real World Qualitative Spatial Networks

Michael Sioutis, Sanjiang Li, Jean-François Condotta

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 3229-3234.

## Abstract

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G-path consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G-path consistency and path consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G-path consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.