Extending the Symmetry Approach in (S)WN Models

摘要

The most useful qualitative/quantitative analysis techniques for Discrete-Event Dynamic Systems are still state-space based. It is well known that similar techniques suffer from the possible state space combinatorial explosion. An approach to face the problem is the exploitation of behavioral symmetries of systems for building quotient (i.e. reduced) state-transition graphs. Behavioral symmetries can be naturally described using a high-level Petri Net formalism, Well-Formed Coloured Nets (WN). WNs exploit symmetries for the automatic generation of a quotient graph, the Symbolic Reachability Graph (SRG). The SRG provides a compact representation of the ordinary state-transition graph of the modeled system. Performance analysis is possible with the SWN formalism (a stochastic extension of WNs), which allows to automatically build a lumped Continuous Time Markov Chain from the SRG. The SRG technique reveals very effective when applied to systems with a high degree of symmetry, but it looses most of its efficacy when considering partially symmetrical systems, namely systems mixing a (prevalent) symmetric behavior with some asymmetry. The intuitive explanation is that in WNs (a)symmetries are specified at syntax level as part of the model color (i.e. data) structure, on which the SRG definition relies. A first attempt of adding flexibility to the static symmetry approach (typical of the SRG), based on the very intuitive idea of taking into account asymmetries only when they actually take place, has lead to the so-called Extended Symbolic Reachability Graph (ESRG). The ESRG gives a representation of the system behavior significantly more compact than the SRG in case of "nearly symmetrical" systems (a restricted class of partially symmetrical systems). The main ESRG limit lies in its reduced capability of capturing more general kinds of symmetries. In the paper the (E)SRG technique is surveyed and is extended to caught local symmetries, extremely frequent in real systems. A new high-level reachability graph is introduced, which reveals more compact than the corresponding (E)SRG for SWN models exhibiting a diffuse asymmetric behavior. The extension retains the basic (E)SRG properties.