Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/78953
Title: Designing and Optimizing Representations for Non-Binary Constraints
Authors: XIA WEI
Keywords: generalized arc consistency, compression, table constraint, regular constraint, CSP transformation, higher-order consistencies
Issue Date: 28-May-2014
Citation: XIA WEI (2014-05-28). Designing and Optimizing Representations for Non-Binary Constraints. ScholarBank@NUS Repository.
Abstract: Global constraint plays a central role in constraint programming due to its strong modelling and efficient propagation. In this thesis, we focus on the design, optimization and analysis of propagation algorithms for non-binary constraints using different representations. We fist propose a GAC algorithm, nfac, for the regular constraint defined on NFA. Nfac can also propagate the constraint represented by DFA or MDD. We investigate the space-time tradeoffs of different representations. We also extend nfac to grammar constraint. Then we revise the state-of-the-art GAC algorithms, STR2 and STR3, for table constraint, so that they can work on compressed representation, c-tuples. Higher-order consistencies are stronger than GAC and have stronger search space reduction, but are more costly to enforce. Thus, only a few practical higher-order consistency algorithms have been designed. We propose to transform one CSP into another, so that higher-order consistencies can be enforced through GAC on the transformed one.
URI: http://scholarbank.nus.edu.sg/handle/10635/78953
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
XiaW.pdf1.24 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

115
checked on Nov 9, 2018

Download(s)

172
checked on Nov 9, 2018

Google ScholarTM

Check


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