Structure-Driven Algorithms for Truth Maintenance

@article{citeulike:1172115, abstract = {This paper studies truth-maintenance and belief revision tasks on singly-connected structures for the purpose of understanding how structural features could be exploited in such tasks. We present distributed algorithms and show that, in the JTMS framework, both belief revision and consistency maintenance are linear in the size of the knowledgebase on singly connected structures. However, the ATMS task is exponential in the branching degree of the network. The singly-connected model, while...}, author = {Dechter, Rina and Dechter, Avi }, citeulike-article-id = {1172115}, journal = {Artificial Intelligence}, keywords = {automated, csp, dynamic, inference, reasoning, tms}, number = {1-2}, pages = {1--2}, posted-at = {2007-03-18 20:37:21}, priority = {5}, title = {Structure-Driven Algorithms for Truth Maintenance}, url = {http://citeseer.ist.psu.edu/291396.html}, volume = {82}, year = {1996} }

TY - JOUR ID - citeulike:1172115 L3 - citeulike-article-id:1172115 TI - Structure-Driven Algorithms for Truth Maintenance JF - Artificial Intelligence VL - 82 IS - 1-2 SP - 1 EP - 2 N2 - This paper studies truth-maintenance and belief revision tasks on singly-connected structures for the purpose of understanding how structural features could be exploited in such tasks. We present distributed algorithms and show that, in the JTMS framework, both belief revision and consistency maintenance are linear in the size of the knowledgebase on singly connected structures. However, the ATMS task is exponential in the branching degree of the network. The singly-connected model, while... KW - automated KW - csp KW - dynamic KW - inference KW - reasoning KW - tms AU - Dechter, Rina AU - Dechter, Avi PY - 1996/// UR - http://citeseer.ist.psu.edu/291396.html ER -