Please use this identifier to cite or link to this item:
Title: Consistency techniques in constraint networks
Keywords: Constraint Networks, Arc Consistency, Set Intersection, Local and Global Consistency, Tree Convexity, Constraint Tightness
Issue Date: 18-Nov-2003
Citation: 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.
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



Page view(s)

checked on Apr 20, 2019


checked on Apr 20, 2019

Google ScholarTM


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