×

Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture. (English) Zbl 1057.49007

Summary: 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.

MSC:

49J27 Existence theories for problems in abstract spaces
37B15 Dynamical aspects of cellular automata
93C65 Discrete event control/observation systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Charalambos D. Aliprantis and Kim C. Border, Infinite-dimensional analysis, 2nd ed., Springer-Verlag, Berlin, 1999. A hitchhiker’s guide. · Zbl 0938.46001
[2] 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. · Zbl 0824.93003
[3] Marc A. Berger and Yang Wang, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), 21 – 27. · Zbl 0818.15006 · doi:10.1016/0024-3795(92)90267-E
[4] J. BERSTEL and P. SÉÉBOLD, Sturmian words, in M. LOTHAIRE , Algebraic combinatorics on words, to appear in Cambridge University Press · Zbl 0883.68104
[5] 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 · Zbl 0985.93042
[6] V. D. BLONDEL and J. N. TSITSIKLIS, Complexity of stability and controllability of elementary hybrid systems, Automatica 35 (1999), pp. 479-489 · Zbl 0943.93044
[7] T. BOUSCH, Le poisson n’a pas d’arêtes, Ann. Inst. H. Poincaré Proba. Stat. 36 (2000), pp. 489-508 CMP 2001:02
[8] T. BOUSCH, La condition de Walters, Ann. Sci. Ec. Norm. Sup. 34 (2001), pp. 287-311 · Zbl 0988.37036
[9] Matthieu Brilman and Jean-Marc Vincent, Dynamics of synchronized parallel systems, Comm. Statist. Stochastic Models 13 (1997), no. 3, 605 – 617. · Zbl 0896.60072 · doi:10.1080/15326349708807441
[10] 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). · Zbl 0823.58012 · doi:10.1017/S0305004100072236
[11] 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. · Zbl 0649.49001
[12] 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. · Zbl 0557.93005 · doi:10.1109/TAC.1985.1103925
[13] Joel E. Cohen, Harry Kesten, and Charles M. Newman , Random matrices and their applications, Contemporary Mathematics, vol. 50, American Mathematical Society, Providence, RI, 1986. · Zbl 0581.00014
[14] 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 · Zbl 0997.37016
[15] Michael G. Crandall and Luc Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc. 78 (1980), no. 3, 385 – 390. · Zbl 0449.47059
[16] Ingrid Daubechies and Jeffrey C. Lagarias, Sets of matrices all infinite products of which converge, Linear Algebra Appl. 161 (1992), 227 – 263. · Zbl 0746.15015 · doi:10.1016/0024-3795(92)90012-Y
[17] I. DAUBECHIES AND J. LAGARIAS, Corrigendum/addendum to: [DL1], Linear Algebra Appl. 327 (2001), pp. 69-83 CMP 2001:10
[18] Manfred Denker, Christian Grillenberger, and Karl Sigmund, Ergodic theory on compact spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976. · Zbl 0328.28008
[19] 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). · Zbl 0885.58022 · doi:10.1016/S0764-4442(97)87883-4
[20] Stéphane Gaubert, Performance evaluation of (max,+) automata, IEEE Trans. Automat. Control 40 (1995), no. 12, 2014 – 2025. · Zbl 0855.93019 · doi:10.1109/9.478227
[21] S. GAUBERT, Introduction aux systèmes dynamiques à événements discrets, ENSTA course notes (1993)
[22] S. GAUBERT and J. GUNAWARDENA, A nonlinear hierarchy for discrete event dynamical systems, in A. GIUA, R. SMEDINGA AND M. SPATHOPOULOS , Proceedings of WODES 98, IEE (1998)
[23] Jeremy Gunawardena , Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3 – 7, 1994. · Zbl 0898.16032
[24] 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. · Zbl 0955.68082 · doi:10.1109/9.754807
[25] S. GAUBERT and J. MAIRESSE, Performance evaluation of timed Petri nets using heaps of pieces, in P. BUCHOLZ AND M. SILVA , Petri nets and performance models (PNPM’99), IEEE Computer Society (1999), pp. 158-169.
[26] B. GAUJAL, M. JAFARI, M. BAYKAL-GÜRSOY AND G. ALPAN, Allocation sequences of two processes sharing a resource, IEEE Trans. Robotics and Automation 11 (1995), pp. 748-753
[27] B. GAUJAL, Optimal allocation sequences of two processes sharing a resource, Discrete Event Dynamical Systems 7 (1997), pp. 327-354 · Zbl 0909.68135
[28] Jeremy Gunawardena , Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3 – 7, 1994. · Zbl 0898.16032
[29] Leonid Gurvits, Stability of discrete linear inclusion, Linear Algebra Appl. 231 (1995), 47 – 85. · Zbl 0845.68067 · doi:10.1016/0024-3795(95)90006-3
[30] L. GURVITS, Stability of linear inclusions. Part 2, NEC Research report TR96-173 (1996)
[31] B. R. HUNT and E. OTT, Optimal periodic orbits of chaotic systems occur at low period, Phys. Rev. E 54 (1996), pp. 328-337
[32] Oliver Jenkinson, Frequency locking on the boundary of the barycentre set, Experiment. Math. 9 (2000), no. 2, 309 – 317. · Zbl 1106.37303
[33] 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. · Zbl 0818.15007 · doi:10.1016/0024-3795(93)00052-2
[34] 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). · Zbl 0581.28010
[35] Ricardo Mañé, Generic properties and problems of minimizing measures of Lagrangian systems, Nonlinearity 9 (1996), no. 2, 273 – 310. · Zbl 0886.58037 · doi:10.1088/0951-7715/9/2/002
[36] 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. · Zbl 0988.68018
[37] M. MORSE and G. A. HEDLUND, Symbolic dynamics II. Sturmian trajectories, Am. J. Math. 62 (1940), pp. 1-42 · Zbl 0022.34003
[38] Jeremy Gunawardena , Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3 – 7, 1994. · Zbl 0898.16032
[39] Gian-Carlo Rota and Gilbert Strang, A note on the joint spectral radius, Nederl. Akad. Wetensch. Proc. Ser. A 63 = Indag. Math. 22 (1960), 379 – 381. · Zbl 0095.09701
[40] Imre Simon, The nondeterministic complexity of a finite automaton, Mots, Lang. Raison. Calc., Hermès, Paris, 1990, pp. 384 – 400.
[41] John N. Tsitsiklis and Vincent D. Blondel, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard — when not impossible — to compute and to approximate, Math. Control Signals Systems 10 (1997), no. 1, 31 – 40. , https://doi.org/10.1007/BF01219774 John N. Tsitsiklis and Vincent D. Blondel, Lyapunov exponents of pairs of matrices. A correction: ”The Lyapunov exponent and joint spectral radius of pairs of matrices are hard — when not impossible — to compute and to approximate”, Math. Control Signals Systems 10 (1997), no. 4, 381. , https://doi.org/10.1007/BF01211553 John N. Tsitsiklis and Vincent D. Blondel, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard — when not impossible — to compute and to approximate, Math. Control Signals Systems 10 (1997), no. 1, 31 – 40. , https://doi.org/10.1007/BF01219774 John N. Tsitsiklis and Vincent D. Blondel, Lyapunov exponents of pairs of matrices. A correction: ”The Lyapunov exponent and joint spectral radius of pairs of matrices are hard — when not impossible — to compute and to approximate”, Math. Control Signals Systems 10 (1997), no. 4, 381. · Zbl 0888.65044 · doi:10.1007/BF01211553
[42] J. M. VINCENT, Some ergodic results on stochastic iterative discrete event systems, Discrete Event Dynamic Systems 7 (1997), pp. 209-233 · Zbl 0880.93057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.