Tractable Class of a Problem of Goal Satisfaction in Mutual Exclusion Network *

In this paper we describe a class of a problem of goal satis-faction in mutual exclusion network that can be solved in polynomial time. This problem provides a common basis for reasoning about various tasks known from artificial intelli-gence. Namely, tasks arising during construction of concur-rent solutions for planning problems and Boolean formula satisfaction can be viewed as problems of goal satisfaction. We experimentally compared a solving algorithm which ex-ploits the defined tractable class with backtracking en-hanced by maintaining consistencies on random problems and on problems arising in concurrent planning. We ob-tained significant speedups in both experimental setups