Home
Scholarly Works
Optimal simulations, nets and reachability graphs
Conference

Optimal simulations, nets and reachability graphs

Abstract

Reasoning about the dynamic properties of a concurrent system can be made easier by avoiding the combinatorial explosion of its state space. One of the ways in which this might be achieved is by using the optimal simulation - a kind of reachability relation on the system's histories. The optimal simulation usually involves only a very small subset of the possible behaviours generated by the system, yet provides a sufficient information to reason about a number of interesting system's properties such as deadlock-freeness and liveness. In this paper we present also other properties of that kind. We then show how the optimal simulation can be used to generate a reachability graph which is usually much smaller than the standard reachability graph of the system. In spite of this both graphs essentially convey the same information about the system's behaviour.

Authors

Janicki R; Koutny M

Series

Lecture Notes in Computer Science

Volume

524

Pagination

pp. 205-226

Publisher

Springer Nature

Publication Date

January 1, 1991

DOI

10.1007/bfb0019976

Conference proceedings

Lecture Notes in Computer Science

ISSN

0302-9743

Labels

View published work (Non-McMaster Users)

Contact the Experts team