B-W Analysis: a Backward Reachability Analysis for Diagnostic Problem Solving suitable to Parallel Implementation

Backward reachability on Petri net models has been proposed since the beginning of the development of net theory without giving it a suitable motivation. For this reason, reachability analysis has been successively developed essentially by taking into account forward reachability. In this paper backward reachability analysis is motivated by showing its suitability to diagnostic problem solving. A particular technique for backward reachability analysis (B-W analysis) is defined for a net model called Behavioral Petri Net (BPN), intended to model the behavior of a system to be diagnosed. Such a technique is based on the use of two different types of tokens (normal and inhibitor tokens) whose aim is to represent the truth or falsity of the condition associated to a marked place. A distributed approach for parallel B-W analysis is also proposed. Such an approach is based on a set of processes derived from the structure of a BPN by means of a formal partitioning technique; this allows us to address the problem of mitigating the high inefficiency diagnostic algorithms usually have.