Collective singleton-based consistency for qualitative constraint networks: Theory and practice

Michael Sioutis, Anastasia Paparrizou, Jean-François Condotta

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)
24 Downloads (Pure)


Partial singleton weak path-consistency, or partial (Figure presented.)-consistency for short, is essential for tackling challenging fundamental reasoning problems associated with qualitative constraints networks. Briefly put, partial (Figure presented.)-consistency ensures that each base relation of each of the constraints of a qualitative constraint network can define a singleton relation in its corresponding partially weakly path-consistent, or partially ⋄-consistent for short, subnetwork. In this paper, we propose a stronger local consistency that couples (Figure presented.)-consistency with the idea of collectively deleting certain unfeasible base relations by exploiting singleton checks. We then propose an algorithm for enforcing this new consistency and a lazy variant of that algorithm for approximating the new consistency that, given a qualitative constraint network, both outperform the respective algorithm for enforcing partial (Figure presented.)-consistency in that network. With respect to the lazy algorithmic variant in particular, we show that it runs up to 5 times faster than our original exhaustive algorithm whilst exhibiting very similar pruning capability. We formally prove certain properties of our new local consistency and our algorithms, and motivate their usefulness through demonstrative examples and a thorough experimental evaluation with random qualitative constraint networks of the Interval Algebra and the Region Connection Calculus from the phase transition region of two different generation models. Finally, we provide evidence of the crucial role of the new consistency in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network.

Original languageEnglish
Pages (from-to)17-41
JournalTheoretical Computer Science
Early online date2019
Publication statusPublished - 1 Jan 2019
MoE publication typeA1 Journal article-refereed


  • Qualitative constraint network
  • Singleton style consistency
  • Spatial and temporal reasoning

Fingerprint Dive into the research topics of 'Collective singleton-based consistency for qualitative constraint networks: Theory and practice'. Together they form a unique fingerprint.

Cite this