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

Stéphane Gaubert; Ricardo Katz

Kybernetika (2004)

  • Volume: 40, Issue: 2, page [153]-180
  • ISSN: 0023-5954

Abstract

top
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 𝒮 n over a semiring 𝒮 is rational if it has a generating family that is a rational subset of 𝒮 n , 𝒮 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.

How to cite

top

Gaubert, Stéphane, and Katz, Ricardo. "Rational semimodules over the max-plus semiring and geometric approach to discrete event systems." Kybernetika 40.2 (2004): [153]-180. <http://eudml.org/doc/33692>.

@article{Gaubert2004,
abstract = {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.},
author = {Gaubert, Stéphane, Katz, Ricardo},
journal = {Kybernetika},
keywords = {invariant spaces; reachability; geometric control; rational sets; Presburger arithmetics; max-plus algebra; discrete event systems; invariant space; reachability; geometric control; rational set; Presburger arithmetic; max-plus algebra; discrete event system},
language = {eng},
number = {2},
pages = {[153]-180},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Rational semimodules over the max-plus semiring and geometric approach to discrete event systems},
url = {http://eudml.org/doc/33692},
volume = {40},
year = {2004},
}

TY - JOUR
AU - Gaubert, Stéphane
AU - Katz, Ricardo
TI - Rational semimodules over the max-plus semiring and geometric approach to discrete event systems
JO - Kybernetika
PY - 2004
PB - Institute of Information Theory and Automation AS CR
VL - 40
IS - 2
SP - [153]
EP - 180
AB - 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.
LA - eng
KW - invariant spaces; reachability; geometric control; rational sets; Presburger arithmetics; max-plus algebra; discrete event systems; invariant space; reachability; geometric control; rational set; Presburger arithmetic; max-plus algebra; discrete event system
UR - http://eudml.org/doc/33692
ER -

References

top
  1. Baccelli F., Cohen G., Olsder, G., Quadrat J., Synchronization and Linearity, Wiley, New York 1992 Zbl0824.93003MR1204266
  2. Berstel J., Transductions and Context-Free Languages, Teubner, Stuttgart 1979 Zbl0424.68040MR0549481
  3. Berstel J., Reutenauer C., Rational Series and their Languages, Springer, New York 1988 Zbl0668.68005MR0971022
  4. Bés A., A survey of arithmetical definability: A tribute to Maurice Boffa, Soc. Math. Belgique 2002, pp. 1–54 MR1900396
  5. Butkovič P., 10.1016/0166-218X(92)00104-T, Discrete Applied Mathematics 48 (1994), 45–68 (1994) Zbl0804.06017MR1254755DOI10.1016/0166-218X(92)00104-T
  6. Butkovič P., Cuninghame-Green R., The equation A ⊗ x = B ⊗ y over ( ℝ ∪ { - ∞ } , max , + ) , Theor. Comp. Sci. 48 (2003), 1, 3–12 MR1957609
  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 (1984) Zbl0545.90101MR0782401
  8. Cochet-Terrasson J., Gaubert, S., Gunawardena J., 10.1080/026811199281967 MR1746112DOI10.1080/026811199281967
  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 (1996) 
  10. Cohen G., Gaubert, S., Quadrat J., Linear projectors in the max-plus algebra: In: Proc, IEEE Mediterranean Conference, Cyprus, 1997, CDROM (1997) 
  11. Cohen G., Gaubert, S., Quadrat J., 10.1016/S1367-5788(99)90091-3, Annual Reviews in Control 23 (1999), 207–219 (1999) DOI10.1016/S1367-5788(99)90091-3
  12. Cohen G., Gaubert, S., Quadrat J., 10.1016/j.laa.2003.08.010, Linear Algebra and Appl. 279 (2004), 395–422. Also e-print arXiv:math.FA/0212294 MR2039751DOI10.1016/j.laa.2003.08.010
  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 Zbl0231.94041
  15. Cuninghame-Green R., Minimax Algebra, (Lecture Notes in Economics and Mathematical Systems 166.) Springer, Berlin 1976 Zbl0739.90073MR0580321
  16. Eilenberg S., Schützenberger M., 10.1016/0021-8693(69)90070-2, Algebra 13 (1969), 1, 173–191 (1969) MR0246985DOI10.1016/0021-8693(69)90070-2
  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 (199.) 
  19. Gaubert S., 10.1109/9.478227, IEEE Trans. Automat. Control 40 (1995), 12, 2014–2025 (1995) Zbl0855.93019MR1364950DOI10.1109/9.478227
  20. Gaubert S., Exotic semirings: Examples and general results: Support de cours de la 26 ième École de Printemps d’Informatique Théorique, Noirmoutier, 199 
  21. Gaubert S., Gunawardena J., 10.1016/S0764-4442(97)82710-3, R. Acad. Sci. 326 (1998), 43–48 (1998) MR1649473DOI10.1016/S0764-4442(97)82710-3
  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 Zbl1108.20057MR2241626
  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 (1997) MR1473780
  24. Ginsburg S., Spanier E. H., 10.2140/pjm.1966.16.285, Pacific J. Math. 16 (1966), 2, 3–12 (1966) Zbl0143.01602MR0191770DOI10.2140/pjm.1966.16.285
  25. Gunawardena J., ed., Idempotency, (Publications of the Isaac Newton Institute.) Cambridge University Press, Cambridge 1998 Zbl1144.68006MR1608370
  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 (1988) Zbl0652.06010MR0937558
  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., 10.1016/S0304-3975(02)00234-7, Comput. Sci. 293 (2003), 1, 115–139 MR1957615DOI10.1016/S0304-3975(02)00234-7
  30. Kolokoltsov V., Linear additive and homogeneous operators, In: Idempotent Analysis (Advances in Soviet Mathematics 13), Amer. Math. Soc., Providence, RI 1992 Zbl0925.47016MR1203786
  31. Krob D., 10.1142/S0218196794000063, Internat. J. Algebra and Comput. 4 (1994), 3, 405–425 (1994) Zbl0834.68058MR1297148DOI10.1142/S0218196794000063
  32. Krob D., 10.1016/0022-4049(94)90090-6, J. Pure and Applied Algebra 93 (1994), 231–249 (1994) Zbl0806.68083MR1275966DOI10.1016/0022-4049(94)90090-6
  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 (1994) MR1299364
  34. Litvinov G., Maslov, V., Shpiz G., 10.1023/A:1010266012029, Math. Notes 69 (2001), 5, 696–729. Also e-print arXiv:math.FA/0009128 MR1846814DOI10.1023/A:1010266012029
  35. Mairesse J., 10.1109/9.467674, IEEE Trans. Automat. Control 40 (1995), 1783–1789 (1995) Zbl0845.93036MR1354519DOI10.1109/9.467674
  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., 10.1016/0022-0000(78)90021-1, J. Comput. System Sci. 16 (1978), 323–332 (1978) MR0478750DOI10.1016/0022-0000(78)90021-1
  38. Pin J.-E., Tropical semirings: In: Idempotency (J, Gunawardena, ed.), Cambridge University Press, Cambridge 1998, pp. 50–69 (1998) MR1608374
  39. Plus M., Max-plus toolbox of scilab: Available from the contrib section of http:--www-rocq, 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 MR1203789
  41. Schrijver A., Theory of Linear and Integer Programming, Wiley, New York 1988 Zbl0970.90052MR0874114
  42. Simon I., Limited subsets of the free monoid, In: 19th Annual Symposium on Foundations of Computer Science 1978, pp. 143–150 (19th) MR0539835
  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 (1990) MR1252678
  44. Wagneur E., 10.1016/0012-365X(91)90412-U, 1. dimension theory. Discrete Math. 98 (1991), 57–73 (1991) Zbl0757.06008MR1139597DOI10.1016/0012-365X(91)90412-U
  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 (1998) Zbl0898.68035MR1608375
  46. Wonham W., Linear Multivariable Control: A Geometric Approach, Third edition. Springer, Berlin 1985 Zbl0609.93001MR0770574
  47. Zimmermann K., A general separation theorem in extremal algebras, Ekonom.-Mat. obzor 13 (1977), 2, 179–201 (1977) Zbl0365.90127MR0453607

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.