Simulation of timed Petri nets by ordinary Petri nets and applications to decidability of the timed reachability problem and other related problems

摘要

The authors consider timed Petri nets, for which a timed step semantics generalizing the ordinary step semantics is presented. A codification of these, with regard to such semantics, by ordinary Petri nets is presented. This codification is presented in a gradual way, beginning with that corresponding to a more restricted and thus simpler step semantics. This semantics does not allow the overlapped firing of several instances of each transition. The authors consider a step semantics which allows such overlapped executions. In restricted cases the construction is based on an automaton which controls the system evolution. The construction for the most general semantics is rather more complicated, that is why it is presented gradually. They consider three versions of it.