Time: 9h30, Thursday, January 21, 2016
Location: Room 201, Building A5, Institute of Mathematics, 18 Hoang Quoc Viet, Cau Giay, Hanoi
Abstract: In the first part, we give the characterisation of a class of product-form Petri nets. We introduce the class of Pi2-nets for which a product-form steady-state distribution exists for every choice of transition rates. Next, we show that intersecting this class and the class of free-choice nets yields a classical class of product-form queueing networks: the Jackson networks.
The second part consists of two effective methods to construct arbitrary Pi2-nets. One can either generate a Pi2-net from the empty net using a finite set of synthesising rules, or to directly modify an existing net.
The third part gives a characterisation of the Pi2-nets in term of complexity. We show that the reachability and liveness problems are PSPACE-complete for 1-bounded Pi2-nets and that the coverability problem is EXPSPACE-complete for general Pi2-nets.
Finally, we introduce the subclass of Pi3-nets whose normalising constant can be efficiently computed using dynamic  programming.