C. Beeri, R. Fagin, D. Maier, and M. Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM, vol.30, issue.3, pp.479-513, 1983.
DOI : 10.1145/2402.322389

N. Beldiceanu, M. Carlsson, R. Debruyne, and T. Petit, Reformulation of Global Constraints Based on Constraints Checkers, Constraints, vol.11, issue.2, pp.339-362, 2005.
DOI : 10.1007/s10601-005-2809-x

C. Bessiere, Constraint Propagation, Handbook of Constraint Programming, chapter 3, 2006.
DOI : 10.1016/S1574-6526(06)80007-6
URL : https://hal.archives-ouvertes.fr/lirmm-00117128

C. Bessiere, E. Hebrard, B. Hnich, Z. Kiziltan, and T. Walsh, Slide : A useful special case of the cardpath constraint, Proc. of ECAI'08, pp.475-479, 2008.
URL : https://hal.archives-ouvertes.fr/lirmm-00329876

C. Bessiere and P. Van-hentenryck, To Be or Not to Be ... a Global Constraint, Proc. CP'03, pp.789-794, 2003.
DOI : 10.1007/978-3-540-45193-8_54
URL : https://hal.archives-ouvertes.fr/lirmm-00269643

E. Boros and P. Hammer, Pseudo-Boolean optimization, Discrete Applied Mathematics, vol.123, issue.1-3, pp.155-225, 2002.
DOI : 10.1016/S0166-218X(01)00341-9
URL : https://hal.archives-ouvertes.fr/hal-01150533

M. Cooper, S. De-givry, M. Sanchez, T. Schiex, M. Zytnicki et al., Soft arc consistency revisited, Artificial Intelligence, vol.174, issue.7-8, pp.449-478, 2010.
DOI : 10.1016/j.artint.2010.02.001

M. C. Cooper, Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and Systems, pp.311-342, 2003.

M. C. Cooper and T. Schiex, Arc consistency for soft constraints, Artificial Intelligence, vol.154, issue.1-2, pp.199-227, 2004.
DOI : 10.1016/j.artint.2003.09.002

G. Cornuéjols and M. Dawande, A class of hard small 0-1 programs, Integer Programming and Combinatorial Optimization, 6th International IPCO Conference Proceedings, pp.284-293, 1998.

K. Culik, I. , and J. Kari, Image compression using Weighted Finite Automata, MFCS, pp.392-402, 1993.
DOI : 10.1007/3-540-57182-5_31

R. Dechter, Mini-buckets, Proc. of the 16 th IJCAI, pp.1297-1303, 1997.
DOI : 10.1145/636865.636866

G. Katsirelos, N. Narodytska, and T. Walsh, The weighted Grammar constraint, Annals of Operations Research, vol.39, issue.2, pp.179-207, 2011.
DOI : 10.1007/s10479-010-0697-y

D. Koller and N. Friedman, Probabilistic graphical models, 2009.

J. Larrosa, S. De-givry, F. Heras, and M. Zytnicki, Existential arc consistency : getting closer to full arc consistency in weighted CSPs, Proc. of the 19 th IJCAI, pp.84-89, 2005.

J. Larrosa and T. Schiex, In the quest of the best form of local consistency for weighted CSP

J. Larrosa and T. Schiex, Solving weighted CSP by maintaining arc consistency, Artificial Intelligence, vol.159, issue.1-2, pp.1-26, 2004.
DOI : 10.1016/j.artint.2004.05.004

J. Lee and K. Leung, Consistency techniques for flow-based projection-safe global cost functions in weighted constraint satisfaction, Journal of Artificial Intelligence Research, vol.43, pp.257-292, 2012.

J. Lee and K. L. Leung, A stronger consistency for soft global constraints in weighted constraint satisfaction, Proc. of AAAI'10, 2010.

J. Ho-man, K. L. Lee, and . Leung, Towards efficient consistency enforcement for global constraints in weighted constraint satisfaction, Proc of the 21 th IJCAI, pp.559-565, 2009.

C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, vol.43, issue.3, pp.425-440, 1991.
DOI : 10.1016/0022-0000(91)90023-X
URL : http://doi.org/10.1016/0022-0000(91)90023-x

G. Pesant, A Regular Language Membership Constraint for Finite Sequences of Variables, Lecture Notes in Computer Science, vol.3258, pp.482-495, 2004.
DOI : 10.1007/978-3-540-30201-8_36

T. Petit, J. Régin, and C. Bessiere, Specific filtering algorithms for overconstrained problems, CP, pp.451-463, 2001.

M. Sánchez, T. Simon-de-givry, and . Schiex, Mendelian Error Detection in Complex Pedigrees Using Weighted Constraint Satisfaction Techniques, Constraints, vol.57, issue.4, pp.130-154, 2008.
DOI : 10.1007/s10601-007-9029-5

T. Schiex, H. Fargier, and G. Verfaillie, Valued constraint satisfaction problems : hard and easy problems, Proc. of the 14 th IJCAI, pp.631-637, 1995.

M. A. Trick, A dynamic programming approach for consistency and propagation for knapsack constraints, Annals of Operations Research, vol.118, issue.1/4, pp.73-84, 2003.
DOI : 10.1023/A:1021801522545

W. Jan-van-hoeve, G. Pesant, and L. Rousseau, On global warming: Flow-based soft global constraints, Journal of Heuristics, vol.1, issue.4, pp.347-373, 2006.
DOI : 10.1007/s10732-006-6550-4

M. Zytnicki, C. Gaspin, S. De-givry, and T. Schiex, Bounds arc consistency for weighted CSPs, Journal of Artificial Intelligence Research, vol.35, issue.2, pp.593-621, 2009.

M. Zytnicki, C. Gaspin, and T. Schiex, A new local consistency for weighted CSP dedicated to long domains, Proceedings of the 2006 ACM symposium on Applied computing , SAC '06, pp.394-398, 2006.
DOI : 10.1145/1141277.1141367