License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2017.19
URN: urn:nbn:de:0030-drops-79237
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7923/
Go to the corresponding LIPIcs Volume Portal

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

Collective Singleton-Based Consistency for Qualitative Constraint Networks

pdf-format:
LIPIcs-TIME-2017-19.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{sioutis_et_al:LIPIcs:2017:7923,
  author =	{Michael Sioutis and Anastasia Paparrizou and Jean-Fran{\c{c}}ois Condotta},
  title =	{{Collective Singleton-Based Consistency for Qualitative Constraint Networks}},
  booktitle =	{24th International Symposium on Temporal Representation and Reasoning (TIME 2017)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-052-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{90},
  editor =	{Sven Schewe and Thomas Schneider and Jef Wijsen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7923},
  URN =		{urn:nbn:de:0030-drops-79237},
  doi =		{10.4230/LIPIcs.TIME.2017.19},
  annote =	{Keywords: Qualitative constraint network, qualitative spatial and temporal reasoning, partial singleton path-consistency, local consistency, minimal labeling pr}
}

Keywords: Qualitative constraint network, qualitative spatial and temporal reasoning, partial singleton path-consistency, local consistency, minimal labeling pr
Collection: 24th International Symposium on Temporal Representation and Reasoning (TIME 2017)
Issue Date: 2017
Date of publication: 25.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI