Please use this identifier to cite or link to this item: https://doi.org/10.1017/S1471068410000591
Title: Solving functional constraints by variable substitution
Authors: Zhang, Y.
Yap, R.H.C. 
Keywords: Arc consistency
Constraint logic programming
Constraint satisfaction problem
Functional constraints
Variable substitution
Issue Date: 2011
Source: Zhang, Y., Yap, R.H.C. (2011). Solving functional constraints by variable substitution. Theory and Practice of Logic Programming 11 (2-3) : 297-322. ScholarBank@NUS Repository. https://doi.org/10.1017/S1471068410000591
Abstract: Functional constraints and bi-functional constraints are an important constraint class in Constraint Programming (CP) systems, in particular for Constraint Logic Programming (CLP) systems. CP systems with finite domain constraints usually employ Constraint Satisfaction Problem(s)-based solvers which use local consistency, for example, arc consistency. We introduce a new approach which is based instead on variable substitution. We obtain efficient algorithms for reducing systems involving functional and bi-functional constraints together with other nonfunctional constraints. It also solves globally any CSP where there exists a variable such that any other variable is reachable from it through a sequence of functional constraints. Our experiments on random problems show that variable elimination can significantly improve the efficiency of solving problems with functional constraints. © 2011 Cambridge University Press.
Source Title: Theory and Practice of Logic Programming
URI: http://scholarbank.nus.edu.sg/handle/10635/41627
ISSN: 14710684
DOI: 10.1017/S1471068410000591
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

40
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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