2026-07-22T13:39:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7923 2024-03-06T10:41:36Z ddc:004 open_access

Collective Singleton-Based Consistency for Qualitative Constraint Networks Sioutis, Michael Paparrizou, Anastasia Condotta, Jean-François Qualitative constraint network qualitative spatial and temporal reasoning partial singleton path-consistency local consistency minimal labeling pr Partial singleton closure under weak composition, or partial singleton (weak) path-consistency for short, is essential for approximating satisfiability of qualitative constraints networks. Briefly put, partial singleton path-consistency ensures that each base relation of each of the constraints of a qualitative constraint network can define a singleton relation in the corresponding partial closure of that network under weak composition, or in its corresponding partially (weak) path-consistent subnetwork for short. In particular, partial singleton path-consistency has been shown to play a crucial role in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network. In this paper, we propose a stronger local consistency that couples partial singleton path-consistency with the idea of collectively deleting certain unfeasible base relations by exploiting singleton checks. We then propose an efficient algorithm for enforcing this consistency that, given a qualitative constraint network, performs fewer constraint checks than the respective algorithm for enforcing partial singleton path-consistency in that network. We formally prove certain properties of our new local consistency, and motivate its usefulness through demonstrative examples and a preliminary experimental evaluation with qualitative constraint networks of Interval Algebra. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Sioutis and Anastasia Paparrizou and Jean-François Condotta 2017 Is Part Of LIPIcs, Volume 90, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2017.19 urn:nbn:de:0030-drops-79237 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2017.19 eng https://creativecommons.org/licenses/by/3.0/legalcode