Combinatorics on words: Christoffel words and repetitions in by Jean Berstel, Aaron Lauve, Christophe Reutenauer, and Franco

By Jean Berstel, Aaron Lauve, Christophe Reutenauer, and Franco V. Saliola

The 2 components of this article are in response to sequence of lectures introduced by way of Jean Berstel and Christophe Reutenauer in March 2007 on the Centre de Recherches Mathematiques, Montreal, Canada. half I represents the 1st glossy and finished exposition of the speculation of Christoffel phrases. half II offers quite a few combinatorial and algorithmic elements of repetition-free phrases stemming from the paintings of Axel Thue--a pioneer within the thought of combinatorics on phrases. A newbie to the idea of combinatorics on phrases should be prompted by means of the varied examples, and the big number of routines, which make the booklet specified at this point of exposition. The fresh and streamlined exposition and the huge bibliography can also be favored. After interpreting this publication, newcomers can be able to learn glossy study papers during this quickly growing to be box and give a contribution their very own study to its improvement. skilled readers may 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 are going to additionally have fun with the historic presentation of the Thue-Morse be aware and its functions, and the radical effects on Abelian repetition-free phrases.

Show description

Read Online or Download Combinatorics on words: Christoffel words and repetitions in words PDF

Best combinatorics books

Applications of Unitary Symmetry And Combinatorics

A concise description of the prestige of a desirable medical challenge - the inverse variational challenge in classical mechanics. The essence of this challenge is as follows: one is given a suite of equations of movement describing a undeniable classical mechanical approach, and the query to be responded is: do those equations of movement correspond to a few Lagrange functionality as its Euler-Lagrange equations?

Analysis and Logic

This quantity offers articles from 4 impressive researchers who paintings on the cusp of research and good judgment. The emphasis is on lively learn subject matters; many effects are provided that experience no longer been released sooner than and open difficulties are formulated. massive attempt has been made by means of the authors to make their articles obtainable to mathematicians new to the realm

Notes on Combinatorics

Méthodes mathématiques de l’informatique II, collage of Fribourg, Spring 2007, model 24 Apr 2007

Optimal interconnection trees in the plane : theory, algorithms and applications

This booklet explores primary features of geometric community optimisation with purposes to numerous actual global difficulties. It offers, for the 1st time within the literature, a cohesive mathematical framework in which the homes of such optimum interconnection networks might be understood throughout a variety of metrics and price capabilities.

Additional resources for Combinatorics on words: Christoffel words and repetitions in words

Sample text

Suppose g ∈ F2 is of length r and suppose that u and v are positive elements with v = gug−1 . Let g = a1 · · · ar be a reduced expression for g, where ai ∈ {x, y, x−1 , y −1 } for 1 ≤ i ≤ r. We consider three cases. (i): If ℓ(gu) < ℓ(g) + ℓ(u), then the first letter z of u must be a−1 r ∈ {x, y}. Write u = zu1 and g = hz −1 for some u1 ∈ {x, y}∗ and some h ∈ F2 . Then v = gug−1 = (hz −1 )(zu1 )(hz −1 )−1 = h(u1 z)h−1 . Since ℓ(h) < r and z ∈ {x, y}, it follows from the induction hypothesis that u1 z and v are conjugate in {x, y}∗ .

If ǫ = p1 , p2 , . . , pr denote the sequence of palindromic prefixes of Pal(w) different than Pal(w) listed in order of increasing length, and if z1 , z2 , . . , zr ∈ {x, y} denote the letters in Pal(w) immediately following the prefixes p1 , p2 , . . , pr in Pal(w), then w = z1 z2 · · · zr . 10. If w = vzu, where u does not have an occurrence of the letter z, then Pal(wz) = Pal(w) Pal(v)−1 Pal(w), where the product is evaluated in the free group generated by {x, y}. 11. 7) Let αx = G = (x, xy) and αy = D = (yx, y).

3. The third is explained by our next characterization of Christoffel words. 2 (Mantaci, Restivo, Sciortino [MRS2003]). A word w ∈ {x, y}∗ is a conjugate of a Christoffel word if and only if BW T (w) takes the form y q xp , where p ⊥ q. 1. 1. 1. 2. The Burrows–Wheeler transform BW T is injective on Lyndon words (cf. [CDP2005] for more details): Given a Lyndon word w = a1 a2 · · · an , let b1 b2 · · · bn and c1 c2 · · · cn denote the first and last columns, respectively, of the Burrows–Wheeler matrix.

Download PDF sample

Rated 4.95 of 5 – based on 29 votes