Algebraic system analysis of timed Petri nets

Summary

Abstract

We show that Continuous Timed Petri Nets (CTPN) can be modeled by generalized polynomial recurrent equations in the (min, +) semiring. We establish a correspondence between CTPN and Markov decision processes. We survey the basic system theoretical results available: behavioral (input–output) properties, algebraic representations, asymptotic regime. Particular attention is paid to the subclass of stable systems (with asymptotic linear growth).

Introduction

The fact that a subclass of Discrete Event Systems equations can be written linearly in the (min, +) or in the (max, +) semiring is now almost classical [9, 2]. The (min, +) linearity allows the presence of synchronization and saturation features but unfortunately prohibits the modeling of many interesting phenomena such as “birth” and “death” processes (multiplication of tokens) and concurrency. The purpose of this paper is to show that after some simplifications, these additional features can be represented by polynomial recurrences in the (min, +) semiring.

We introduce a fluid analogue of general Timed Petri Nets (in which the quantities of tokens are real numbers), called Continuous Timed Petri Nets (CTPN). We show that, assuming a stationary routing policy, the counter variables of a CTPN satisfy recurrence equations involving the operators min, +, ×. We interpret CTPN equations as dynamic programming equations of classical Markov Decision Problems: CTPN can be seen as the dedicated hardware executing the value iteration.

We set up a hierarchy of CTPN which mirrors the natural hierarchy of optimization problems (deterministic vs. stochastic, discounted vs. ergodic). For each level and sublevel of this hierarchy, we recall or introduce the required algebraic and analytic tools, provide input–output characterizations and give asymptotic results.