Discrete Geometry and Word Combinatorics

Valerie Berthe 1
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The aim of this lecture is to show how discrete geometry and word combinatorics can interact through the study of the most basic objects in discrete geometry, namely arithmetic discrete planes. In word combinatorics, Sturmian words and regular continued fractions are known to provide a very fruitful interaction between arithmetics, discrete geometry and symbolic dynamics. Recall that Sturmian words are infinite words which code irrational discrete lines over a two-letter alphabet. Most combinatorial properties of Sturmian words can be described in terms of the continued fraction expansion of the slope of the discrete line that they code. Our aim here is to show how to extend this interaction to higher dimensions. Special focus will be given to a generation method for discrete planes based on a formalism extending to the multidimensional case morphisms of the free monoid. The role played respectively by words and classical continued fractions will be played by stepped surfaces (which are discretizations of two-dimensional surfaces embedded in the three-dimensional space) and generalized unimodular Euclidean algorithms. We will use the fact that we can describe an arithmetic discrete plane either as a tiling of the plane by three kinds of lozenges (after projection), or else, as a multidimensional word over a three-letter alphabet (after coding).
Type de document :
Communication dans un congrès
CanaDAM'09: 2nd Canadian Discrete and Algorithmic Mathematics Conference, May 2009, Canada. 2009, 〈http://www.crm.umontreal.ca/CanaDAM2009/index_e.shtml〉
Liste complète des métadonnées

Contributeur : Valerie Berthe <>
Soumis le : vendredi 29 mai 2009 - 19:55:57
Dernière modification le : jeudi 11 janvier 2018 - 06:26:07


  • HAL Id : lirmm-00389856, version 1



Valerie Berthe. Discrete Geometry and Word Combinatorics. CanaDAM'09: 2nd Canadian Discrete and Algorithmic Mathematics Conference, May 2009, Canada. 2009, 〈http://www.crm.umontreal.ca/CanaDAM2009/index_e.shtml〉. 〈lirmm-00389856〉



Consultations de la notice