×

zbMATH — the first resource for mathematics

From local to global consistency. (English) Zbl 0762.68053
Summary: In reasoning tasks involving the maintenance of consistent databases (so- called QQconstraint networks/\(Q\)/\(Q\)), it is customary to enforce local consistency conditions in order to simplify the subsequent construction of a globally coherent model of the data.
We present a relationship between the sizes of the variables’ domains, the constraints’ arity and the level of local consistency sufficient to ensure global consistency. Based on these parameters a new tractability classification of constraint networks is presented. We also show, based on this relationship, that any relation on bi-valued variables which is not representable by a network of binary constraints cannot be represented by networks with any number of hidden variables.

MSC:
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68T30 Knowledge representation
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, J.F., Maintaining knowledge about temporal intervals, Commun. ACM, 26, 11, 832-843, (1983) · Zbl 0519.68079
[2] Clowes, M.B., On seeing things, Artif. intell., 2, 79-116, (1971)
[3] Cooper, M.C., An optimal k-consistency algorithm, Artif. intell., 41, 1, 89-95, (1990) · Zbl 0678.68058
[4] Dechter, R., Studies in the use and generation of heuristics, ()
[5] Dechter, R., On the expressiveness of networks with hidden variables, ()
[6] Dechter, R.; Meiri, I., Experimental evaluation of preprocessing techniques in constraint satisfaction, () · Zbl 0707.68081
[7] Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artif. intell., 34, 1, 1-38, (1987) · Zbl 0643.68156
[8] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. intell., 38, 353-366, (1989) · Zbl 0665.68084
[9] Doyle, J., A truth maintenance system, Artif. intell., 12, 231-272, (1979)
[10] Freuder, E.C., Synthesizing constraint expression, Commun. ACM, 21, 11, 958-965, (1978) · Zbl 0386.68065
[11] Freuder, E.C., On the knowledge required to label a picture graph, Artif. intell., 15, 1, 1-17, (1980)
[12] Freuder, E.C., A sufficient condition for backtrack-free search, J. ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063
[13] Garey, M.R.; Johnson, D.S., ()
[14] Herzberger, H.G., Pierce’s remarkable theorem, ()
[15] Huffman, D.A., Impossible objects as nonsense sentences, (), 195-234
[16] S. Kasif, Private communication (October 1990).
[17] Kirousis, L.M.; Papadimitriou, C.H., The complexity of recognizing polyhedral scenes, (), 175-185
[18] Mackworth, A.K., Consistency in networks of relations, Artif. intell., 8, 1, 99-118, (1977) · Zbl 0341.68061
[19] Mackworth, A.K.; Freuder, E.C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artif. intell., 25, 1, 65-74, (1985)
[20] McAllester, D.A., An outlook on truth-maintenance, ()
[21] McAllester, D.A., Truth maintenance, (), 1109-1115
[22] Meiri, I.; Pearl, J., Faster constraint satisfaction algorithms for temporal reasoning, ()
[23] Mohr, R.; Henderson, T.C., Arc and path consistency revisited, Artif. intell., 28, 2, 225-233, (1986)
[24] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inf. sci., 7, 95-132, (1974) · Zbl 0284.68074
[25] van Beek, P., Reasoning about qualitative temporal information, (), 728-734
[26] van Beek, P.; Cohen, R., Approximation algorithms for temporal reasoning, () · Zbl 0718.68065
[27] Vilain, M.; Kautz, H., Constraint propagation algorithms for temporal reasoning, (), 377-382
[28] Waltz, D., Understanding line 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.