×

zbMATH — the first resource for mathematics

Tree clustering for constraint networks. (English) Zbl 0665.68084
The paper offers a systematic way of regrouping constraints into hierarchical structures capable of supporting seach without backtracking. The method involves the formation and preprocessing of an acyclic database that permits a large variety of queries and local perturbations to be processed swiftly, either by sequential backtrack-free procedures, or by distributed constraint propagation processes.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P20 Information storage and retrieval of data
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX Cite
Full Text: DOI
References:
[1] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algebraic discrete methods, 8, 2, 277-284, (1987) · Zbl 0611.05022
[2] Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, () · Zbl 0662.03030
[3] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 3, 479-513, (1983) · Zbl 0624.68087
[4] Bertelé, U.; Brioschi, F., ()
[5] Borning, A., The programming language aspects of thinglab, a constraint-oriented simulation laboratory, ACM trans. program. lang. syst., 3, 4, 353-387, (1981)
[6] Dechter, A.; Dechter, R., Removing redundancies in constraint networks, (), 105-109
[7] Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artificial intelligence, 34, 1, 1-38, (1988) · Zbl 0643.68156
[8] Dechter, R.; Pearl, J., The cycle-cutset method for improving search performance in AI applications, (), 224-230
[9] Dechter, R.; Dechter, A., Belief maintenance in dynamic constraint networks, (), 37-42
[10] Dechter, R.; Dechter, A.; Pearl, J., Optimization in constraint-networks, () · Zbl 0678.68100
[11] de Kleer, J., An assumption-based TMS, Artificial intelligence, 28, 127-162, (1986)
[12] Doyle, J., A truth maintenance system, Artificial intelligence, 12, 3, 231-272, (1979)
[13] Freuder, E.C., Synthesizing constraint expressions, Commun. ACM, 21, 11, 958-965, (1978) · Zbl 0386.68065
[14] Freuder, E.C., A sufficient condition of backtrack-free search, J. ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063
[15] Lauritzen, S.L.; Spiegelhalter, D.J., Local computations with probabilities on graphical structures and their applications to expert systems, J. R. stat. soc. B., 50, 127-224, (1988) · Zbl 0684.68106
[16] Mackworth, A.K.; Freuder, E.C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial intelligence, 25, 1, 65-74, (1985)
[17] Maier, D., ()
[18] Malvestuto, F.M., Answering queries in categorical databases, (), 87-96
[19] Mohr, R.; Henderson, T.C., Arc and path consistency revisited, Artificial intelligence, 28, 2, 225-233, (1986)
[20] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inf. sci., 7, 95-132, (1974) · Zbl 0284.68074
[21] Pearl, J., ()
[22] Seidel, R., A new method for solving constraint-satisfaction problems, (), 338-342
[23] Shafer, G.; Shenoy, P.P., Bayesian and belief-function propagation, ()
[24] Sussman, G.J.; Steele, G.L., CONSTRAINTS: A language for expressing almost-hierarchical descriptions, Artificial intelligence, 14, 1, 1-39, (1980)
[25] Tarjan, R.E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 3, 566-579, (1984) · Zbl 0545.68062
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.