文章基本信息

标题：Unbounded Product-Form Petri Nets
本地全文：下载
作者：Patricia Bouyer ; Serge Haddad ; Vincent Jug{\'e 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：85
页码：31:1-31:16
DOI：10.4230/LIPIcs.CONCUR.2017.31
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Computing steady-state distributions in infinite-state stochastic systems is in general a very difficult task. Product-form Petri nets are those Petri nets for which the steady-state distribution can be described as a natural product corresponding, up to a normalising constant, to an exponentiation of the markings. However, even though some classes of nets are known to have a product-form distribution, computing the normalising constant can be hard. The class of (closed) \Pi^3-nets has been proposed in an earlier work, for which it is shown that one can compute the steady-state distribution efficiently. However these nets are bounded. In this paper, we generalise queuing Markovian networks and closed \Pi^3-nets to obtain the class of open \Pi^3-nets, that generate infinite-state systems. We show interesting properties of these nets: (1) we prove that liveness can be decided in polynomial time, and that reachability in live \Pi^3-nets can be decided in polynomial time; (2) we show that we can decide ergodicity of such nets in polynomial time as well; (3) we provide a pseudo-polynomial time algorithm to compute the normalising constant.
关键词：Performance evaluation; infinite-state systems; Petri nets; steady-state distribution