Người báo cáo: Nguyễn Hoàng Thạch
Thời gian: 14h00, Thứ 5, ngày 28 tháng 1, năm 2016
Địa điểm: Phòng 201, Nhà A5, Viện Toán học, 18 Hoàng Quốc Việt Cầu Giấy Hà Nội
Tóm tắt: 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. |
