In: Jensen, K.: Lecture Notes in Computer Science, Vol. 616; 13th International Conference on Application and Theory of Petri Nets 1992, Sheffield, UK, pages 348-367. Springer-Verlag, 1992.
Abstract: Structure theory is a branch of net theory devoted to investigate the relationship between the structure and the behaviour of net models. It leads to semidecision algorithms for general nets and powerful algorithms for some subclasses of ordinary nets. The aim of this contribution is to draw a general perspective of the structure theory for a class of nets with Marked-Graph-like underlying graph but allowing weights: weighted T-graphs (WTG). Weights are convenient to properly model systems with bulk services and arrivals. Properties of the WTG and the corresponding weighted T-systems (WTS) are presented at three different levels: purely structural properties (e.g. in consistent WTG conservativeness is equivalent to strong connectedness), inter-relationships between the behavioural and structural properties (e.g. structural liveness and boundedness is equivalent to consistency and strong connectedness) and liveness and reachability characterizations (e.g. deciding liveness is linear wrt. the 1-norm of the unique minimal T-semiflow of a consistent, even unbounded, WTS). The classical results for Marked Graphs can be derived as corollaries when consistency, which plays an essential role, is assumed. Nevertheless, even in live and consistent WTS, important properties of Marked Graphs do not hold (e.g. P-semiflows based characterization of reachability).
Keywords: structure theory; weighted T-graphs; marked graphs.
Back to the Petri Nets Bibliography