Title: Unbounded product-form Petri nets,
Abstract: Computing steady-state distributions in infinite-state stochastic systems is
in general a very dificult 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.