Spelling suggestions: "subject:"sturmian work"" "subject:"sturmiana work""
1 |
Mots de retours et pavages dans les plans sturmiens / Return words in discrete planesSimonet, Matthieu 12 October 2012 (has links)
Les mots sturmiens sont une façon de coder les droites discrètes apériodiques. Ils ont été étudiés depuis la fin du 19ème siècle et disposent de nombreuses caractérisations. L'une d'elles, obtenue par Vuillon, est centrée sur la notion de mot de retour.Cette thèse a pour objet l'étude des mots sturmiens en dimension 2 vus comme codages des plans discrets apériodiques. L'objectif est d'aller vers une caractérisation des mots sturmiens bi-dimensionnels analogue à celle obtenue par Vuillon en dimension 1.Mais des problèmes propres à la dimension 2 rendent cette étude délicate, tels l'absence de concaténation de mots ou la difficulté à localiser un facteur au sein d'un mot. Afin d'y faire face, nous introduisons en dimension 2 les notions de motifs, motifs pointés, mots de localisation et mots de retour. Nous obtenons ainsi un prolongement à la dimension 2 d'un théorème de Morse et Hedlund concernant certains mots de retour dans un mot sturmien.Ce résultat nous permet d'établir un nouvel algorithme de fractions continues et nous permet de proposer, dans un cadre restreint, une notion de suite dérivée. / Sturmian words are a way to encode aperiodic discrete lines. They have been studied since the end of the 19th century and can be characterized in many ways. One of these characterizations, obtained by Vuillon, centers around the notion of return words.This thesis aims to study 2-dimensional Sturmian words as encodings of aperiodic discrete planes. It is a first step towards a characterization of 2-dimensional Sturmian words analogous to that of Vuillon in dimension 1.However, concerns specific to dimension 2, such as the impossibility to concatenate words or the difficulty to locate a factor inside a word make the study much trickier. To tackle this, we introduce in dimension 2 notions of patterns, pointed patterns, localization words and return words.We obtain a 2-dimensional version of a theorem of Morse and Hedlund concerning certain return words in a Sturmian word. This result enables us to establish a new continued-fractions algorithm and to introduce, in a restricted setting, a notion of derived sequence.
|
2 |
Digital lines, Sturmian words, and continued fractionsUscka-Wehlou, Hanna January 2009 (has links)
In this thesis we present and solve selected problems arising from digital geometry and combinatorics on words. We consider digital straight lines and, equivalently, upper mechanical words with positive irrational slopes a<1 and intercept 0. We formulate a continued fraction (CF) based description of their run-hierarchical structure. Paper I gives a theoretical basis for the CF-description of digital lines. We define for each irrational positive slope less than 1 a sequence of digitization parameters which fully specifies the run-hierarchical construction. In Paper II we use the digitization parameters in order to get a description of runs using only integers. We show that the CF-elements of the slopes contain the complete information about the run-hierarchical structure of the line. The index jump function introduced by the author indicates for each positive integer k the index of the CF-element which determines the shape of the digitization runs on level k. In Paper III we present the results for upper mechanical words and compare our CF-based formula with two well-known methods, one of which was formulated by Johann III Bernoulli and proven by Markov, while the second one is known as the standard sequences method. Due to the special treatment of some CF-elements equal to 1 (essential 1's in Paper IV), our method is currently the only one which reflects the run-hierarchical structure of upper mechanical words by analogy to digital lines. In Paper IV we define two equivalence relations on the set of all digital lines with positive irrational slopes a<1. One of them groups into classes all the lines with the same run length on all digitization levels, the second one groups the lines according to the run construction in terms of long and short runs on all levels. We analyse the equivalence classes with respect to minimal and maximal elements. In Paper V we take another look at the equivalence relation defined by run construction, this time independently of the context, which makes the results more general. In Paper VI we define a run-construction encoding operator, by analogy with the well-known run-length encoding operator. We formulate and present a proof of a fixed-point theorem for Sturmian words. We show that in each equivalence class under the relation based on run length on all digitization levels (as defined in Paper IV), there exists exactly one fixed point of the run-construction encoding operator.
|
Page generated in 0.0703 seconds