×

zbMATH — the first resource for mathematics

The essence of constraint propagation. (English) Zbl 0930.68164
Summary: We show that several constraint propagation algorithms (also called (local) consistency, consistency enforcing, Waltz, filtering or narrowing algorithms) are instances of algorithms that deal with chaotic iteration. To this end we propose a simple abstract framework that allows us to classify and compare these algorithms and to establish in a uniform way their basic properties.

MSC:
68W05 Nonnumerical algorithms
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apt, K.R., A proof theoretic view of constraint programming, Fund. inform., 33, 3, 263-293, (1998), Available via
[2] Barwise, J.; Moss, L., Vicious circles: on the mathematics of circular phenomena, () · Zbl 0865.03002
[3] Baudet, G.M., Asynchronous iterative methods for multiprocessors, J. ACM, 25, 2, 226-244, (1978) · Zbl 0372.68015
[4] Benhamou, F., Heterogeneous constraint solving, (), 62-76 · Zbl 1355.68030
[5] Benhamou, F.; McAllester, D.A.; Van Hentenryck, P., CLP(intervals) revisited, (), 124-138
[6] Benhamou, F.; Older, W., Applying interval arithmetic to real, integer and Boolean constraints, J. logic programm, 32, 1, 1-24, (1997) · Zbl 0882.68032
[7] Caseau, Y., Abstract interpretation of constraints on order-sorted domains, (), 435-452
[8] Chazan, D.; Miranker, W., Chaotic relaxation, Linear algebra appl., 2, 199-222, (1969) · Zbl 0225.65043
[9] Cook, W.J.; Cunningham, W.H.; Pulleyblank, W.R.; Schrijver, A., Combinatorial optimization, (1998), Wiley New York · Zbl 0909.90227
[10] Cousot, P., Méthodes itératives de construction et d’approximation de points fixes d’opérateurs monotones sur un treillis, analyse sémantique des programmes, ()
[11] Cousot, P.; Cousot, R., Automatic synthesis of optimal invariant assertions: mathematical foundations, (), 1-12, (8) · Zbl 0788.68094
[12] Davis, E., Constraint propagation with interval labels, Artif. intell., 32, 3, 281-331, (1987) · Zbl 0642.68176
[13] Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artif. intell., 34, 1, 1-38, (1988) · Zbl 0643.68156
[14] Dechter, R.; van Beek, P., Local and global relational consistency, Theoret. comput. sci., 173, 1, 283-308, (1997) · Zbl 0902.68043
[15] Deville, Y.; Barette, O.; Van Hentenryck, P., Constraint satisfaction over connected row convex constraints, () · Zbl 0916.68061
[16] Fages, F.; Fowler, J.; Sola, T., Experiments in reactive constraint logic programming, J. logic programm., 37, 1-3, 185-212, (1998) · Zbl 0920.68031
[17] Güsgen, H.-W.; Hertzberg, J., Some fundamental properties of local constraint propagation, Artif. intell., 36, 2, 237-247, (1988) · Zbl 0648.68106
[18] Lhomme, O., Consistency techniques for numeric csps, (), 232-238
[19] Mackworth, A., Consistency in networks of relations, Artif. intell., 8, 1, 99-118, (1977) · Zbl 0341.68061
[20] Mohr, R.; Henderson, T.C., Arc-consistency and path-consistency revisited, Artif. intell., 28, 225-233, (1986)
[21] Mohr, R.; Masini, G., Good old discrete relaxation, (), 651-656
[22] Monfroy, E.; Réty, J.-H., Chaotic iteration for distributed constraint propagation, (), 19-24
[23] Montanari, U.; Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, (), 7, 2, 95-132, (1974), Also · Zbl 0284.68074
[24] Montanari, U.; Rossi, F., Constraint relaxation may be perfect, Artif. intell., 48, 143-170, (1991) · Zbl 1117.68495
[25] Older, W.; Vellino, A., Constraint arithmetic on real intervals, (), 175-195
[26] Saraswat, V.A.; Rinard, M.; Panangaden, P., Semantic foundations of concurrent constraint programming, (), 333-352
[27] Telerman, V.; Ushakov, D., Data types in subdefinite models, (), 305-319 · Zbl 0972.68034
[28] van Emden, M.H., Value constraints in the CLP scheme, Constraints, 2, 2, 163-184, (1997) · Zbl 0888.68034
[29] Van Hentenryck, P.; Deville, Y.; Teng, Choh-Man, A generic arc-consistency algorithm and its specializations, Artif. intell., 57, 2-3, 291-321, (1992) · Zbl 0763.68059
[30] Waltz, D.L., Generating semantic descriptions from drawings of scenes with shadows, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.