Synchronization and linearity: An algebra for discrete event systems

I Discrete Event Systems and Petri Nets......Page 16
Introduction and Motivation......Page 18
Preliminary Remarks and Some Notation......Page 19
Miscellaneous Examples......Page 24
Planning......Page 25
Communication......Page 30
Production......Page 31
Queuing System with Finite Capacity......Page 34
Parallel Computation......Page 36
Traffic......Page 38
Continuous System Subject to Flow Bounds and Mixing......Page 41
Issues and Problems in Performance Evaluation......Page 44
Notes......Page 48
Graph Theory and Petri Nets......Page 50
Directed Graphs......Page 51
Graphs and Matrices......Page 54
Composition of Matrices and Graphs......Page 57
Maximum Cycle Mean......Page 62
The Cayley-Hamilton Theorem......Page 64
Definition......Page 69
Subclasses and Properties of Petri Nets......Page 75
Timed Event Graphs......Page 78
Simple Examples......Page 79
The Basic Autonomous Equation......Page 84
Constructiveness of the Evolution Equations......Page 93
Standard Autonomous Equations......Page 97
The Nonautonomous Case......Page 99
Stochastic Event Graphs......Page 103
Multigraphs......Page 104
Places with Finite Capacity......Page 105
Synthesis of Event Graphs from Interacting Resources......Page 106
Notes......Page 113
II Algebra......Page 114
Max-Plus Algebra......Page 116
Definitions......Page 117
The min Operation in the Max-Plus Algebra......Page 119
Matrices in Rmax......Page 120
Linear and Affine Scalar Functions......Page 121
Structures......Page 122
Systems of Linear Equations in (Rmax)n......Page 124
Spectral Theory of Matrices......Page 127
Application to Event Graphs......Page 130
Polynomial Functions P(Rmax)......Page 132
Rational Functions......Page 140
Algebraic Equations......Page 143
The Algebraic Structure S......Page 145
Linear Balances......Page 147
Linear Systems in S......Page 149
Determinant......Page 150
Solving Systems of Linear Balances by the Cramer Rule......Page 151
Some Polynomial Functions......Page 154
Factorization of Polynomial Functions......Page 155
Critical Graph of a Matrix A......Page 159
Eigenspace Associated with the Maximum Eigenvalue......Page 161
Spectral Projector......Page 163
Convergence of Ak with k......Page 164
Cyclic Matrices......Page 166
Notes......Page 167
Dioids......Page 168
Introduction......Page 169
Axiomatics......Page 170
Some Examples......Page 171
Subdioids......Page 172
Homomorphisms, Isomorphisms and Congruences......Page 173
Basic Notions in Lattice Theory......Page 174
Order Structure of Dioids......Page 176
Complete Dioids, Archimedian Dioids......Page 178
Lower Bound......Page 180
Distributive Dioids......Page 181
Isotony and Continuity of Mappings......Page 183
Elements of Residuation Theory......Page 187
Closure Mappings......Page 193
Residuation of Addition and Multiplication......Page 194
General Fixed-Point Equations......Page 200
The Case (x)=a xb......Page 204
The Case (x)=axb......Page 205
Some Problems of Best Approximation......Page 207
From `Scalars' to Matrices......Page 210
Residuation of Matrices and Invertibility......Page 211
Definitions and Properties of Formal Polynomials and Power Series......Page 213
Polynomial Matrices......Page 217
Rational Closure and Rational Calculus......Page 219
Rational Representations......Page 221
Yet Other Rational Representations......Page 223
Rational Representations in Commutative Dioids......Page 224
Dioids and Related Structures......Page 226
Related Results......Page 227
III Deterministic System Theory......Page 228
Two-Dimensional Domain Description of Event Graphs......Page 230
Introduction......Page 231
A Comparison Between Counter and Dater Descriptions......Page 233
A Dioid of Nondecreasing Mappings......Page 237
-Transforms of Daters and Representation by Power Series in......Page 240
The Zmax Algebra through Another Shift Operator......Page 246
The  Algebra......Page 248
 Equations for Event Graphs......Page 254
A First Derivation of Counters......Page 260
Counters Derived from Daters......Page 261
Alternative Definition of Counters......Page 263
Dynamic Equations of Counters......Page 264
 Backward Equations......Page 265
Backward Equations for Daters......Page 267
Preliminaries......Page 269
Definitions......Page 270
Main Theorem......Page 271
On the Coding of Rational Elements......Page 273
Realizations by - and -Transforms......Page 275
Numerical Functions Associated with Elements of B[[,]]......Page 277
Specialization to......Page 279
Eigenfunctions of Rational Transfer Functions......Page 280
Notes......Page 284
Max-Plus Linear System Theory......Page 286
Definitions......Page 287
Some Elementary Systems......Page 289
The Algebra of Impulse Responses......Page 292
Shift-Invariant Systems......Page 294
Systems with Nondecreasing Impulse Response......Page 295
Evaluation Homomorphism......Page 296
Closed Concave Impulse Responses and Inputs......Page 298
Closed Convex Inputs......Page 300
Polynomial, Rational and Algebraic Systems......Page 302
Examples of Polynomial Systems......Page 303
Characterization of Rational Systems......Page 304
Minimal Representation and Realization......Page 308
Sojourn Time and Correlations......Page 310
Stability and Stabilization......Page 314
Notes......Page 317
IV Stochastic Systems......Page 318
Ergodic Theory of Event Graphs......Page 320
Introduction......Page 321
The Event Graph......Page 322
Statistical Assumptions......Page 323
Statement of the Eigenvalue Problem......Page 325
Relation with the Event Graph......Page 329
Uniqueness and Coupling......Page 331
First-Order and Second-Order Theorems......Page 333
Notation and Statistical Assumptions......Page 335
Examples in Rmax......Page 336
Maximal Lyapunov Exponent in Rmax......Page 337
The Strongly Connected Case......Page 339
General Graph......Page 340
First-Order Theorems in Other Dioids......Page 344
Notation and Assumptions......Page 345
Ratio Equation in a General Dioid......Page 346
Stationary Solution of the Ratio Equation......Page 347
Specialization to Rmax......Page 349
Multiplicative Ergodic Theorems in Rmax......Page 363
Ratio Equation......Page 364
Backward Process......Page 366
From Stationary Ratios to Random Eigenpairs......Page 368
Finiteness and Coupling in Rmax; Positive Case......Page 369
Finiteness and Coupling in Rmax; Strongly Connected Case......Page 378
Finiteness and Coupling in Rmax; General Case......Page 380
Multiplicative Ergodic Theorems in Rmax......Page 381
Stationary Marking of Stochastic Event Graphs......Page 382
Appendix on Ergodic Theorems......Page 385
Notes......Page 386
Computational Issues in Stochastic Event Graphs......Page 388
Introduction......Page 389
Monotonicity Table for Stochastic Event Graphs......Page 390
Properties of Daters......Page 391
Properties of Counters......Page 395
Properties of Cycle Times......Page 399
Comparison of Ratios......Page 402
Event Graphs and Branching Processes......Page 404
Statistical Properties......Page 405
Simple Bounds on Cycle Times......Page 406
General Case......Page 411
Discrete Distributions......Page 416
Continuous Distribution Functions......Page 425
Stochastic Comparison......Page 428
Notes......Page 430
V Postface......Page 432
Related Topics and Open Ends......Page 434
The Exponential as a Tool; Another View on Cayley-Hamilton......Page 435
Rational Transfer Functions and ARMA Models......Page 438
Realization Theory......Page 439
More on Minimal Realizations......Page 441
Control of Discrete Event Systems......Page 443
Brownian and Diffusion Decision Processes......Page 445
Dynamic Programming......Page 446
Fenchel and Cramer Transforms......Page 448
Central Limit Theorem in Dynamic Programming......Page 449
The Brownian Decision Process......Page 450
Diffusion Decision Process......Page 452
FIFO Timed Petri Nets......Page 453
Evolution Equations......Page 455
Evolution Equations for Switching......Page 460
Integration of the Recursive Equations......Page 462
Min-Max Systems......Page 463
General Timed Petri Nets and Descriptor Systems......Page 465
Existence of Periodic Behavior......Page 466
Numerical Procedures for the Eigenvalue......Page 468
Stochastic Min-Max Systems......Page 471
About Cycle Times in General Petri Nets......Page 472
Notes......Page 474
Bibliography......Page 477
Notation......Page 487