Bouyer, Patricia ;
Haddad, Serge ;
Jugé, Vincent
Unbounded ProductForm Petri Nets
Abstract
Computing steadystate distributions in infinitestate stochastic systems is in general a very difficult task. Productform Petri nets are those Petri nets for which the steadystate 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 productform distribution, computing the normalising constant can be hard. The class of (closed) \Pi^3nets has been proposed in an earlier work, for which it is shown that one can compute the steadystate distribution efficiently. However these nets are bounded. In this paper, we generalise queuing Markovian networks and closed \Pi^3nets to obtain the class of open \Pi^3nets, that generate infinitestate 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^3nets 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 pseudopolynomial time algorithm to compute the normalising constant.
BibTeX  Entry
@InProceedings{bouyer_et_al:LIPIcs:2017:7795,
author = {Patricia Bouyer and Serge Haddad and Vincent Jug{\'e}},
title = {{Unbounded ProductForm Petri Nets}},
booktitle = {28th International Conference on Concurrency Theory (CONCUR 2017)},
pages = {31:131:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770484},
ISSN = {18688969},
year = {2017},
volume = {85},
editor = {Roland Meyer and Uwe Nestmann},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7795},
URN = {urn:nbn:de:0030drops77957},
doi = {10.4230/LIPIcs.CONCUR.2017.31},
annote = {Keywords: Performance evaluation, infinitestate systems, Petri nets, steadystate distribution}
}
2017
Keywords: 

Performance evaluation, infinitestate systems, Petri nets, steadystate distribution 
Seminar: 

28th International Conference on Concurrency Theory (CONCUR 2017)

Issue date: 

2017 
Date of publication: 

2017 