On Neighbourhood Singleton-style Consistencies for Qualitative Spatial and Temporal Reasoning - Université d'Artois Accéder directement au contenu
Article Dans Une Revue Information and Computation Année : 2020

On Neighbourhood Singleton-style Consistencies for Qualitative Spatial and Temporal Reasoning

Michael Sioutis
Tomi Janhunen
  • Fonction : Auteur

Résumé

Given a qualitative constraint network (QCN), a singleton-style consistency focuses on each base relation (atom) of a constraint separately, rather than the entire constraint altogether. This local consistency is essential for tackling fundamental reasoning problems associated with QCNs, such as minimal labeling, but can suffer from redundant constraint checks, especially when checks occur far from where the pruning usually takes place. In this paper, we propose singleton-style consistencies that are applied just on the neighbourhood of a singleton-checked constraint instead of the whole network. We make a theoretical comparison with existing consistencies and consequently prove some properties of the new ones. Further, we propose algorithms to enforce our consistencies, as well as parsimonious variants thereof, that are more efficient in practice than the state of the art. An experimental evaluation with random and structured QCNs of Allen’s Interval Algebra in the phase transition region demonstrates the potential of our approach.
Fichier principal
Vignette du fichier
main.pdf (539.81 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03301105 , version 1 (29-11-2021)

Identifiants

  • HAL Id : hal-03301105 , version 1

Citer

Michael Sioutis, Anastasia Paparrizou, Tomi Janhunen. On Neighbourhood Singleton-style Consistencies for Qualitative Spatial and Temporal Reasoning. Information and Computation, 2020. ⟨hal-03301105⟩
33 Consultations
82 Téléchargements

Partager

Gmail Facebook X LinkedIn More