首页    期刊浏览 2025年07月11日 星期五
登录注册

文章基本信息

  • 标题:Collective Singleton-Based Consistency for Qualitative Constraint Networks
  • 本地全文:下载
  • 作者:Michael Sioutis ; Anastasia Paparrizou ; Jean-Fran{\c{c}}ois Condotta
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:90
  • 页码:19:1-19:17
  • DOI:10.4230/LIPIcs.TIME.2017.19
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Qualitative constraint network; qualitative spatial and temporal reasoning; partial singleton path-consistency; local consistency; minimal labeling pr
国家哲学社会科学文献中心版权所有