Donald Bren School of Information and Computer Sciences

This paper presents distributed algorithms for performing truth-maintenance and belief revision tasks on singly-connected structures. We show that on such models the JTMS tasks of belief revision and consistency maintenance are linear in the size of the knowledge-base. The ATMS task remains exponential with a reduced exponent - the branching degree of the network. The single-connected model, while restrictive, is useful for three reasons. First, efficient algorithms on single-connected models can be utilized in more general structures by employing well-known clustering techniques. Second, these algorithms can serve as approximations or as heuristics in algorithms that perform truth-maintenance on general problems. Finally, the analysis provides insights for understanding the sources of the computational difficulties associated with both JTMS and ATMS.