In: Rozenberg, G.: Lecture Notes in Computer Science, Vol. 524; Advances in Petri Nets 1991, pages 205-226. Berlin, Germany: Springer-Verlag, 1991.
Abstract: One of the ways to avoid the combinatorial explosion of the state space is by using optimal simulation. The optimal simulation usually involves only a very small subset of the possible behaviours generated by the system, yet provides sufficient information to reason about a number of interesting system's properties such as deadlock-freeness and liveness. In this paper the authors present also other properties of that kind, and show how the optimal simulation can be used to generate a reachability graph which is usually much smaller than the standard one. In spite of this both graphs convey essentially the same amount of information.
Keywords: system's histories; optimal simulation; reachability graph; traces; partial order semantics; step sequences; liveness; deadlock-freeness; combinatorial explosion (of the) state space; simulation.