KR2023Proceedings of the 20th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 2-8, 2023.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-02-7

Sponsored by
Published by

Copyright © 2023 International Joint Conferences on Artificial Intelligence Organization

A Decomposition Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning

  1. Yakoub Salhi(CRIL UMR 8188, Artois University, CNRS)
  2. Michael Sioutis(LIRMM UMR 5506, University of Montpellier, CNRS)


  1. Geometric, spatial, and temporal reasoning
  2. Qualitative reasoning, reasoning about physical systems
  3. Inconsistency- and exception tolerant reasoning, paraconsistent logics
  4. Reasoning about constraints, constraint programming


Decomposition can be a fundamental process for dealing with

inconsistency in different domains. Among other things, it

allows us to capture potential contexts, identify conflicting

factors, restore consistency, and measure inconsistency. The

aim of this paper is to explore the process of decomposition

in qualitative spatial and temporal reasoning. We first study

a problem that consists in decomposing the original

inconsistent constraint network into the fewest possible

consistent subnetworks (components) that share a given part.

After establishing several interesting theoretical properties,

such as providing bounds on the number of components in a

decomposition, as well as computational complexity results, we

propose two methods for solving this problem. The first method

is based on a SAT encoding, while the second one corresponds to

a greedy constraint-based algorithm, a variant of which involves

the use of spanning trees to reduce the number of oracle calls.

Secondly, we consider a version of the previous decomposition

problem by focusing on maximizing the similarity between the

decomposition components; the similarity in this context is

represented by the common constraints among components. We then

adapt our methods to solve this new problem. Thirdly, we propose

two inconsistency measures that are based on our decomposition

framework and show that they satisfy several desired properties.

Finally, we provide implementations of our decomposition methods

and perform an experimental evaluation.