A (max,+) algebra for nonstationary and nondeterministic periodic discrete event systems

Modern technology deals with complex problems which are often described in terms of discrete-valued variables. Furthermore, the values of these variables may be subject to important discontinuities. These systems, called discrete event systems (DES), are described as collections of events (such as the arrival of a message or the completion of a task). These events are characterized by their occurrences in time. In fact, occurrences mark changes in the state of the system.; There has been an extensive body of work that analyzes a class of DES represented by timed event graphs. One of the most promising approaches is based on a particular algebraic structure that causes the equations describing a system to be linear. This algebra, called the (max,+) algebra helps characterize DES by computing the occurrence times of all the events comprising the system. This analytic approach has been augmented to include the ability of synthesizing controllers for DES. A discrete event systems can be controlled by delaying some of its events (obviously, the ones that are controllable) to force the system to match a specific temporal behavior.; The goal of this research is to extend this framework based on the (max,+) algebra so that it can apply to a larger class of systems. Therefore, this work defines a (max,+) algebra of periodic signals that can compute and synthesize controllers for the temporal behavior of DES that have non-stationary delays (i.e., delays that can vary over time) and that may include some non-deterministic features.; This dissertation increases the application domain of the (max,+) algebra to include timed discrete event systems in which delays can vary over time as long as they ultimately follow a periodic pattern. Delays are completely defined by two finite lists of delay values. The first one consists of values that do not follow any particular pattern. They are applied only once (during what is called a transitory phase). The second list defines a pattern that is repeated over time; this corresponds to the periodic phase of the delay. Unfortunately, the inclusion of time-varying delays results in the definition of a non-commutative algebra. This means that the algorithms used in the traditional (max,+) algebra to compute the closure matrix of: (1) transition matrix of a system no longer apply. Therefore, this dissertation defines, (2) new fixed-point algorithm that computes closure matrices for time-varying discrete event systems based on their initial conditions.; The main criticism about the (max,+) algebra is that it applies only to deterministic systems. This dissertation also defines a hierarchical modeling framework within which the (max,+) algebra of signals can be applied to non-deterministic models. Given the constraints of this algebra, it has been necessary to restrict the type of non-determinism allowed in models. In essence, the impact of each nondeterministic part of a system has to be contained within an independent subnet that can be reduced to a single place. The delay of this place is the result of a convolution operation on the delays in each of the paths in the current non-deterministic part. The inf-convolution must be used to compute earliest firing times.