Petri Nets

An alternative to automata for untimed models of DES is provided by Petri nets. These models were first developed by C. A. Petri in the early 1960’s. As we will see, Petri nets are related to automata in the sense that they also explicitly represent the transition function of DES. Like an automaton, a Petri net is a device that manipulates events according to certain rules. One of its features is that it includes explicit conditions under which an event can be enabled; this allows the representation of very general DES whose operation depends on potentially complex control schemes. This representation is conveniently described graphically, at least for small systems, resulting in Petri net graphs; Petri net graphs are intuitive and capture a lot of structural information about the system. We will see that an automaton can always be represented as a Petri net; on the other hand, not all Petri nets can be represented as finite-state automata. Consequently, Petri nets can represent a larger class of languages than the class of regular languages, R. Another motivation for considering Petri net models of DES is the body of analysis techniques that have been developed for studying them. Such techniques cover not only untimed Petri net models but timed Petri net models as well; in this regard, we will see in the next chapter that there is a well-developed theory, called the “max-plus algebra,” for a certain class of timed Petri nets (cf. Section 5.4). Finally, we mention that Grafcet, the widely-used programming language for programmable logic controllers (or PLCs) used in industrial automation, is inspired by Petri nets.