Please use this identifier to cite or link to this item:
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.
Appears in Collections:Ph.D Theses (Open)

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



Page view(s)

checked on Jun 7, 2020


checked on Jun 7, 2020

Google ScholarTM


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