| Title:
|
Rational semimodules over the max-plus semiring and geometric approach to discrete event systems (English) |
| Author:
|
Gaubert, Stéphane |
| Author:
|
Katz, Ricardo |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
40 |
| Issue:
|
2 |
| Year:
|
2004 |
| Pages:
|
[153]-180 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
invariant spaces |
| Keyword:
|
reachability |
| Keyword:
|
geometric control |
| Keyword:
|
rational sets |
| Keyword:
|
Presburger arithmetics |
| Keyword:
|
max-plus algebra |
| Keyword:
|
discrete event systems |
| MSC:
|
06F05 |
| MSC:
|
16Y60 |
| MSC:
|
93B03 |
| MSC:
|
93B07 |
| MSC:
|
93B25 |
| MSC:
|
93B27 |
| MSC:
|
93C65 |
| idZBL:
|
Zbl 1249.93125 |
| idMR:
|
MR2069176 |
| . |
| Date available:
|
2009-09-24T20:00:18Z |
| Last updated:
|
2015-03-23 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135586 |
| . |
| Reference:
|
[1] Baccelli F., Cohen G., Olsder, G., Quadrat J.: Synchronization and Linearity.Wiley, New York 1992 Zbl 0824.93003, MR 1204266 |
| Reference:
|
[2] Berstel J.: Transductions and Context-Free Languages.Teubner, Stuttgart 1979 Zbl 0424.68040, MR 0549481 |
| Reference:
|
[3] Berstel J., Reutenauer C.: Rational Series and their Languages.Springer, New York 1988 Zbl 0668.68005, MR 0971022 |
| Reference:
|
[4] Bés A.: A survey of arithmetical definability: A tribute to Maurice Boffa.Soc. Math. Belgique 2002, pp. 1–54 MR 1900396 |
| Reference:
|
[5] Butkovič P.: Strong regularity of matrices – a survey of results.Discrete Applied Mathematics 48 (1994), 45–68 Zbl 0804.06017, MR 1254755, 10.1016/0166-218X(92)00104-T |
| Reference:
|
[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 1957609 |
| Reference:
|
[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 Zbl 0545.90101, MR 0782401 |
| Reference:
|
[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. MR 1746112, 10.1080/026811199281967 |
| Reference:
|
[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 |
| Reference:
|
[10] Cohen G., Gaubert, S., Quadrat J.: Linear projectors in the max-plus algebra: In: Proc.IEEE Mediterranean Conference, Cyprus, 1997, CDROM |
| Reference:
|
[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 10.1016/S1367-5788(99)90091-3 |
| Reference:
|
[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 MR 2039751, 10.1016/j.laa.2003.08.010 |
| Reference:
|
[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. |
| Reference:
|
[14] Conway J.: Regular Algebra and Finite Machines.Chapman and Hall, London 1971 Zbl 0231.94041 |
| Reference:
|
[15] Cuninghame-Green R.: Minimax Algebra.(Lecture Notes in Economics and Mathematical Systems 166.) Springer, Berlin 1976 Zbl 0739.90073, MR 0580321 |
| Reference:
|
[16] Eilenberg S., Schützenberger M.: Rational sets in commutative monoids: J.Algebra 13 (1969), 1, 173–191 MR 0246985, 10.1016/0021-8693(69)90070-2 |
| Reference:
|
[17] Gaubert S.: Théorie des systèmes linéaires dans les dioïdes.Thèse, École des Mines de Paris, July 1992 |
| Reference:
|
[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 |
| Reference:
|
[19] Gaubert S.: Performance evaluation of (max,+) automata.IEEE Trans. Automat. Control 40 (1995), 12, 2014–2025 Zbl 0855.93019, MR 1364950, 10.1109/9.478227 |
| Reference:
|
[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. |
| Reference:
|
[21] Gaubert S., Gunawardena J.: The duality theorem for min-max functions: C.R. Acad. Sci. 326 (1998), 43–48 MR 1649473, 10.1016/S0764-4442(97)82710-3 |
| Reference:
|
[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 Zbl 1108.20057, MR 2241626 |
| Reference:
|
[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 1473780 |
| Reference:
|
[24] Ginsburg S., Spanier E. H.: Semigroups, Presburger formulas, and languages.Pacific J. Math. 16 (1966), 2, 3–12 Zbl 0143.01602, MR 0191770, 10.2140/pjm.1966.16.285 |
| Reference:
|
[25] Gunawardena J., ed.: Idempotency.(Publications of the Isaac Newton Institute.) Cambridge University Press, Cambridge 1998 Zbl 1144.68006, MR 1608370 |
| Reference:
|
[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 Zbl 0652.06010, MR 0937558 |
| Reference:
|
[27] Katz R.: Problemas de alcanzabilidad e invariancia en el álgebra max-plus.Ph.D. Thesis, University of Rosario, November 2003 |
| Reference:
|
[28] Klimann I.: Langages, séries et contrôle de trajectoires.Thèse, Université Paris 7, 1999 |
| Reference:
|
[29] Klimann I.: A solution to the problem of $(A,B)$-invariance for series: Theoret.Comput. Sci. 293 (2003), 1, 115–139 MR 1957615, 10.1016/S0304-3975(02)00234-7 |
| Reference:
|
[30] Kolokoltsov V.: Linear additive and homogeneous operators.In: Idempotent Analysis (Advances in Soviet Mathematics 13), Amer. Math. Soc., Providence, RI 1992 Zbl 0925.47016, MR 1203786 |
| Reference:
|
[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 Zbl 0834.68058, MR 1297148, 10.1142/S0218196794000063 |
| Reference:
|
[32] Krob D.: Some consequences of a Fatou property of the tropical semiring.J. Pure and Applied Algebra 93 (1994), 231–249 Zbl 0806.68083, MR 1275966, 10.1016/0022-4049(94)90090-6 |
| Reference:
|
[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 1299364 |
| Reference:
|
[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 MR 1846814, 10.1023/A:1010266012029 |
| Reference:
|
[35] Mairesse J.: A graphical approach of the spectral theory in the (max,+) algebra.IEEE Trans. Automat. Control 40 (1995), 1783–1789 Zbl 0845.93036, MR 1354519, 10.1109/9.467674 |
| Reference:
|
[36] Moller P.: Théorie algébrique des Systèmes à Événements Discrets.Thèse, École des Mines de Paris, 1988 |
| Reference:
|
[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 MR 0478750, 10.1016/0022-0000(78)90021-1 |
| Reference:
|
[38] Pin J.-E.: Tropical semirings: In: Idempotency (J.Gunawardena, ed.), Cambridge University Press, Cambridge 1998, pp. 50–69 MR 1608374 |
| Reference:
|
[39] Plus M.: Max-plus toolbox of scilab: Available from the contrib section of http:--www-rocq.inria.fr/scilab, 1998 |
| Reference:
|
[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 1203789 |
| Reference:
|
[41] Schrijver A.: Theory of Linear and Integer Programming.Wiley, New York 1988 Zbl 0970.90052, MR 0874114 |
| Reference:
|
[42] Simon I.: Limited subsets of the free monoid.In: 19th Annual Symposium on Foundations of Computer Science 1978, pp. 143–150 MR 0539835 |
| Reference:
|
[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 1252678 |
| Reference:
|
[44] Wagneur E.: Moduloids and pseudomodules.1. dimension theory. Discrete Math. 98 (1991), 57–73 Zbl 0757.06008, MR 1139597, 10.1016/0012-365X(91)90412-U |
| Reference:
|
[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 Zbl 0898.68035, MR 1608375 |
| Reference:
|
[46] Wonham W.: Linear Multivariable Control: A Geometric Approach.Third edition. Springer, Berlin 1985 Zbl 0609.93001, MR 0770574 |
| Reference:
|
[47] Zimmermann K.: A general separation theorem in extremal algebras.Ekonom.-Mat. obzor 13 (1977), 2, 179–201 Zbl 0365.90127, MR 0453607 |
| . |
