Rational semimodules over the max-plus semiring and geometric approach to discrete event systems

Gaubert, Stéphane   ; Katz, Ricardo

Kybernetika, Tome 40 (2004) no. 2, pp. 153-180

Abstract (VO)

We introduce rational semimodules over semirings whose addition is idempotent, like the max-plus semiring, in order to extend the geometric approach of linear control to discrete event systems. We say that a subsemimodule of the free semimodule ${\mathcal{S}}^n$ over a semiring ${\mathcal{S}}$ is rational if it has a generating family that is a rational subset of ${\mathcal{S}}^n$, ${\mathcal{S}}^n$ being thought of as a monoid under the entrywise product. We show that for various semirings of max-plus type whose elements are integers, rational semimodules are stable under the natural algebraic operations (sum, product, direct and inverse image, intersection, projection, etc). We show that the reachable and observable spaces of max-plus linear dynamical systems are rational, and give various examples.

Détail

Classification : 06F05, 16Y60, 93B03, 93B07, 93B25, 93B27, 93C65
Keywords: invariant spaces; reachability; geometric control; rational sets; Presburger arithmetics; max-plus algebra; discrete event systems

Bibliographie

[1] Baccelli F., Cohen G., Olsder, G., Quadrat J.: Synchronization and Linearity. Wiley, New York 1992 | MR | Zbl

[2] Berstel J.: Transductions and Context-Free Languages. Teubner, Stuttgart 1979 | MR | Zbl

[3] Berstel J., Reutenauer C.: Rational Series and their Languages. Springer, New York 1988 | MR | Zbl

[4] Bés A.: A survey of arithmetical definability: A tribute to Maurice Boffa. Soc. Math. Belgique 2002, pp. 1–54 | MR

[5] Butkovič P.: Strong regularity of matrices – a survey of results. Discrete Applied Mathematics 48 (1994), 45–68 | DOI | MR | Zbl

[6] Butkovič P., Cuninghame-Green R.: The equation $A\otimes x=B\otimes y$ over $({\mathbb{R}}\cup \lbrace -\infty \rbrace ,\max ,+)$. Theor. Comp. Sci. 48 (2003), 1, 3–12 | MR

[7] Butkovič P., Hegedüs G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom.-Mat. obzor 20 (1984), 2, 203–215 | MR | Zbl

[8] Cochet-Terrasson J., Gaubert, S., Gunawardena J.: A constructive fixed point theorem for min-max functions: Dynamics and Stability of Systems 14 (1999), 4, 407–43. | DOI | MR

[9] Cohen G., Gaubert, S., Quadrat J.: Kernels, images and projections in dioids. In: 3rd Workshop on Discrete Event Systems (WODES’96), IEE Edinburgh, August 1996, pp. 151–158

[10] Cohen G., Gaubert, S., Quadrat J.: Linear projectors in the max-plus algebra: In: Proc. IEEE Mediterranean Conference, Cyprus, 1997, CDROM

[11] Cohen G., Gaubert, S., Quadrat J.: Max-plus algebra and system theory: where we are and where to go now. Annual Reviews in Control 23 (1999), 207–219 | DOI

[12] Cohen G., Gaubert, S., Quadrat J.: Duality and separation theorem in idempotent semimodules. Linear Algebra and Appl. 279 (2004), 395–422. Also e-print arXiv:math.FA/0212294 | DOI | MR

[13] Cohen G., Moller P., Quadrat, J., Viot M.: Algebraic tools for the performance evaluation of discrete event systems: IEEE Proceedings: Special Issue on Discrete Event Systems 77 (1989), 1, 39–5.

[14] Conway J.: Regular Algebra and Finite Machines. Chapman and Hall, London 1971 | Zbl

[15] Cuninghame-Green R.: Minimax Algebra. (Lecture Notes in Economics and Mathematical Systems 166.) Springer, Berlin 1976 | MR | Zbl

[16] Eilenberg S., Schützenberger M.: Rational sets in commutative monoids: J. Algebra 13 (1969), 1, 173–191 | DOI | MR

[17] Gaubert S.: Théorie des systèmes linéaires dans les dioïdes. Thèse, École des Mines de Paris, July 1992

[18] Gaubert S.: Rational series over dioids and discrete event systems. In: Proc. 11th Conference on Analysis and Optimization of Systems – Discrete Event Systems. (Lecture Notes in Control and Inform. Sciences 199.) Sophia Antipolis, June 1994. Springer, Berlin 1995

[19] Gaubert S.: Performance evaluation of (max,+) automata. IEEE Trans. Automat. Control 40 (1995), 12, 2014–2025 | DOI | MR | Zbl

[20] Gaubert S.: Exotic semirings: Examples and general results: Support de cours de la 26$^{\text{ième}}$ École de Printemps d’Informatique Théorique, Noirmoutier, 199.

[21] Gaubert S., Gunawardena J.: The duality theorem for min-max functions: C. R. Acad. Sci. 326 (1998), 43–48 | DOI | MR

[22] Gaubert S., Katz R.: Reachability Problems for Products of Matrices in Semirings. Research Report 4944, INRIA, September 2003. Also e-print arXiv:math.OC/0310028. To appear in Internat. J. Algebra and Comput | MR | Zbl

[23] Gaubert S., Plus M.: Methods and applications of (max,+) linear algebra. In: 14th Symposium on Theoretical Aspects of Computer Science (STACS’97), Lübeck, March 1997 (R. Reischuk and M. Morvan, eds., Lecture Notes in Computer Science 1200), Springer, Berlin 1998, pp. 261–282 | MR

[24] Ginsburg S., Spanier E. H.: Semigroups, Presburger formulas, and languages. Pacific J. Math. 16 (1966), 2, 3–12 | DOI | MR | Zbl

[25] Gunawardena J., ed.: Idempotency. (Publications of the Isaac Newton Institute.) Cambridge University Press, Cambridge 1998 | MR | Zbl

[26] Helbig S.: On Caratheodory’s and Kreĭn-Milman’s theorems in fully ordered groups. Comment. Math. Univ. Carolin. 29 (1988), 1, 157–167 | MR | Zbl

[27] Katz R.: Problemas de alcanzabilidad e invariancia en el álgebra max-plus. Ph.D. Thesis, University of Rosario, November 2003

[28] Klimann I.: Langages, séries et contrôle de trajectoires. Thèse, Université Paris 7, 1999

[29] Klimann I.: A solution to the problem of $(A,B)$-invariance for series: Theoret. Comput. Sci. 293 (2003), 1, 115–139 | DOI | MR

[30] Kolokoltsov V.: Linear additive and homogeneous operators. In: Idempotent Analysis (Advances in Soviet Mathematics 13), Amer. Math. Soc., Providence, RI 1992 | MR | Zbl

[31] Krob D.: The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Internat. J. Algebra and Comput. 4 (1994), 3, 405–425 | DOI | MR | Zbl

[32] Krob D.: Some consequences of a Fatou property of the tropical semiring. J. Pure and Applied Algebra 93 (1994), 231–249 | DOI | MR | Zbl

[33] Krob D., Rigny A. Bonnier: A complete system of identities for one letter rational expressions with multiplicities in the tropical semiring. J. Pure Appl. Algebra 134 (1994), 27–50 | MR

[34] Litvinov G., Maslov, V., Shpiz G.: Idempotent functional analysis: an algebraical approach. Math. Notes 69 (2001), 5, 696–729. Also e-print arXiv:math.FA/0009128 | DOI | MR

[35] Mairesse J.: A graphical approach of the spectral theory in the (max,+) algebra. IEEE Trans. Automat. Control 40 (1995), 1783–1789 | DOI | MR | Zbl

[36] Moller P.: Théorie algébrique des Systèmes à Événements Discrets. Thèse, École des Mines de Paris, 1988

[37] Oppen D. C.: A $2^{2^{2^{pn}}}$ upper bound on the complexity of Presburger arithmetic. J. Comput. System Sci. 16 (1978), 323–332 | DOI | MR

[38] Pin J.-E.: Tropical semirings: In: Idempotency (J. Gunawardena, ed.), Cambridge University Press, Cambridge 1998, pp. 50–69 | MR

[39] Plus M.: Max-plus toolbox of scilab: Available from the contrib section of http:--www-rocq</b>. inria.fr/scilab, 1998

[40] Samborskiĭ S. N., Shpiz G. B.: Convex sets in the semimodule of bounded functions: In: Idempotent Analysis, pp. 135–137. Amer. Math. Soc., Providence, RI 1992 | MR

[41] Schrijver A.: Theory of Linear and Integer Programming. Wiley, New York 1988 | MR | Zbl

[42] Simon I.: Limited subsets of the free monoid. In: 19th Annual Symposium on Foundations of Computer Science 1978, pp. 143–150 | MR

[43] Simon I.: The nondeterministic complexity of a finite automaton. In: Mots – Mélange offert à M. P. Schutzenberger (M. Lothaire, ed.), Hermes, Paris 1990, pp. 384–400 | MR

[44] Wagneur E.: Moduloids and pseudomodules. 1. dimension theory. Discrete Math. 98 (1991), 57–73 | DOI | MR | Zbl

[45] Walkup E., Borriello G.: A general linear max-plus solution technique. In: Idempotency (J. Gunawardena, ed.), Cambridge University Press, Cambridge 1998, pp. 406–415 | MR | Zbl

[46] Wonham W.: Linear Multivariable Control: A Geometric Approach. Third edition. Springer, Berlin 1985 | MR | Zbl

[47] Zimmermann K.: A general separation theorem in extremal algebras. Ekonom.-Mat. obzor 13 (1977), 2, 179–201 | MR | Zbl