Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/13502
Title: Consistency techniques in constraint networks
Authors: ZHANG YUANLIN
Keywords: Constraint Networks, Arc Consistency, Set Intersection, Local and Global Consistency, Tree Convexity, Constraint Tightness
Issue Date: 18-Nov-2003
Source: ZHANG YUANLIN (2003-11-18). Consistency techniques in constraint networks. ScholarBank@NUS Repository.
Abstract: Consistency techniques play an important role in studying constraint networks. We focus on two aspects of them: consistency as a pruning tool and consistency as a tool to relate local consistency and global consistency. For the first aspect, we mainly study arc consistency (AC). We find a simple and worst case optimal implementation for a well known algorithm AC-3. To enforce arc consistency on non-binary constraints is NP-hard. A class of monotonic constraints is identified and a polynomial AC algorithm is designed for them. For the second aspect, we relate consistency to set intersection. This relation allows us not only to unify several well-known results on consistency in a network but also to derive new results on consistency in a network from set intersection properties. For example we identify a tree convex network where a certain level of local consistency guarantees global consistency. It is also found that a properly m-tight constraint network can be made globally consistent after enforcing some level of local relational consistency. Another line of our work on the second aspect is the development of efficient and elegant algorithms for functional constraints and implicational constraints.
URI: http://scholarbank.nus.edu.sg/handle/10635/13502
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Consistency_Techniques_in_Constraint_Networks.pdf780.31 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

199
checked on Dec 11, 2017

Download(s)

179
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.