Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture

Authors: Thierry Bousch and Jean Mairesse
Journal: J. Amer. Math. Soc. 15 (2002), 77-111
MSC (2000): Primary 49J27, 37D35
Published electronically: September 10, 2001
MathSciNet review: 1862798
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [AB] C. D. ALIPRANTIS and K. C. BORDER, Infinite dimensional analysis: a hitchhiker's guide, second edition, Springer (1999) MR 2000k:46001
  • [Ba] F. BACCELLI, G. COHEN, G. J. OLSDER AND J. P. QUADRAT, Synchronization and linearity, Wiley (1992) MR 94b:93001
  • [BW] M. A. BERGER and Y. WANG, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), pp. 21-27 MR 92m:15012
  • [BeS] J. BERSTEL and P. S´EÉBOLD, Sturmian words, in M. LOTHAIRE (ed.), Algebraic combinatorics on words, to appear in Cambridge University Press
  • [BT1] 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] V. D. BLONDEL and J. N. TSITSIKLIS, Complexity of stability and controllability of elementary hybrid systems, Automatica 35 (1999), pp. 479-489
  • [B1] T. BOUSCH, Le poisson n'a pas d'arêtes, Ann. Inst. H. Poincaré Proba. Stat. 36 (2000), pp. 489-508 CMP 2001:02
  • [B2] T. BOUSCH, La condition de Walters, Ann. Sci. Ec. Norm. Sup. 34 (2001), pp. 287-311
  • [BV] M. BRILMAN AND J. M. VINCENT, Dynamics of synchronized parallel systems, Stochastic Models 13 (1997), pp. 605-619 MR 98b:68043
  • [BS] S. BULLETT and P. SENTENAC, Ordered orbits of the shift, square roots, and the devil's staircase, Math. Proc. Camb. Phil. Soc. 115 (1994), pp. 451-481 MR 95j:58043
  • [CHL] D. A. CARLSON, A. B. HAURIE AND A. LEIZAROWITZ, Infinite horizon optimal control: deterministic and stochastic systems, second edition, Springer (1991) MR 92e:49001
  • [Co] G. COHEN, D. DUBOIS, J. P. QUADRAT AND M. VIOT, A linear system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing, IEEE Trans. Aut. Cont. 30 (1985), pp. 210-220 MR 86c:93002
  • [CKN] J. COHEN, H. KESTEN AND M. NEWMAN (eds.), Random matrices and their applications, Contemporary Mathematics 50, AMS (1986) MR 87a:60006
  • [CLT] 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
  • [CT] M. CRANDALL and L. TARTAR, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc. 78 (1980), pp. 385-390 MR 81a:47054
  • [DL1] I. DAUBECHIES AND J. LAGARIAS, Sets of matrices all infinite products of which converge, Linear Algebra Appl. 161 (1992), pp. 227-263 MR 93f:15006
  • [DL2] I. DAUBECHIES AND J. LAGARIAS, Corrigendum/addendum to: [DL1], Linear Algebra Appl. 327 (2001), pp. 69-83 CMP 2001:10
  • [DGS] M. DENKER, C. GRILLENBERGER AND K. SIGMUND, Ergodic theory on compact spaces, Lecture notes in Mathematics 0527, Springer (1976) MR 56:15879
  • [Fat] A. FATHI, Théorème KAM faible et théorie de Mather sur les systèmes lagrangiens, C. R. Acad. Sci. Paris Math. 324 (1997), pp. 1043-1046 MR 98g:58151
  • [Ga1] S. GAUBERT, Performance evaluation of $(\max,+)$ automata, IEEE Trans. Aut. Cont. 40 (1995), pp. 2014-2025 MR 96i:68058
  • [Ga2] S. GAUBERT, Introduction aux systèmes dynamiques à événements discrets, ENSTA course notes (1993)
  • [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)
  • [GM1] S. GAUBERT and J. MAIRESSE, Task resource models and $(\max,+)$ automata, in [Gun], pp. 133-144 MR 98i:00020
  • [GM2] S. GAUBERT and J. MAIRESSE, Modeling and analysis of timed Petri nets using heaps of pieces, IEEE Trans. Aut. Cont. 44 (1999), pp. 683-698 MR 99m:68139
  • [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] B. GAUJAL, M. JAFARI, M. BAYKAL-URSOY AND G. ALPAN, Allocation sequences of two processes sharing a resource, IEEE Trans. Robotics and Automation 11 (1995), pp. 748-753
  • [G2] B. GAUJAL, Optimal allocation sequences of two processes sharing a resource, Discrete Event Dynamical Systems 7 (1997), pp. 327-354
  • [Gun] J. GUNAWARDENA (ed.), Idempotency, Cambridge University Press (1998) MR 98i:00020
  • [Gu1] L. GURVITS, Stability of discrete linear inclusion, Linear Algebra Appl. 231 (1995), pp. 47-85 MR 96i:93056
  • [Gu2] L. GURVITS, Stability of linear inclusions. Part 2, NEC Research report TR96-173 (1996)
  • [HO] B. R. HUNT and E. OTT, Optimal periodic orbits of chaotic systems occur at low period, Phys. Rev. E 54 (1996), pp. 328-337
  • [Jen] O. M. JENKINSON, Frequency-locking on the boundary of the barycentre set, Experimental Mathematics 9 (2000), pp. 309-317 MR 2001g:37050
  • [LW] J. C. LAGARIAS and Y. WANG, The finiteness conjecture for the generalized spectral radius of a set of matrices, Linear Algebra Appl. 214 (1995), pp. 17-42 MR 95k:15038
  • [M1] R. MAÑÉ, Introdução à teoria ergódica, IMPA, Rio (1983) MR 87d:58085
  • [M2] R. MAÑÉ, Generic properties and problems of minimizing measures of lagrangian systems, Nonlinearity 9 (1996), pp. 273-310 MR 97d:58118
  • [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.
  • [MH] M. MORSE and G. A. HEDLUND, Symbolic dynamics II. Sturmian trajectories, Am. J. Math. 62 (1940), pp. 1-42 MR 1:123d
  • [Pin] J. E. PIN, Tropical semirings, in [Gun], pp. 50-69 MR 98i:00020
  • [RS] G.-C. ROTA and W. G. STRANG, A note on the joint spectral radius, Indag. Math. 22 (1960), pp. 379-381 MR 26:5434
  • [Sim] I. SIMON, The nondeterministic complexity of a finite automaton, in M. LOTHAIRE (ed.), Mots, Mélanges offerts à M. P. Schützenberger, Hermes, Paris (1990), pp. 384-400 MR 94k:68148
  • [TB] J. N. TSITSIKLIS and V. D. BLONDEL, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard, when not impossible, to compute and to approximate, Mathematics of Control, Signals and Systems 10 (1997), pp. 31-40 & correction p. 381 MR 99h:65238a; MR 99h:65238b
  • [Vin] J. M. VINCENT, Some ergodic results on stochastic iterative discrete event systems, Discrete Event Dynamic Systems 7 (1997), pp. 209-233

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 49J27, 37D35

Retrieve articles in all journals with MSC (2000): 49J27, 37D35

Additional Information

Thierry Bousch
Affiliation: Laboratoire de Mathématique (UMR 8628 du CNRS), bât. 425, Université de Paris-Sud, 91405 Orsay Cedex, France

Jean Mairesse
Affiliation: LIAFA, CNRS et Université Paris 7, case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France

Keywords: Topical maps, max-plus automata, Tetris, sturmian processes, optimal control, finiteness conjecture. ( Mots-clés. Applications topicales, automates max-plus, Tetris, processus sturmiens, contrôle optimal, conjecture de finitude.)
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”)
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society