Discrete Event Systems in Dioid Algebra and Conventional Algebra

Philippe Declerck is Senior Lecturer LISA / ISTIA Laboratory at University of Angers, France.

• Chapter 1 Introduction 11.1 General introduction 11.2 History and three mainstays 21.3 Scientific context 21.3.1 Dioids 31.3.2 Petri nets 41.3.3 Time and algebraic models 51.4 Organization of the book 7Chapter 2 Consistency 92.1 Introduction 92.1.1 Models 92.1.2 Physical point of view 112.1.3 Objectives 122.2 Preliminaries 142.3 Models and principle of the approach 172.3.1 P-time event graphs 172.3.2 Dater form 212.3.3 Principle of the approach (example 2) 232.4 Analysis in the “static” case 252.5 “Dynamic” model 282.6 Extremal acceptable trajectories by series of matrices 312.6.1 Lowest state trajectory 322.6.2 Greatest state trajectory 352.7 Consistency 362.7.1 Example 3 412.7.2 Maximal horizon of temporal consistency 442.7.3 Date of the first token deaths 472.7.4 Computational complexity 482.8 Conclusion 50Chapter 3 Cycle Time 533.1 Objectives 533.2 Problem without optimization 553.2.1 Objective 553.2.2 Matrix expression of a P-time event graph 563.2.3 Matrix expression of P-time event graphs with interdependent residence durations 573.2.4 General form Ax ≤ b 593.2.5 Example 603.2.6 Existence of a 1-periodic behavior 613.2.7 Example continued 653.3 Optimization 673.3.1 Approach 1 673.3.2 Example continued 693.3.3 Approach 2 703.4 Conclusion 753.5 Appendix 76Chapter 4 Control with Specifications 794.1 Introduction 794.2 Time interval systems 804.2.1 (min, max, +) algebraic models 814.2.2 Timed event graphs 824.2.3 P-time event graphs 834.2.4 Time stream event graphs 844.3 Control synthesis 884.3.1 Problem 884.3.2 Pedagogical example: education system 894.3.3 Algebraic models 914.4 Fixed-point approach 924.4.1 Fixed-point formulation 924.4.2 Existence 954.4.3 Structure 1034.5 Algorithm 1074.6 Example 1114.6.1 Models 1114.6.2 Fixed-point formulation 1134.6.3 Existence 1144.6.4 Optimal control with specifications 1164.6.5 Initial conditions 1174.7 Conclusion 118Chapter 5 Online Aspect of Predictive Control 1195.1 Introduction 1195.1.1 Problem 1195.1.2 Specific characteristics 1205.2 Control without desired output (problem 1) 1225.2.1 Objective 1225.2.2 Example 1 1235.2.3 Trajectory description 1245.2.4 Relaxed system 1255.3 Control with desired output (problem 2) 1275.3.1 Objective 1275.3.2 Fixed-point form 1285.3.3 Relaxed system 1295.4 Control on a sliding horizon (problem 3): online and offline aspects 1305.4.1 CPU time of the online control 1315.5 Kleene star of the block tri-diagonal matrix and formal expressions of the sub-matrices 1325.6 Conclusion 138Bibliography 141List of Symbols 149Index 153