Mining Diamonds in Labelled Transition Systems
摘要
Labelled transition systems can be a great way to visualise the complex behaviour of parallel and communicating systems. However, if, during a particular time frame, no synchronisation or communication between processes occurs, then multiple parallel sequences of actions are able to interleave arbitrarily, and the resulting graph quickly becomes too complex for the human eye to understand easily. With that in mind, we propose an exact formalisation of these arbitrary interleavings, and an algorithm to find all said interleavings in any arbitrary finite LTS, to reduce the visual complexity of labelled transition systems.