# Article

Full entry | PDF   (1.4 MB)
Keywords:
reachability; controllability; max-algebra
Summary:
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.
References:
[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