Exploiting local persistency for reduced statespace generation This paper deals with two partial order techniques for Petri nets (PN in short): persistent sets and step graphs. These techniques aim to reduce the width and the depth of the marking graphs of PN, respectively, while preserving their deadlocks. To achieve more reductions while preserving the deadlocks of PN, this paper revisits the definition of persistent sets and establishes some weaker practical sufficient conditions. It also proposes a combination of persistent sets with steps as a sort of Cartesian product of persistent sets. This combination provides a means of better controlling the length and the number of steps, while still preserving deadlocks.

Relative Liveness: From Intuition to Automated Verification We define a new liveness condition for asynchronous circuits. Although finitary (finiteexecution) descriptions are not powerful enough to express general liveness properties, those liveness properties needed in practice appear to be related in a unique manner to finitary descriptions. Our liveness condition exploits this observation and is defined directly on finitary descriptions, in two forms: one on finite trace structures and the other on finite automata. We prove the equivalence of these two forms. We also introduce a safety condition and derive theorems for the modular and hierarchical verification theorems of both safety and liveness. Finally, we give an algorithm for verifying our liveness condition.