No label defined (Q4424873)

This monograph is an introduction to discrete event systems which can be represented as dynamical linear systems by using a new class of algebras. The first chapter is an introduction to Petri nets. A Petri net is a mathematical representation of discrete distributed systems. Petri nets were defined in the 1960s by Carl Adam Petri. Because of their ability to express concurrent events, they generalize automata theory. A Petri net consists of places, transitions and directed arcs. Arcs connect a place to a transition and vice versa. There are no arcs between two places, nor between two transitions. The transitions represent events and the places represent states or conditions. Not only can you model a system's architecture with a Petri net, you can also simulate execution of the system. This is done by ``marking'' the Petri net with ``tokens''. Places may contain any number of tokens. Transitions fire, that is consume tokens from input positions and produce tokens in output positions. A transition is enabled if there are tokens in every input position. In the most basic form, tokens in a Petri net are indistinguishable from each other. More complex Petri nets add token coloring, activation time and hierarchy to the network. The author shows in chapters 2 and 4 several mathematical tools that will be used along this work. More specifically, he introduces the algebra of dioids in chapter 2 and the theory of residuation in chapter 4. The remainder of the chapters of this monograph are dedicated to study timed event graphs. Event graphs constitute a special class of Petri nets in which transitions admit several incoming and outgoing arcs whereas places admit single upstream and downstream arcs. A \textit{fork} -- several outgoing arcs from a transition -- represents for example the simultaneous broadcasting of messages in several directions. A \textit{join} -- several incoming arcs -- represents the requirement of simultaneous availability of resources in order to perform a task. Considering timed event graphs and performance evaluation, a fork mathematically translates into the equality of either the dates of the corresponding event occurrences or the numbers of event occurrences up to any given time. As for joins, they involve max or min operations whether we consider dates or numbers of events. By using the algebra of dioids, it is possible to consider these systems as linear systems, and to develop a theory for them which bears much resemblance with the conventional linear system theory. Others representations of timed event graphs are described in chapter 5. Finally, in chapter 6 the author analyses the asymptotical behaviour of timed event graphs.