By Jean Berstel, Aaron Lauve, Christophe Reutenauer, and Franco V. Saliola
ISBN-10: 0821844806
ISBN-13: 9780821844809
The 2 components of this article are in accordance with sequence of lectures brought by way of Jean Berstel and Christophe Reutenauer in March 2007 on the Centre de Recherches Mathematiques, Montreal, Canada. half I represents the 1st smooth and complete exposition of the idea of Christoffel phrases. half II provides quite a few combinatorial and algorithmic elements of repetition-free phrases stemming from the paintings of Axel Thue--a pioneer within the concept of combinatorics on phrases. A newbie to the speculation of combinatorics on phrases might be prompted via the various examples, and the massive number of workouts, which make the ebook specified at this point of exposition. The fresh and streamlined exposition and the large bibliography can be favored. After studying this e-book, newcomers might be able to learn sleek study papers during this speedily transforming into box and give a contribution their very own study to its improvement. skilled readers might be drawn to the finitary method of Sturmian phrases that Christoffel phrases supply, in addition to the radical geometric and algebraic technique selected for his or her exposition. they'll additionally take pleasure in the old presentation of the Thue-Morse be aware and its functions, and the unconventional effects on Abelian repetition-free phrases.
Read or Download Combinatorics on words: Christoffel words and repetitions in words PDF
Best combinatorics books
Download PDF by Leonard M. Adleman: Primality Testing and Abelian Varieties over Finite Fields
From Gauss to G|del, mathematicians have sought an effective set of rules to differentiate best numbers from composite numbers. This booklet offers a random polynomial time set of rules for the matter. The tools used are from mathematics algebraic geometry, algebraic quantity thought and analyticnumber conception.
Get Geometry of Algebraic Curves: Volume II with a contribution PDF
The second one quantity of the Geometry of Algebraic Curves is dedicated to the principles of the idea of moduli of algebraic curves. Its authors are study mathematicians who've actively participated within the improvement of the Geometry of Algebraic Curves. the topic is an exceptionally fertile and lively one, either in the mathematical group and on the interface with the theoretical physics group.
Download PDF by M. Ram Murty, V. Kumar Murty: Mathematical legacy of srinivasa ramanujan
Preface. - bankruptcy 1. The Legacy of Srinivasa Ramanujan. - bankruptcy 2. The Ramanujan tau functionality. - bankruptcy three. Ramanujan's conjecture and l-adic representations. - bankruptcy four. The Ramanujan conjecture from GL(2) to GL(n). - bankruptcy five. The circle approach. - bankruptcy 6. Ramanujan and transcendence. - bankruptcy 7.
- Numbers, sets and axioms: the apparatus of mathematics
- Set theory for the mathematician
- George Pólya: Collected Papers, Volume 4: Probability; Combinatorics; Teaching and Learning in Mathematics
- Combinatorial Pattern Matching: 8th Annual Symposium, CPM 97 Aarhus, Denmark, June 30–July 2, 1997 Proceedings
- Polyominoes: puzzles, patterns, problems, and packings
Extra resources for Combinatorics on words: Christoffel words and repetitions in words
Example text
Suppose |ad − bc| = 1. Then (1, 0) and (0, 1) are in the span of (a, b) and (c, d). Indeed, d(a, b) − b(c, d) = (ad − bc, 0) = ±(1, 0) and a(c, d) − c(a, b) = ±(0, 1). Thus (a, b) and (c, d) generate Z2 . Conversely, suppose (a, b) and (c, d) generate Z2 . Then the matrix equation a c x=b b d has a unique solution x ∈ Z2 for all vectors b ∈ Z2 . For b = (0, 1)T , we have x= a c b d −1 0 1 = 1 ad − bc d −c −b a 0 1 = 1 ad − bc −c a ∈ Z2 . It follows that |ad − bc| divides |a| and |c|. Since (a, b) and (c, d) generate Z2 , there exists i, j ∈ Z such that i(a, b) + j(c, d) = (1, 0).
Example. 6, marching upwards from the vertex (xxxy, xxxyxxy) to the root (x, y). 26 CHAPTER 3. STANDARD FACTORIZATION some Christoffel words w ... 6: Paths in the Christoffel tree from (u, v) to the root (x, y) preserve the cutting points for standard factorizations. Note that we have found a characterization of those Christoffel morphisms that preserve Christoffel words. Namely, f : (x, y) → (w1 , w2 ) is such a morphism if and only if (w1 , w2 ) is a standard factorization of a Christoffel word.
1. u = Pal(v) for some v ∈ {x, y}∗ if and only if xuy is a Christoffel word. 2. u = Pal(v) for some v ∈ {x, y}∗ if and only if u has relatively prime periods p and q and |u| = p + q − 2. Proof of 1. 6, if u = Pal(v) then xuy is a Christoffel word. Conversely, let w = xuy be a Christoffel word and let (w1 , w2 ) be its standard factorization. 4, |w1 |x |w2 |x |w1 |y |w2 |y ∈ SL2 (Z) ∩ N2×2 38 CHAPTER 4. PALINDROMIZATION (writing N2×2 for the set of 2 × 2 matrices with nonnegative integer entries).
Combinatorics on words: Christoffel words and repetitions in words by Jean Berstel, Aaron Lauve, Christophe Reutenauer, and Franco V. Saliola
by Richard
4.4