Petri net systems modelling distributed systems often provide a component structure, comprising individual components that collaborate occasionally. The modular state space [1, 6] method for Petri net systems embraces this structure in the exploration of the state space with the aim of completely representing the behavior of a Petri net system while minimizing time and memory resources. The efficient method currently considers bounded Petri net systems with a finite state space. For unbounded Petri net systems with an infinite state space, the coverability graph [7] is a finite representation of the state space that abstracts the infinite behavior on diverging places. As it is related with the state space by a simulation relation [2], the coverability graph is a valid base for verification for unbounded Petri net systems. This work presents a modular construction algorithm for unbounded Petri net systems, that generates a finite, modular representation of its state space, the covering modular state space. The covering modular state space simulates the state space as well and allows efficient modular verification for unbounded Petri net systems. Furthermore, this work examines how verification of standard Petri net system properties such as reachability, existence of deadlocks and liveness, can be performed in the covering modular state space.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Coverability Abstraction for the Modular State Space

  • Sophie Wallner,
  • Julian Gaede,
  • Lukas Zech,
  • Karsten Wolf

摘要

Petri net systems modelling distributed systems often provide a component structure, comprising individual components that collaborate occasionally. The modular state space [1, 6] method for Petri net systems embraces this structure in the exploration of the state space with the aim of completely representing the behavior of a Petri net system while minimizing time and memory resources. The efficient method currently considers bounded Petri net systems with a finite state space. For unbounded Petri net systems with an infinite state space, the coverability graph [7] is a finite representation of the state space that abstracts the infinite behavior on diverging places. As it is related with the state space by a simulation relation [2], the coverability graph is a valid base for verification for unbounded Petri net systems. This work presents a modular construction algorithm for unbounded Petri net systems, that generates a finite, modular representation of its state space, the covering modular state space. The covering modular state space simulates the state space as well and allows efficient modular verification for unbounded Petri net systems. Furthermore, this work examines how verification of standard Petri net system properties such as reachability, existence of deadlocks and liveness, can be performed in the covering modular state space.