Previous |  Up |  Next


reachability; controllability; max-algebra
We are interested here in the reachability and controllability problems for DEDS in the max-algebra. Contrary to the situation in linear systems theory, where controllability (resp observability) refers to a (linear) subspace, these properties are essentially discrete in the $\max $-linear dynamic system. We show that these problems, which consist in solving a $\max $-linear equation lead to an eigenvector problem in the $\min $-algebra. More precisely, we show that, given a $\max $-linear system, then, for every natural number $k\ge 1\,$, there is a matrix $\Gamma _k$ whose $\min $-eigenspace associated with the eigenvalue $1$ (or $\min $-fixed points set) contains all the states which are reachable in $k$ steps. This means in particular that if a state is not in this eigenspace, then it is not controllable. Also, we give an indirect characterization of $\Gamma _k$ for the condition to be sufficient. A similar result also holds by duality on the observability side.
[1] G: Birkhoff: Lattice Theory. A.M.S. Coll. Pub. Vol. XXV, Providence 1967 MR 0227053
[2] Baccelli F., Cohen G., Olsder G. J., Quadrat J. P.: Synchronization and Linearity. Wiley, Chichester 1992 MR 1204266 | Zbl 0824.93003
[3] Cunninghame–Green R. A.: Minimax Algebra. (Lecture Notes in Economics and Mathematical Systems 83.) Springer–Verlag, Berlin 1979 MR 0580321
[4] Gaubert S.: Théorie des Systèmes linéaires dans les Dioïdes. Thèse. Ecole Nationale Supérieure des Mines de Paris 1992
[5] Gazarik M. J., Kamen E. W.: Reachability and observability of linear system over Max–Plus. In: 5th IEEE Mediterranean Conference on Control and Systems, Paphos 1997, revised version: Kybernetika 35 (1999), 2–12 MR 1705526
[6] Gondran M., Minoux M.: Valeurs propres et vecteurs propres dans les dioïdes et leur interprétation en théorie des graphes. EDF Bull. Direction Études Rech. Sér. C Math. Inform. 2 (1977), 25–41
[8] Prou J.-M.: Thèse. Ecole Centrale de Nantes 1997
[9] Wagneur E.: Moduloïds and Pseudomodules. 1. Dimension Theory. Discrete Math. 98 (1991), 57–73 DOI 10.1016/0012-365X(91)90412-U | MR 1139597 | Zbl 0757.06008
Partner of
EuDML logo