Computing the reveals relation in occurrence nets.

Abstract: Petri net unfoldings are a useful tool to tackle state-space explosion in verification and related tasks. Moreover, their structure allows to access directly the relations of causal precedence, concurrency, and conflict between events. Here, we explore the data structure further, to determine the following relation: event is said to reveal event iff the occurrence of implies that inevitably occurs, too, be it before, after, or concurrently with . Knowledge of reveals facilitates in particular the analysis of partially observable systems, in the context of diagnosis, testing, or verification; it can also be used to generate more concise representations of behaviors via abstractions. The reveals relation was previously introduced in the context of fault diagnosis, where it was shown that the reveals relation was decidable: for a given pair in the unfolding of a safe Petri net , a finite prefix of is sufficient to decide whether or not reveals . In this paper, we first considerably improve the bound on and show that the new bounds are optimal for the method presented. We then show that there exists an efficient algorithm for computing the relation on a given prefix. We have implemented the algorithm and report on experiments. [Copyright &y& Elsevier]