Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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 Free Access

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?)


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
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

DOI: http://dx.doi.org/10.1090/S0894-0347-01-00378-2
PII: S 0894-0347(01)00378-2
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