Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture
HTML articles powered by AMS MathViewer
- by Thierry Bousch and Jean Mairesse;
- J. Amer. Math. Soc. 15 (2002), 77-111
- DOI: https://doi.org/10.1090/S0894-0347-01-00378-2
- Published electronically: September 10, 2001
- PDF | Request permission
Abstract:
Given an Iterated Function System (IFS) of topical maps verifying some conditions, we prove that the asymptotic height optimization problems are equivalent to finding the extrema of a continuous functional, the average height, on some compact space of measures. We give general results to determine these extrema, and then apply them to two concrete problems. First, we give a new proof of the theorem that the densest heaps of two Tetris pieces are sturmian. Second, we construct an explicit counterexample to the Lagarias-Wang finiteness conjecture for the joint spectral radius of a set of matrices.
Résumé. Etant donné un système itéré de fonctions (IFS) topicales, vérifiant certaines conditions, nous montrons que les questions d’optimisation asymptotique de la hauteur sont équivalentes à la recherche des extrema d’une fonctionnelle continue, la hauteur moyenne, sur un certain espace compact de mesures. Nous présentons des résultats généraux permettant de déterminer ces extrema, puis appliquons ces méthodes à deux problèmes concrets. Premièrement, nous redémontrons que les empilements les plus denses de deux pièces de Tetris sont sturmiens. Deuxièmement, nous construisons un contre-exemple effectif à la conjecture de finitude de Lagarias et Wang sur le rayon spectral joint d’un ensemble de matrices.
References
- Charalambos D. Aliprantis and Kim C. Border, Infinite-dimensional analysis, 2nd ed., Springer-Verlag, Berlin, 1999. A hitchhiker’s guide. MR 1717083, DOI 10.1007/978-3-662-03961-8
- François Louis Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat, Synchronization and linearity, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1992. An algebra for discrete event systems. MR 1204266
- Marc A. Berger and Yang Wang, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), 21–27. MR 1152485, DOI 10.1016/0024-3795(92)90267-E [BeS]berstel J. Berstel and P. Séébold, Sturmian words, in M. Lothaire (ed.), Algebraic combinatorics on words, to appear in Cambridge University Press [BT1]jsr-nc V. D. Blondel and J. N. Tsitsiklis, The boundedness of all products of a pair of matrices is undecidable, Systems and Control Letters 41 (2000), pp. 135–140 [BT2]bt-complex V. D. Blondel and J. N. Tsitsiklis, Complexity of stability and controllability of elementary hybrid systems, Automatica 35 (1999), pp. 479–489 [B1]poisson T. Bousch, Le poisson n’a pas d’arêtes, Ann. Inst. H. Poincaré Proba. Stat. 36 (2000), pp. 489–508 [B2]cwalters T. Bousch, La condition de Walters, Ann. Sci. Ec. Norm. Sup. 34 (2001), pp. 287–311
- Matthieu Brilman and Jean-Marc Vincent, Dynamics of synchronized parallel systems, Comm. Statist. Stochastic Models 13 (1997), no. 3, 605–617. MR 1457662, DOI 10.1080/15326349708807441
- Shaun Bullett and Pierrette Sentenac, Ordered orbits of the shift, square roots, and the devil’s staircase, Math. Proc. Cambridge Philos. Soc. 115 (1994), no. 3, 451–481 (English, with English and French summaries). MR 1269932, DOI 10.1017/S0305004100072236
- D. A. Carlson and A. Haurie, Infinite horizon optimal control, Lecture Notes in Economics and Mathematical Systems, vol. 290, Springer-Verlag, Berlin, 1987. Theory and applications. MR 1117222, DOI 10.1007/978-3-662-02529-1
- Guy Cohen, Didier Dubois, Jean-Pierre Quadrat, and Michel Viot, A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing, IEEE Trans. Automat. Control 30 (1985), no. 3, 210–220. MR 778424, DOI 10.1109/TAC.1985.1103925
- Joel E. Cohen, Harry Kesten, and Charles M. Newman (eds.), Random matrices and their applications, Contemporary Mathematics, vol. 50, American Mathematical Society, Providence, RI, 1986. MR 841077, DOI 10.1090/conm/050 [CLT]thieu G. Contreras, A. Lopes and P. Thieullen, Lyapunov minimizing measures for expanding maps of the circle, manuscript (1999), to appear in Ergodic Theory and Dynamical Systems
- Michael G. Crandall and Luc Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc. 78 (1980), no. 3, 385–390. MR 553381, DOI 10.1090/S0002-9939-1980-0553381-X
- Ingrid Daubechies and Jeffrey C. Lagarias, Sets of matrices all infinite products of which converge, Linear Algebra Appl. 161 (1992), 227–263. MR 1142737, DOI 10.1016/0024-3795(92)90012-Y [DL2]daubechies2 I. Daubechies and J. Lagarias, Corrigendum/addendum to: [DL1], Linear Algebra Appl. 327 (2001), pp. 69–83
- Manfred Denker, Christian Grillenberger, and Karl Sigmund, Ergodic theory on compact spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976. MR 457675, DOI 10.1007/BFb0082364
- Albert Fathi, Théorème KAM faible et théorie de Mather sur les systèmes lagrangiens, C. R. Acad. Sci. Paris Sér. I Math. 324 (1997), no. 9, 1043–1046 (French, with English and French summaries). MR 1451248, DOI 10.1016/S0764-4442(97)87883-4
- Stéphane Gaubert, Performance evaluation of $(\max ,+)$ automata, IEEE Trans. Automat. Control 40 (1995), no. 12, 2014–2025. MR 1364950, DOI 10.1109/9.478227 [Ga2]cours-gaubert S. Gaubert, Introduction aux systèmes dynamiques à événements discrets, ENSTA course notes (1993) [GG]gg S. Gaubert and J. Gunawardena, A nonlinear hierarchy for discrete event dynamical systems, in A. Giua, R. Smedinga and M. Spathopoulos (eds.), Proceedings of WODES 98, IEE (1998)
- Jeremy Gunawardena (ed.), Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3–7, 1994. MR 1608365, DOI 10.1017/CBO9780511662508
- Stéphane Gaubert and Jean Mairesse, Modeling and analysis of timed Petri nets using heaps of pieces, IEEE Trans. Automat. Control 44 (1999), no. 4, 683–697. MR 1684424, DOI 10.1109/9.754807 [GM3]gm3 S. Gaubert and J. Mairesse, Performance evaluation of timed Petri nets using heaps of pieces, in P. Bucholz and M. Silva (eds.), Petri nets and performance models (PNPM’99), IEEE Computer Society (1999), pp. 158–169. [G1]gaujal1 B. Gaujal, M. Jafari, M. Baykal-Gürsoy \textand G. Alpan, Allocation sequences of two processes sharing a resource, IEEE Trans. Robotics and Automation 11 (1995), pp. 748–753 [G2]gaujal2 B. Gaujal, Optimal allocation sequences of two processes sharing a resource, Discrete Event Dynamical Systems 7 (1997), pp. 327–354
- Jeremy Gunawardena (ed.), Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3–7, 1994. MR 1608365, DOI 10.1017/CBO9780511662508
- Leonid Gurvits, Stability of discrete linear inclusion, Linear Algebra Appl. 231 (1995), 47–85. MR 1361100, DOI 10.1016/0024-3795(95)90006-3 [Gu2]gurvits2 L. Gurvits, Stability of linear inclusions. Part 2, NEC Research report TR 96-173 (1996) [HO]hunt-ott B. R. Hunt and E. Ott, Optimal periodic orbits of chaotic systems occur at low period, Phys. Rev. E 54 (1996), pp. 328–337
- Oliver Jenkinson, Frequency locking on the boundary of the barycentre set, Experiment. Math. 9 (2000), no. 2, 309–317. MR 1780215, DOI 10.1080/10586458.2000.10504655
- Jeffrey C. Lagarias and Yang Wang, The finiteness conjecture for the generalized spectral radius of a set of matrices, Linear Algebra Appl. 214 (1995), 17–42. MR 1311628, DOI 10.1016/0024-3795(93)00052-2
- Ricardo Mañé, Introdução à teoria ergódica, Projeto Euclides [Euclid Project], vol. 14, Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, 1983 (Portuguese). MR 800092
- Ricardo Mañé, Generic properties and problems of minimizing measures of Lagrangian systems, Nonlinearity 9 (1996), no. 2, 273–310. MR 1384478, DOI 10.1088/0951-7715/9/2/002 [MV]mv J. Mairesse and L. Vuillon, Optimal sequences in a heap model with two pieces, Liafa research report 98/09, Univ. Paris 7 (1998), to appear in Theor. Comp. Sci.
- T. Venkatarayudu, The $7$-$15$ problem, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 531. MR 1, DOI 10.1090/gsm/058
- Jeremy Gunawardena (ed.), Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3–7, 1994. MR 1608365, DOI 10.1017/CBO9780511662508
- Gian-Carlo Rota and Gilbert Strang, A note on the joint spectral radius, Indag. Math. 22 (1960), 379–381. Nederl. Akad. Wetensch. Proc. Ser. A 63. MR 147922, DOI 10.1016/S1385-7258(60)50046-1
- Imre Simon, The nondeterministic complexity of a finite automaton, Mots, Lang. Raison. Calc., Hermès, Paris, 1990, pp. 384–400. MR 1252678
- Lawrence M. Graves, The Weierstrass condition for multiple integral variation problems, Duke Math. J. 5 (1939), 656–660. MR 99 [Vin]vincent J. M. Vincent, Some ergodic results on stochastic iterative discrete event systems, Discrete Event Dynamic Systems 7 (1997), pp. 209–233
Bibliographic Information
- Thierry Bousch
- Affiliation: Laboratoire de Mathématique (UMR 8628 du CNRS), bât. 425, Université de Paris-Sud, 91405 Orsay Cedex, France
- Email: Thierry.Bousch@math.u-psud.fr
- Jean Mairesse
- Affiliation: LIAFA, CNRS et Université Paris 7, case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France
- Email: Jean.Mairesse@liafa.jussieu.fr
- Received by editor(s): July 11, 2000
- Published electronically: September 10, 2001
- Additional Notes: The work of the second author was partially supported by the European Community Framework IV programme through the research network ALAPEDES (“The ALgebraic Approach to Performance Evaluation of Discrete Event Systems”)
- © Copyright 2001 American Mathematical Society
- Journal: J. Amer. Math. Soc. 15 (2002), 77-111
- MSC (2000): Primary 49J27, 37D35
- DOI: https://doi.org/10.1090/S0894-0347-01-00378-2
- MathSciNet review: 1862798