On tightness of constraints

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The tightness of a constraint refers to how restricted the constraint is. The existing work shows that there exists a relationship between tightness and global consistency of a constraint network. In this paper, we conduct a comprehensive study on this relationship. Under the concept of k-consistency (k is a number), we strengthen the existing results by establishing that only some of the tightest, not all, binary constraints are used to predict a number k such that strong k-consistency ensures global consistency of an arbitrary constraint network which may include non-binary constraints. More importantly, we have identified a lower bound of the number of the tightest constraints we have to consider in predicting the number k. To make better use of the tightness of constraints, we propose a new type of consistency: dually adaptive consistency. Under this concept, only the tightest directionally relevant constraint on each variable (and thus in total n - 1 such constraints where n is the number of variables) will be used to predict the level of "consistency" ensuring global consistency of a network.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsMark Wallace
PublisherSpringer-Verlag
Pages777-781
Number of pages5
ISBN (Print)3540232419, 9783540232414
DOIs
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3258
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint Dive into the research topics of 'On tightness of constraints'. Together they form a unique fingerprint.

  • Cite this

    Zhang, Y. (2004). On tightness of constraints. In M. Wallace (Ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 777-781). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3258). Springer-Verlag. https://doi.org/10.1007/978-3-540-30201-8_65