Abdel Belaïd

Nazih Ouwayed

Segmentation of ancient Arabic documents

This chapter addresses the problem of ancient Arabic document segmentation. As ancient documents neither have a real physical structure nor logical one, the segmentation will be limited to textual area or to line extraction in the areas. Although this type of segmentation appears quite simple, its implementation remains a challenging task. This is due to the state of the old document where the image is of low quality, the lines are not straight, sinuous and connected. Given the failure of traditional methods, we proposed a method for line extraction in multi-oriented documents. The method is based on an image meshing that allows it to detect locally and safely the orientations. These orientations are then extended to larger areas. The orientation estimation uses the energy distribution of Cohen's class, more accurate than the projection method. Then, the method exploits the projection peaks to follow the connected components forming text lines. The approach ends with a final separation of connected lines, based on the exploitation of the morphology of terminal letters.

Introduction

The ancient handwriting is inherently complex because of its irregularity due to the manual aspect of the script. Rarely, the writers used line support (or layer) to write, resulting in sinuous lines of writing. Moreover, because of the calligraphic style of the writing, ligatures are easily introduced between the parts of words and attachment occurred between the words of the successive rows. Adding to this that as the document existed only on paper, updating was done directly on the text itself, Abdel Belaïd LORIA, Campus Scientifique, 54500 Vandoeuvre, France -e-mail: abdel.belaid@loria.fr Nazih Ouwayed LORIA, Campus Scientifique, 54500 Vandoeuvre, France -e-mail: nazih.ouwayed@loria.fr 1 which led either to extend the lines in the margins, or adding entire blocks of lines in these margins.

All these artifacts complicate the problem of line segmentation which is essentially contextual in old documents, although most segmentation techniques of modern document are rather "natural", seeking essentially parallel alignments of connected components. The problem with this "contextual" segmentation is new and complex, which is the challenge in research over the last decade.

The literature suggests haphazardly a lot of techniques for extracting lines. Some are more suited than others to the former. We will expose, in the first part of this chapter, a classification of these techniques. Several classification choices are possible, either by the focus type, either by the script type or finally by the method procedure, bottom up or top down. The second section will be devoted to the segmentation of a class of ancient Arabic documents. A further difficulty arises when dealing with Arabic, corresponding mostly to the calligraphic aspect more accentuated in the case of Arabic (see Fig 1 showing different document classes with different kinds of orientation)

Given the failure of traditional methods, we proposed a method for line extraction in multi-oriented documents [START_REF] Ouwayed | Multi-Oriented Text Line Extraction from Handwritten Arabic Documents[END_REF][START_REF] Ouwayed | Estimation de l'inclinaison d'un document arabe manuscrit numérisé par analyse temps-fréquence des histogrammes de projection[END_REF][START_REF] Ouwayed | Separation of Overlapping and Touching Lines within Handwritten Arabic Documents[END_REF][START_REF] Ouwayed | Une Approache Générale pour l'Extraction des Lignes des Documents Arabes Anciens Multi-orientées[END_REF][START_REF] Ouwayed | General Text Line Extraction Approach based on Locally Orientation Estimation[END_REF][START_REF] Ouwayed | Segmentation en lignes de documents anciens : application aux documents arabes[END_REF]. The technique has been studied for Arabic documents but can be generalized to any other script that writing is linear. The method starts by an image meshing allowing us to progressively and locally determine the orientations. The orientation is estimated using the energy distribution of Cohen's class on the projection histogram profile. This local orientation is then enlarged to extract the orientation areas. Afterwards, the text lines are extracted locally in each area basing on the connected components follow-up. Finally, the connected components that touch in adjacent lines are separated.. The chapter is organized as follows. In the section 2, a brief state of the art is given concerning the segmentation approaches. The multi-skew detection algorithm is detailed in section 3. We present some experimental results in section 4 and conclusion and the future trends of this work will be given in section 5.

Previous work

The literature mentions a quantity of approaches proposed for document line segmentation. Some of them are top-down while others are bottom-up. . Top down methods start from the whole image and iteratively subdivide it into smaller blocks to isolate the desired part. They use either an a priori knowledge on the documents such as interline or inter column spaces, or a document model to reach such a segmentation. The localization of white separations is generally done by analyzing the projection histogram profile, either by analyzing vertical stripes like in [START_REF] Bennasri | Extraction des lignes d'un texte manuscrit Arabe[END_REF], or by shredding the interline surface with local minima tracers like in [START_REF] Nicolas | Text Line Segmentation in Handwritten Document Using a Production System[END_REF], or finally by using a vector distance between histogram peaks and pixels, as in [START_REF] Antonacopoulos | Document Image Analysis for World War II Personal Records[END_REF]. To face the inclination problem, one uses Hough transform that considers the whole image composed of straight lines [START_REF] Shapiro | Handwritten document image segmentation and analysis[END_REF]. Given the failure of these global methods, other researchers are trying to use a knowledge model, as DMOS model proposed by [START_REF] Coüasnon | DMOS, une méthode générique de reconnaissance de documents : évaluation sur 60 000 formulaires du XIXe siècle[END_REF] which consists of a grammatical formalism position to model the document structure, or the model of [START_REF] Zheng | A Model-based Line Detection Algorithm in Documents[END_REF] corresponding to a vectorization based algorithm, parametrized by some line features such as angle, length, etc. Nicolas, Paquet and Heutte [START_REF] Nicolas | Text Line Segmentation in Handwritten Document Using a Production System[END_REF] propose an IA problem solving framework using production systems.

Bottom up methods deal with noise problems and writing variation. Most methods of line extraction in handwritten documents are bottom-up. The connected component based methods are the mainstay of the bottom up approaches. They are clustered into bigger elements such as words, lines and blocks. In each research, simple rules are used in a different way. These rules are based on the geometric relationships between neighboring blocks, such as distance, overlap, and size compatibility. The difference between the different works lies in their capabilities to cope with space variation and influence of the script and the writer peculiarities. Several approaches for clustering connected components have been proposed in the literature, such as K NN, Hough transform, Smoothing, Repulsive-attractive Network, Minimal Spanning Tree (MST) and deformable models.

Clustering methods related to the notion of mutual neighborhood have been considered in the clustering literature, as in [START_REF] Zahour | Contribution à la segmentation de textes manuscrits anciens[END_REF] where the clustering is operated on different kinds of textual blocks extracted from vertical strips, or in [START_REF] Likforman-Sulem | Extracting lines on handwritten documents by perceptual grouping[END_REF] where a perceptual grouping based on the "Gestalt theory" principles, such as proximity and similarity, is operated, or finally in [START_REF] Feldbach | Line Detection and Segmentation in Historical Church Registers[END_REF] where the grouping is based on the text line alignments. Hough transform is also used in bottom up approaches. The main questions are related to the voting points, the most representative of the text lines. In [START_REF] Likforman-Sulem | A Hough Based Algorithm for Extracting Text Lines in Handwritten Document[END_REF], the voting points correspond to the center of gravity of connected components. In Pu and Shi [START_REF] Pu | A natural learning algorithm based on Hough transform for text lines extraction in handwritten documents[END_REF], they correspond to the minima of the connected components, located in a vertical strip on the left side of the image. In [START_REF] Louloudis | Text line and word segmentation of handwritten documents[END_REF], the voting points correspond to character blocks which size is estimated from the average of the character sizes in the document.

The smoothing technique (Run Length Smoothing or RLS), is to darken the small spaces between the consecutive black pixels in the horizontal direction, which leads to connect them. The boxes which include the successive connected components in the image, form the lines. In [START_REF] Shi | Line Separation for Complex Document Images Using Fuzzy Run length[END_REF], a fuzzy run length algorithm is used. In [START_REF] Lebourgeois | Networking digital document images[END_REF], lines are extracted by applying RLSA, adapted to a gray scale image. Instead of connecting a series of white and black pixels, the gradient of the image is expanded in the horizontal direction with a tilt angle that varies between ±30 • .

The repulsive attractive network is a dynamic system to minimize energy, which interacts with the textual image by attractive and repulsive forces defined on the network components and the document image [START_REF] Oztop | Repulsive attractive network for baseline extraction on document images[END_REF]. Experimental results indicate that the network can successfully extract the baselines under significant noise in the presence of overlaps between the ascending and descending parts of characters in two lines.

Considering the connected components in a document as the vertices of a graph, we can obtain a complete undirected graph. A spanning tree of a connected graph is a tree that contains all the vertices of this graph. A minimal spanning tree of a graph is that spanning tree for which the sum of the edges is minimal among all the spanning trees of this graph. A minimal spanning tree of a graph can be generated with Kruskal algorithm. In this algorithm, the tree is built by inserting the remaining unused edge with the smallest cost until all the vertices are connected [START_REF] Yin | Handwritten text line segmentation by clustering with distance metric learning[END_REF].

The deformable model is an analytical approach which can act interactively on the modeling. It allows to change (in time and space) the model representation of the model towards the solution of the minimization problem introduced in the modeling. Concretely, this leads to introduce a term of time evolution in the minimization criterion, which allows, each time, to influence the prior model when necessary, and to readjust to a better solution. Early work in this area are those of Kass, Witkin and Terzopoulos [START_REF] Kass | Snakes: Active contour models[END_REF]. In the case of a 2D image, the deformable contour model is used to find an existing object. The process is iterative. From an initial contour, a mechanism of deformable contour is applied to change this form so that it is the target area. The evolution mechanism is an energy function. The target area will be found by minimizing this energy. Several deformable contour models exist in the literature. Here are a few examples: the parametric active contour model (snake [START_REF] Kass | Snakes: Active contour models[END_REF], the geometric snake [START_REF] Caselles | Geodesic active contours[END_REF], the Level Set method [START_REF] Pluempitiwiriyawej | STACS: new active contour scheme for cardiac MR image segmentation[END_REF][START_REF] Osher | Geometric Level Set Methods in Imaging,Vision,and Graphics[END_REF][START_REF] Sethian | Curvature and the evolution of fronts[END_REF], the B-spline or Bsnake [START_REF] Leitner | From Splines and Snakes to SNAKE SPLINES[END_REF] and the Mumford-Shah model [START_REF] Ramlau | A Mumford-Shah level-set approach for the inversion and segmentation of X-ray tomography data[END_REF]).

Table 1 summarizes all the methods mentioned, divided according to 15 criteria: lines types (straight, oriented and cursive), materials types (printed, handwritten, multi-oriented interval orientation (IO), Latin, Chinese, Indian, Arabic, Persian, Urdu, image level (C: Color, G: Gray and B: Binary) and mesh. All these approaches are either too general, proceeding by projection or by alignment search, or too local, operating by connected component following. They find here their limits facing to the poor quality and multi-orientation of documents. Most of these techniques have been applied to documents with a single orientation. The adaptation of these approaches is impossible if we want to extract all directions.

Overview of the proposed system

Given the failure of traditional methods, we proposed a method for line extraction in multi-oriented documents. The technique has been studied for Arabic documents but can be generalized to any other script that writing is linear. The method is based on an image meshing that allows it to detect locally and safely the orientations. These orientations are then extended to larger areas. The only assumption is that initially the central part of the paper is horizontal. The orientation estimation uses the energy distribution of Cohen's class, more accurate than the projection method. Then, the method exploits the projection peaks to follow the connected components forming text lines. The approach ends with a final separation of connected lines, based on the exploitation of the morphology of terminal letters.

Image Meshing

In this step, the document image is partitioned into small meshes. The mesh size is generated, based on the idea that a mesh must approximately contain 3 lines, so as to produce a projection histogram profile that is representative of the writing orientation. To find the lines, the Active Contour Model (or Snake) is applied. The traditional external energy has some limitations such as the edge initialization near the contour and the poor convergence to regions with concavities. For that reason, Xu et al. [START_REF] Xu | Gradient Vector Flow: A New External Force for Snakes[END_REF] developed a new kind of external energy that permits the snake to start far from the object, and forces it into boundary concavities. This energy is named gradient vector flow, or GVF. In our application, the major axis (equal to the first harmonic of the Fourier descriptor) of the connected components is used as the initial Snake. We used the GVF as external energy and a null internal energy. To detect the alignments, some morphological operations such as dilation and erosion are first applied to the initial image (see Figure 2.b) to expand the edges. Then, the major axis of each connected component is determined using the Fourier descriptors [START_REF] Montagnat | A review of deformable surfaces: topology, geometry and deformation[END_REF] (see Figure 2.c). Finally, the energy minimization mechanism is operated on the snake to deform and push it to the text edge, more or less similar to the connected component skeleton (see Figure 2.d). To ensure that the lines will be detected, we increment the size of the major axis by a threshold equal to the quarter of the average width of the connected components. This threshold is obtained by experiments. Finally, the connected components that belong to the same line are grouped to form the lines (see Figure 2.e). Figure 4.b shows the results of the automatic meshing of the document presented in the figure 4.a.

In order to reduce the running speedup, we discard the meshes containing few pixels because their inclination is insignificant. If a mesh contains some text (i.e. few connected components) and thus no noise, it is automatically merged with the neighbor meshes.

Orientation Area Extraction

Orientation Estimation

As the lines are wavy, the orientation is first searched in small meshes where it is more likely to have fragments of straight lines. Traditionally, the projection his-

Time-Frequency Distributions

To have a more robust estimator, we therefore considered using a time-frequency representation of the histogram projection. This distribution best responds that projection to the peaks generated by the lines, translating their presence in high energy.

It is becoming less sensitive to false maxima disrupting calculating depths of the peaks in the histogram which his orientation significant. We used the Cohen's class distributions which are quadratic and verify the invariance property by temporal or frequency translation. Each member of this class is distinguished by a kernel which has a determinant role in the quality of the provided images and in the properties it verifies. We limited to the Wigner-Ville distribution (WVD) which their properties allow to be more reactive to the presence of histogram peaks than the others distributions of the Cohen class [START_REF] Ouwayed | Estimation de l'inclinaison d'un document arabe manuscrit numérisé par analyse temps-fréquence des histogrammes de projection[END_REF].

Traditional approaches of signal processing such as Fourier transform can not study the signal variation over time and frequency. The energetic time-frequency distributions go beyond what these approaches allow by analyzing the non-stationarity of a signal and distribute the energy of a signal in time and frequency.

According to [START_REF] Hlawatsch | Linear and quadratic time-frequency signal representation[END_REF], the energy E x of a signal x(t) is defined as

E x = +∞ -∞ |x(t)| 2 dt = +∞ -∞ | x( f )| 2 d f (1)
where x( f ) is the Fourier transform of the signal x(t). The value E x is quadratic. For this reason, the time-frequency distributions must keep this property.

Cohen's Class: in 1966, Cohen [START_REF] Auger | Quelques commentaires sur des représentations temps-fréquence proposées récemment[END_REF][START_REF] Cohen | Generalized phase-space distribution functions[END_REF][START_REF] Escudié | Sur une formulation générale de la représentation en temps et en fréquence dans l'analyse des signaux d'énergie finie[END_REF] proved that a significant number of time-frequency distributions can be seen as particular cases of the following general expression:

C x (t, f ) = +∞ -∞ +∞ -∞ φ dD (τ, ξ )A x (τ, ξ )e j2π(tξ -f τ) dξ dτ, (2)
where A x (τ, ξ ) is the ambiguity function defined by:

A x (τ, ξ ) = +∞ -∞ x(t + τ/2) x * (t -τ/2) e -j2πξ t dt
The Cohen's class contains all the time-frequency distributions that are covariant under time-and frequency-shifts. The members of this class are identified by a particular kernel φ dD (τ, ξ ), (expressed here in the delay-Doppler plane dD) which determines their theoretical properties [START_REF] Classen | The Wigner distribution -A tool for time frequency analysis, Parts I-III[END_REF][START_REF] Flandrin | Time-Frequency/Time-Scale Analysis[END_REF][START_REF] Hlawatsch | Linear and quadratic time-frequency signal representation[END_REF] and their practical readability.

We want to use these distributions on the signal representing the histogram projection profile in each mesh, in order to estimate its orientation. The Cohen's class distributions are used to estimate the orientation because when computing the projection histogram of a document along one direction of projection, we obtain, if this direction is the real orientation of the document, a histogram in which each line leads to a clearly localized local maximum. Each block of the document leads in the projection histogram to a succession of periodic peaks and valleys, whose period is relatively constant. This periodic succession is delimited by the block size ("time" support) and oscillates at a frequency determined by the space width between the lines. As all the pixels are accumulated in the same positions, the local maxima have higher energy levels than with other projection directions. This explains why we can estimate the orientation of a document by seeking the projection angle for which the time-frequency distribution localizes a large energy level on a small area of the timefrequency plane. For example, Figure 3 shows the increase of the maximum of the Wigner-Ville distribution when the number of peaks and valleys increases and when the valleys become wider.

To estimate the orientation angle, we use the analytic signal x a (t) of the centered squared root of the projection histogram x(t) of the document. The analytic signal is the signal x(t) without its negative frequencies. The histogram x(t) is determined by projecting each document with a chosen orientation. To calculate all possible projection histograms, we turn the image around its center of gravity (which gives us a point deduced from the image content and not from its size and framing) and we choose the horizontal axis as an arbitrary reference for the zero degree angle. Then, we compute a time-frequency representation for the squared root of each projection histogram, whose average has been removed. The angle corresponding to the histogram with the highest maximum value of its time-frequency representation is chosen as the estimated angle of the document. Kavallieratou et al. [START_REF] Kavallieratou | Skew angle estimation in document processing using Cohen's class distributions[END_REF][START_REF] Kavallieratou | Skew angle estimation for printed and handwritten documents using the Wigner-Ville distribution[END_REF] already used the Wigner-Ville distribution (DWV) to estimate the overall direction of Latin documents printed or handwritten. In this work, we wanted to first determine the properties of time-frequency representations that seem desirable for such an application, to then establish a list of performances, the performances were finally evaluated.

Orientation Area Expanding

To extend the areas of orientation, we examine the orientations in neighboring meshes and proceed to an extension or a correction. Considering the writing direction in Arabic, we examine pairs of neighbors along three right-left directions: straight, sloping upward and sloping down. The two neighbor meshes are merged if the orientation of the global mesh is equal to one of them, otherwise the orientations are maintained in both meshs. The operation is repeated for all the document meshes. After this step, the zones will be constructed.

When a mesh contains several orientations, the mesh orientation will be erroneous. To detect this phenomenon, we observe the orientation of the horizontal (resp. vertical) surrounding meshes which have different angles. Since this case arises inside the main horizontal (resp. vertical) writing, the vertical (resp. horizontal) projection profile is used to resolve this case. The first minimum value in the projection profile is looked for from the right representing the end of the first inclination (I m minimum index). Then the mesh is divided at I m into two meshes.

Being applied automatically, the initial paving edges can cross the connected components creating problems (false maxima) in text line detection. The incorrect paving exists only in the horizontal and the vertical zones. We need to correct the position of these edges by proceeding a horizontal or vertical shift in order that the local paving covers the local connected components. In the horizontal (resp. vertical) area, the edge that divides two consecutive rows (resp. columns) is moved to the nearest position in these rows (resp. columns) when the horizontal (resp. vertical) projection vector for each of their two consecutive meshes has a minimum value (see Figure 4.g).

Text Line Extraction

The text line follow-up starts in the first window on the right side of the page. The algorithm starts by looking for the new maxima (see Figure 5.a). Each peak represents the starting point P s of the orientation line bl j . The ending point P e of the orientation line is calculated using the P s , the orientation, the width and the height of each window (see Figure 5.b). The orientation line bl j is calculated basing on the two points (P s , P e ) and the orientation of the window. The connected components that belong to a baseline are looked for construct the text line (see Figure 5.c).

A step of text line correction follows the text line detection to assign the nondetected components and the diacritical symbols to the appropriate text line (see Figure 5.c and d). A distance method is used to address this problem. First, the distance between the centroid of non-detected component or diacritical symbol C i and the text line is calculated. C i is assigned to the text line l j if d ci,l j < d ci,l j+1 else to l j + 1.

Connected Line Separation

The connections occur between two successive lines when their characters touch. Often, these connections are made between ascenders in the lower line and descenders in the higher line. Table 2 lists the four categories of connection in Arabic: a) a descender with right loop, connects a vertical ascender, b) a left descender with a loop, touches a vertical ascender, c) a right descender touches the higher part of the loop of a character, and d) a left descender connects the higher part of the lower curve of a letter.

In all connection cases, we note the presence of a descender connecting a lower end letter. The descenders are grouped into two categories: (a,c) where the descender of the line starts from the right, and (b, d) where the descender of the line starts from the left. To streamline the work, the analysis focuses on the connection areas. (see Figure 6 ). The method starts by extracting in the two lines, the connected component created by the connection between the two successive lines (see Figure 7.a). Then, the intersection points of each connected component is detected (see Figure 7.b, the points are in red). An intersection point is a pixel that has at least three neighboring pixels. As in the case chosen, the connection occurs at a single point of intersection S p close the minimum axis (valley between two lines, see Figure 7.c). Thus, the point S p is the nearest point of the minimum axis (see Figure 7.d). We then look for the starting point of the ligature, Bp, which is generally the highest point, near the baseline of the top line. Then, from this point, the method is to follow the descending character (i.e. its skeleton, see Figure 7.f). The following continues beyond the intersection point respecting an angular variation corresponding to the curvature of the descending character.

Experiments and Discussion

To study the effectiveness of our approach, we have experimented on 100 Arabic ancient documents containing 2,500 lines. These documents belong to a database stemmed from web sites of the Tunisian National Library, National Library of Medicine in the USA and National Library and Archives of Egypt. The tests were prepared after a manual areas and lines labeling step of each document. The rotation angle examined during these experiments ranged from -75 • to +90 • . The execution time is measured from the meshing phase until the line separation phase. It depends on the document and the mesh sizes. The tests were performed on a PC with a Pentium M 1.4 GHz and a cache of 1 GB in Windows XP. The application was developed with MATLAB completed by the time-frequency toolbox tftb [START_REF] Auger | Quelques commentaires sur des représentations temps-fréquence proposées récemment[END_REF].

The approach is composed of two main steps: multi-oriented area detection and text line extraction. Our results are measured according to theses algorithms. The multi-oriented algorithm is composed of three main steps: image meshing, orientation estimation and orientation extension and paving correction. A global accuracy rate of 97% is reached. The 3% error are shared by the three stages of treatment: 1% is due to the image paving, 1.3% is due to the orientation estimation and 0.7% is due to the orientation extension and paving correction.

In image meshing, it is just needed at least three text lines to obtain a projection profile representing the orientation in each mesh. So, if this criterion is not obtained by the paving algorithm, some errors may happen for area detection. The error rate of 1% is divided in two cases: 0.7% is due to the adjacent line connection and 0.3% is due to the small oriented areas. In the first case, the connection between lines is very frequent in ancient Arabic documents. When the active contour model (Snake) is applied in a mesh to alignements extract, it is possible that it connect two adjacent lines. This will increase the alignement height and consequently the mesh height. A large mesh may include different oriented areas. In the second case, the oriented areas are composed of few small lines. These areas can be gathered by the paving in other meshes and naturally will not be extracted. The Figure 10 shows the image meshing results of 4 different documents. We can note in these documents the presence at least of three lines in each mesh. The meshes in our documents have, in some cases, more than one orientation or cursive lines. In the two cases, the orientation estimation is wrong and will be wrong for the orientation extension and consequently for the area detection. The error rate of 0.9% is due to the meshes with multi-orientation. The 0.4% error is due to the Arabic curvature lines in Arabic ancient documents. The Figure 11 shows the results of the first orientation estimation of four documents selected in our database. Each color represent an orientation (see Figure 4 for the color legend). We remark in these documents the presence of meshes with erronous orientation (multi-orientations or cursive lines (Gray color)).

Four extension rules are applied for mesh extension having the same orientation. In the extension phase, any error is happened because all possible orientations in the documents are considered. The error rate of 0.7% is due to the paving correction. As this paving is rectangular, the correction can be applied just along the horizontal and vertical directions. In some cases (oblique areas), the paving correction can not be applied that will yield some segmentation errors. The Figure 12 shows the results of the multi-oriented areas extraction of the four selected documents. Each area is visualized by a color. In theses documents, all the multi-oriented areas are extracted correctely.

Table 3 summarizes the results of the 4 representative documents chosen arbitrary from the 100 documents selected. These results show the effectiveness and the performance of the multi-oriented area detection algorithm.

For line segmentation, the extraction rate reaches 98.6%. The 0.9% of non detected lines is due to the detection area algorithm. The error rate of 0.5% is due to the Table 3: Results of the multi-skew estimation for the four documents.

presence of diacritical symbols in the beginning of lines that create false maxima. Figure 13 illustrates the effectiveness of our algorithm on a sample of 3 documents chosen randomly among the 100 documents processed. To identify the lines, each pair of consecutive lines are presented in two different colors.

Conclusion

A multi-oriented text line extraction approach is proposed in this chapter based on the local orientation estimation. To extract the lines, the approach proceeds first by an image paving of the document. Then, the orientation in each mesh is estimated, extended and corrected. Finally, the text lines are extracted and separated. The mesh size is estimated using the active contour model (Snake) approach. This size is fixed once three lines in the mesh are extracted. The skew detection approach use the Cohen's class distributions applied on the projection histogram profile in each mesh and considered as a signal. The Wigner-Ville distribution (WVD) from this class is retained for our application thanks to its interesting properties adapted to the properties of ours signals. The mesh area is extended to similar oriented meshes to obtain largest orientation areas using 4 rules. These rules depends on the orientations presented in these documents. The text lines are extracted in each mesh using a follow-up connected components algorithm. The lines are separated based on the analysis of the terminal Arabic letters.

Experimental results on various types of handwritten Arabic documents show that the proposed method has achieved a promising performance for the text line extraction. This approach will be generalized to other documents types (Latin, Urdu, Farsi etc.) and to heterogeneous documents with text and images.

Fig. 1 :

 1 Fig. 1: Examples of four categories of handwritten ancient document: (a) Mono-oriented, (b) Multi-oriented, (c) Multi-scripts, and (d) heterogeneous.

Fig. 2 :

 2 Fig. 2: Application of the Snake for line detection, (a) initial image, (b) dilation and erosion of the image, (c) major axis drawn for each connected component of the lines. The ellipse encapsulates the initial connected component of (b). (d) shows the distorted snake of (c). (e) gives the final result showing the connected components gathered in each line.

Fig. 3 :

 3 Fig. 3: Examples of maximum value of the Wigner-Ville distribution obtained for different projection histogram profiles when the number of peaks and valleys increases and when the valleys become wider.

Fig. 4 :

 4 Fig. 4: The results for the different steps of the multi-skew detection approach.

Fig. 5 :Table 2 :

 52 Fig. 5: Text line detection steps for a window, (a) maxima detection, (b) orientation lines estimation, (c) assignment of each connected component and diacritical symbol to its appropriate line, (d) extracted lines.

Fig. 6 :

 6 Fig. 6: Connection areas and direction of descenders (right direction indicated by the red arrow, and the erroneous direction, by the blue arrow).

Fig. 7 :

 7 Fig. 7: Different steps of the separation of connected components.

Fig. 8 :

 8 Fig. 8: (a) Example of Arabic connected components (the Arabic letter "ra" is connected with the letter "alif"), (b) estimation algorithm of the angular variation.

Fig. 9 :

 9 Fig. 9: Results of some connected lines separation.

Fig. 10 :

 10 Fig. 10: Meshing results of 4 different documents .

Fig. 11 :Fig. 12 :

 1112 Fig. 11: Results of the first orientation estimation of the four selected documents

  Figure Document Resolution w × h of Execution Zone number size (dpi) paving(pixels) time True Detected First document 572×800 72 75× 75 35 s 5 5 Second document 410×625 72 75× 75 30 s 5 5 Third document 750×941 72 120×120 34 s 2 2 Fourth document 362×500 72 90× 90 30 s 2 2

Fig. 13 :

 13 Fig. 13: Result examples of the text lines extraction.

Table 1 :

 1 Line segmentation bibliography

	Class	Category	Authors	Straight	Line Type Oriented	Cursive	Printed	Handwritten	Multi-oriented	I. O.	Material Type Latin Chinese	Indian	Arabic	Persian	Urdu	Level	Meshing
			[Nicolaouall209]	x x			x			x						G,B
	Top-Down	Projection based	[Bennasri et al. 99] [Shapiro et al. 93] [Antonacopoulos et al.	x x x x x		x	x x			x x			x			B x B B
			04]
		Document Model	[Nagy et al. 88] [Lu et al. 04]	x x x		x x				x x						B x B x
			[Likformanfaure1994] x x x		x			x						G,B
		k-NN
			[Zahour et al. 04]	x x x		x						x			B
			[Zahour et al. 07]	x x x		x						x			B
			[Zahour et al. 08]	x x x		x						x			B
			[Feldbach et al. 01]	x x			x			x						G
	Bottom-Up	Hough Transform Smoothing	[Likforman et al. 95] [Pu ert al. 98] [Malleron et al. 09] [Louloudis 09] [proceeding8] [Bourgeois et al. 01]	x x x x x x x x x x x x x x x x x x x x x x x		x x ±45 • x x						B B B G,B B G
		Repulsive-attractive [Oztop et al. 99]	x x x		x			x			x x		G
		MST	[Yin et al. 08] [Nicolas et al. 04]	x x x x			x x			x	x					B B
		Snake	[Bukhari et al. 09]	x x x x x x		x			x		x G,B
		Level set	[Li et al. 08]	x x x x x x		x x x x			B
		Mumford-Shah	[Xiaojun et al. 09]	x x x		x x		x						G


S Brlek

D Jamet
email: jamet@loria.fr

G Paquin

Smooth Words on 2-letter alphabets having same parity ⋆

Keywords: Smooth words, Kolakoski word, Lyndon factorization, letter frequency

In this paper, we consider smooth words over 2-letter alphabets {a, b}, where a, b are integers having same parity, with 0 < a < b. We show that all are recurrent and that the closure of the set of factors under reversal holds for odd alphabets only. We provide a linear time algorithm computing the extremal words, w.r.t. lexicographic order. The minimal word is an infinite Lyndon word if and only if either a = 1 and b odd, or a, b are even. A connection is established between generalized Kolakoski words and maximal infinite smooth words over even 2-letter alphabets revealing new properties for some of the generalized Kolakoski words. Finally, the frequency of letters in extremal words is 1/2 for even alphabets, and for a = 1 with b odd, the frequency of b's is 1/( √ 2b -1 + 1).

Introduction

Smooth infinite words over Σ = {1, 2} form an infinite class K of infinite words containing the well known Kolakoski word K [START_REF] Kolakoski | Self Generating Runs, Problem 5304[END_REF] defined as one of the two fixed points of the run-length encoding function ∆, that is

∆(K) = K = 2211212212211211221211212211211212212211212212 • • • .
They are characterized by the property that the orbit obtained by iterating ∆ is contained in {1, 2} * . As a discrete dynamical system, (K, ∆) is topologically conjugate of the full shift (Σ * , σ) where σ is the shift operator. In the early work of Dekking [START_REF] Dekking | On the structure of self generating sequences, Séminaire de théorie des nombres de Bordeaux[END_REF] there are some challenging conjectures on the structure of K that still remain unsolved despite the efforts devoted to the study of patterns in K. For instance, we know from Carpi [START_REF] Carpi | On repeated factors in C ∞ Inform[END_REF] that K does contain only a finite number of squares, implying by direct inspection that K is cubefree. This result was extended in [START_REF] Brlek | Combinatorial properties of smooth infinite words[END_REF] to the infinite class K of smooth words over Σ = {1, 2}. Weakley [START_REF] Weakley | On the number of C ∞ -words of each length[END_REF] showed that the complexity function (number of factors of length n) of K is polynomially bounded. In [START_REF] Brlek | A note on differentiable palindromes[END_REF], a connection was established between the palindromic complexity and the recurrence of K. More recently, Berthé et al. [START_REF] Berthé | Smooth words over arbitrary alphabets[END_REF] studied smooth words over arbitrary alphabets and obtained a new characterization of the infinite Fibonacci word. Relevant work may also be found in [START_REF] Bergeron-Brlek | Patterns in Smooth Tilings[END_REF] and in [START_REF] Berthé | Smooth words over arbitrary alphabets[END_REF][START_REF] Jamet | Discrete surfaces and infinite smooth words[END_REF], where generalized Kolakoski words are studied for arbitrary alphabets. Finally, in [START_REF] Paquin | Properties of the extremal infinite smooth words[END_REF], the authors studied the extremal infinite smooth words, that is the minimal and the maximal ones w.r.t. the lexicographic order, over the alphabets {1, 2} and {1, 3}: a surprising link was established between the minimal infinite smooth word over {1, 3} and the Fibonacci word.

Here, we deal with smooth words over 2-letter alphabets {a, b} where a < b are positive integers having same parity. The paper is organized as follows.

In Section 2, we borrow from Lothaire [START_REF] Lothaire | Combinatorics on words[END_REF] all the basic notions on combinatorics on words, while in Section 3, we briefly sketch the computation of extremal infinite smooth words and recall the main results of Paquin et al. [START_REF] Paquin | Properties of the extremal infinite smooth words[END_REF]. Section 4 deals with the extremal smooth words over odd alphabets. We generalize a result of [START_REF] Paquin | Properties of the extremal infinite smooth words[END_REF] about the extremal words over {1, 3}: we show that Φ(m {a,b} ) = (ab) ω where m {a,b} is the minimal smooth word over the alphabet {a, b} and Φ is a natural bijection (Theorem 12), giving linear time algorithm for computing the extremal words ( Corollary 14). A recurrent definition of extremal smooth words over the alphabet {1, b} is given and it provides the letter frequencies (Theorem 20). Next, we prove that the set F (w) of factors of an infinite smooth word w is closed under reversal, and consequently, that w is recurrent (Proposition 15). Finally, we show that the minimal infinite smooth word is an infinite Lyndon word if and only if a = 1 and then, that the Lyndon factorization of ∆(m {a,b} ) is an infinite sequence of finite Lyndon words (Theorem 19). Section 5 is devoted to even alphabets, in which case Φ(m {a,b} ) = ab ω (Theorem 22 and Corollary 23), yielding in turn a linear time algorithm to generate the extremal words. From the algorithm, we deduce that the frequency of the letters a and b is 1 2 . Moreover, smooth words over even alphabets are recurrent (Proposition 25) despite the fact that the set of factors is not closed under reversal (Proposition 26). Minimal smooth words are infinite Lyndon words (Theorem 29), and a connection is established between generalized Kolakoski words and maximal infinite smooth words. It provides new properties for some generalized Kolakoski words which are still open problems for the alphabet {1, 2}.

Preliminaries

Throughout this paper Σ is a finite alphabet of letters equipped with an order <. A finite word is a finite sequence of letters w : [1..n] -→ Σ, n ∈ N of length n, and w[i] denotes its i-th letter. The set of n-length words over Σ is denoted by Σ n . By convention the empty word is denoted by ε and its length is 0. The free monoid generated by Σ is defined by Σ * = n≥0 Σ n and Σ * \ ε is denoted Σ + . The set of right infinite words, also called infinite words for short, is denoted by Σ ω and Σ ∞ = Σ * ∪ Σ ω . Adopting a consistent notation for finite words over the infinite alphabet N, N * = n≥0 N n is the set of finite sequences and N ω is that of infinite ones. Given a word w ∈ Σ * , a factor f of

w is a word f ∈ Σ * satisfying ∃x, y ∈ Σ * , w = xf y. If x = ε (resp. y = ε ) then f is called a prefix (resp. suffix).
A block of length k is a factor of the particular form f = α k , with α ∈ Σ. The set of all factors of w, also called the language of w, is denoted by F (w), and those of length n is F n (w) = F (w) ∩ Σ n , while Pref(w) (resp. Suff(w)) denotes the set of all prefixes (resp. suffixes) of w. The length of a word w is |w|, and the number of occurrences of a factor f ∈ Σ * is |w| f . For a finite word w, the frequency of the letter a is defined by d a (w) = |w| a /|w|. For an infinite word w, we follow [START_REF] Pytheas-Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF] and define the frequency of a letter a in w by

d a (w) = lim n→∞ 1 n |w[1.
.n]| a whenever this limit exists. An infinite word w is said recurrent if |w| f is infinite for every factor f ∈ F (w).

Over an arbitrary 2-letter alphabet Σ = {a, b}, there is a usual length preserving morphism, the complementation, defined by a = b ; b = a, which extends to words as follows. The complement of u

= u[1]u[2] • • • u[n] ∈ Σ n , is the word u = u[1] u[2] • • • u[n]. The reversal of u is the word u = u[n] • • • u[2]u[1].
For u, v ∈ Σ * , we write u ≺ v if and only if u is a proper prefix of v or if there exists an integer k such that u

[i] = v[i] for 1 ≤ i ≤ k -1 and u[k] < v[k].
The relation defined by u v if and only if u = v or u ≺ v, is called the lexicographic order. That definition holds for Σ ∞ . Note that in general, the complementation does not preserve the lexicographic order. Indeed, when u is not a proper prefix of v then

u ≻ v ⇐⇒ u ≺ v. (1)
A word u ∈ Σ * is a Lyndon word if u ≺ v for all proper non-empty suffixes v of u. For instance, the word 11212 is a Lyndon word while 12112 is not since 112 ≺ 12112. A word of length 1 is clearly a Lyndon word. The set of Lyndon words is denoted by L. From Lothaire [START_REF] Lothaire | Combinatorics on words[END_REF], we take the following theorem.

Theorem 1 [Lyndon] Any non empty finite word w is uniquely expressed as a non increasing product of Lyndon words

w = ℓ 1 ℓ 2 • • • ℓ n = n i=1 ℓ i , where ℓ i ∈ L, and ℓ 1 ℓ 2 • • • ℓ n . (2)
Siromoney et al. [START_REF] Siromoney | Infinite lyndon words[END_REF] extended Theorem 1 to infinite words. The set L ∞ of infinite Lyndon words consists of words smaller than any of their suffixes.

Theorem 2 [START_REF] Siromoney | Infinite lyndon words[END_REF] Any infinite word w is uniquely expressed as a non increasing product of Lyndon words, finite or infinite, in one of the two following forms:

(i) either there exists an infinite sequence (ℓ k ) k≥1 of elements in L such that w = ℓ 1 ℓ 2 ℓ 3 • • • and for all k, ℓ k ℓ k+1 . (ii) there exist a finite sequence ℓ 1 , . . . , ℓ m (m ≥ 0) of elements in L and ℓ m+1 ∈ L ∞ such that

w = ℓ 1 ℓ 2 • • • ℓ m ℓ m+1 and ℓ 1 • • • ℓ m ≻ ℓ m+1 .
Let recall from ( [START_REF] Lothaire | Combinatorics on words[END_REF] Chapter 5.1) a useful property concerning Lyndon words.

Lemma 3 Let u, v ∈ L. We have uv ∈ L if and only if u ≺ v.

A direct corollary of this lemma is:

Corollary 4 Let u, v ∈ L, with u ≺ v. Then uv n , u n v ∈ L, for all n ≥ 0.
The widely known run-length encoding is used in many applications as a method for compressing data. For instance, the first step in the algorithm used for compressing the data transmitted by Fax machines, consists of a runlength encoding of each line of pixels. It also was used for the enumeration of factors in the Thue-Morse sequence [START_REF] Brlek | Enumeration of factors in the Thue-Morse word[END_REF]. Let Σ = {a, b} be an ordered alphabet. Then every word w ∈ Σ * can be uniquely written as a product of factors as follows:

w = a i 1 b i 2 a i 3 • • • with i 1 ≥ 0 and i k ≥ 1 for k ≥ 2.
The operator giving the size of the blocks appearing in the coding is a function ∆ : Σ * -→ N * , defined by ∆(w) = i 1 , i 2 , i 3 , • • • which is easily extended to infinite words as ∆ : Σ ω -→ N ω .

For instance, let Σ = {1, 3} and w = 13333133111, then

w = 1 1 3 4 1 1 3 2 1 3 , and ∆(w) = [1, 4, 1, 2, 3].
When ∆(w) ⊆ {1, 2, • • • , 9} * , the punctuation and the parentheses are often omitted in order to manipulate the more compact notation ∆(w) = 14123. This example is a special case where the coding integers do not coincide with the alphabet on which is encoded w, so that ∆ can be viewed as a partial function ∆ : {1, 3} * -→ {1, 2, 3, 4} * .

Remark 5 From now on, we only consider 2-letter alphabets Σ = {a, b}, with a < b.

Recall from [START_REF] Brlek | A note on differentiable palindromes[END_REF] that ∆ is not bijective since ∆(w) = ∆(w), but commutes with the reversal ( ), is stable under complementation ( ) and preserves palindromicity. Since ∆ is not bijective, pseudo-inverse functions

∆ -1 a , ∆ -1 b : Σ * -→ Σ *
are defined for 2-letter alphabets by ∆ -1 α (u) = α u [1] α u [2] α u [3] α u [4] • • • , for α ∈ {a, b}.

Note that the pseudo-inverse function ∆ -1 also commutes with the mirror image, that is,

∆ -1 α (w) = ∆ -1 β ( w) (3)
where β = α if |w| odd, and β = α if |w| is even.

The operator ∆ may be iterated, provided the process is stopped when the coding alphabet changes or when the resulting word has length 1.

Example. Let w = 1333111333133311133313133311133313331113331. The successive application of ∆ gives :

∆ 0 (w) = 1333111333133311133313133311133313331113331; ∆ 1 (w) = 1333133311133313331; ∆ 2 (w) = 131333131; ∆ 3 (w) = 1113111; ∆ 4 (w) = 313; ∆ 5 (w) = 111; ∆ 6 (w) = 3.
The operator ∆ extends to infinite words (see [START_REF] Brlek | A note on differentiable palindromes[END_REF]). Define the set of infinite smooth words over Σ = {a, b} by

K Σ = {w ∈ Σ ω | ∀k ∈ N, ∆ k (w) ∈ Σ ω }.
In K Σ the operator ∆ has two fixpoints, namely

∆(K (a,b) ) = K (a,b) , ∆(K (b,a) ) = K (b,a) ,
where K (a,b) is the generalized Kolakoski word [START_REF] Jamet | Discrete surfaces and infinite smooth words[END_REF] over the alphabet {a, b} starting with the letter a.

Example. The Kolakoski word [START_REF] Kolakoski | Self Generating Runs, Problem 5304[END_REF] over Σ = {1, 2} and starting with the letter 2 is K = K (2,1) . We also have

K (2,3) = 2233222333223322333222 • • • , and K (3,1) = 3331113331313331113331 • • • . A bijection Φ : K Σ -→ Σ ω is built by setting Φ(w)[j + 1] = ∆ j (w)[1], for j ≥ 0,
and its inverse is defined as follows. Let u ∈ Σ k , then Φ -1 (u) = w k , where

w n =      u[k], if n = 1; ∆ -1 u[k-n+1] (w n-1 ), if 1 < n ≤ k. Then, for k = ∞, Φ -1 (u) = lim k→∞ w k = lim k→∞ Φ -1 (u[1..k]
). Such a bijection also exists for k-letters alphabet, but an additional parameter is required for recording the letter written, in order to avoid writing 0-blocks.

Remark 6 With respect to the usual topology defined by

d((u n ) n≥0 , (v n ) n≥0 ) := 2 -min{j∈N,u j =v j } ,
the limit exists because each iteration is a prefix of the next one.

Example. For the word w = 1333111333133311133313133311133313331113331 of Example 2, Φ(w) = 1111313.

Note that since Φ is a bijection, the set of infinite smooth words is infinite, and conjugate of the full shift Σ ω (in the terminology of symbolic dynamics).

For later use we borrow from [START_REF] Berthé | Smooth words over arbitrary alphabets[END_REF] the following powerful lemma:

Lemma 7 [Glueing Lemma] Let u, v ∈ ∆ * (Σ).
If there exists an index m such that, for all i, 0 ≤ i ≤ m, the last letter of ∆ i (u) differs from the first letter of ∆ i (v), and

∆ i (u) = 1, ∆ i (v) = 1, then (i) Φ(uv) = Φ(u)[0..m] • Φ • ∆ m+1 (uv); (ii) ∆ i (uv) = ∆ i (u)∆ i (v).
We recall from [START_REF] Paquin | Properties of the extremal infinite smooth words[END_REF] the useful right derivative D r : Σ * → N * such that:

D r (w) =              ε if ∆(w) = α, α < b or w = ε, ∆(w) if ∆(w) = xb, x if ∆(w) = xα, α < b, where α ∈ N. A word w is r-smooth (also said smooth prefix) if ∀k ≥ 0, D k r (w) ∈ Σ * .
In other words, if a word w is r-smooth, then it is a prefix of at least one infinite smooth word (see [START_REF] Brlek | Combinatorial properties of smooth infinite words[END_REF] for more details).

Example. Let w = 112112212. Then, ∆(w) = 212211, ∆ 2 (w) = 1122, ∆ 3 (w) = 22 and D r (w) = 21221, D 2 r (w) = 112, D 3 r (w) = 2.

Computation of extremal smooth words

Let m {a,b} (resp. M {a,b} ) be the minimal (resp. maximal) infinite smooth word over the alphabet Σ = {a, b} w.r.t the lexicographic order. From (1), it easily follows that M {a,b} = m {a,b} , so that the computation of m {a,b} also yields M {a,b} , by simply exchanging the order on the alphabet. The naive algorithm for computing the minimal infinite smooth word over an alphabet Σ consists in computing the minimal smooth prefixes of increasing length. At each step, the minimal letter of the alphabet Σ which makes the word a smooth prefix is added. The smoothness condition is checked with the right derivative operator D r , and ensures that the prefix computed is the prefix of at least one infinite smooth word. If we assume a < b, the corresponding algorithm is:

Algorithm 1 input : Σ = {a,
m {1,2} [1..47] = 11211221211212211211212212112212211211212211211, M {1,2} [1..47] = 21211221211212211211212212112212211211212211211, m {1,3} [1..47] = 11131113131113111313111313111311131311131113131, M {1,3} [1..47] = 33313331313331333131333131333133313133313331313, m {2,4} [1..47] = 22224444222244442244224422224444222244442244224, m {3,5} [1..47] = 33333555553333355533355533333555553333355533355, m {2,3} [1..47] = 22233322233223322233322233223332223322333222333, m {3,4} [1..47] = 33334444333344433344433334444333344433344433334.
With the naive algorithm, the computation of a n-length prefix of m {a,b} takes O(n 2 log(n)) steps: indeed, for every newly added letter to the current prefix of m {a,b} , we have to check smoothness by applying the D r operator. To improve the amount of D r operations, it is convenient to add more than one letter at each step. That was already done for m {1,2} in [START_REF] Paquin | Properties of the extremal infinite smooth words[END_REF] by using the De Bruijn graphs. The same idea can be applied to extremal smooth words for other alphabets, but we shall prove in the next sections that more efficient algorithms exist for computing them.

Extremal smooth words over {1, 2} and {1, 3}

We recall some results established in a previous paper [START_REF] Paquin | Properties of the extremal infinite smooth words[END_REF]. First, extensive computations yield

Φ(m {1,2} ) = 1212212112221121112112221111221211112222 • • • Φ(M {1,2} ) = 2212212112221121112112221111221211112222 • • •
No characaterization is known, so that we do not know whether Φ(m {1,2} ) and Φ(M {1,2} ) are periodic or not. Nevertheless, the minimal smooth word m {1,2} / ∈ L ∞ [START_REF] Paquin | Properties of the extremal infinite smooth words[END_REF].

In [START_REF] Berthé | Smooth words over arbitrary alphabets[END_REF], Berthé et al. showed that the infinite Fibonacci word F , defined as

F = lim n→∞ F n where F 0 = 2, F 1 = 1, and ∀n ≥ 2, F n = F n-1 F n-2 ,
is not smooth over the alphabet Σ = {1, 2}, but smooth over the alphabet Σ = {1, 2, 3}. More precisely, they proved that Φ(F ) = 112(13) ω , the periodicity meaning that ∆ k (F ) = ∆ k+2 (F ) for all k ≥ 3. In [START_REF] Paquin | Properties of the extremal infinite smooth words[END_REF], the link between the Fibonacci word and the minimal infinite smooth word over Σ = {1, 3} is established:

Theorem 8 [[13] Theorem 6] m {1,3} = ∆ 3 (F ).
Since F and m {1,3} are in the same orbit of the ∆ operator, Corollary 9 follows immediately from properties established for the Fibonacci orbit in [START_REF] Berthé | Smooth words over arbitrary alphabets[END_REF].

Corollary 9 [[13] Cor. 8] The extremal infinite smooth words over Σ = {1, 3} satisfy the conditions:

(i) ∆ k (m {1,3} ) = ∆ k+2 (m {1,3}
), for all k ≥ 0;

(ii) Φ(m {1,3} ) = ( 13

u n = u n-1 u n-2 .
Finally, from property (iv) of Corollary 9, the following transducer computing the minimal infinite smooth word m {1,3} in linear time is provided.

I 3 1/3 3/111 1/1 1 11/1 ε/11
Our transducer is a finite state machine using one tape, and two heads used for reading and writing on it. The "next state" function labels the transitions between two states by (u, v): in a given state, the transducer reads u and write v, and moves to the next state.

The next table describes how

• • • • • • • • •
In the next section, we show that for same parity alphabets the situation becomes simpler, a rather surprising fact.

Extremal words over odd alphabets

In this section, we assume that the letters of Σ = {a, b}, are both odd integers and such that a < b. We start by a useful lemma.

Lemma 11 For all u ∈ Σ + , Φ -1 (u) is a palindrome of odd length.

Proof. Let w = Φ -1 (u). We proceed by induction on the length of u.

If n = |u| = 1 then w = β ∈ Σ, which is a palindrome. If n = 2 then u = αβ, with α, β ∈ {a, b}. Then Φ -1 (u) = w = α β is palindromic.
Since a and b are odd, it follows that w has odd length. Assume now that the statement is true for every

u such that |u| ≤ k. Let u ′ ∈ Σ k and w = Φ -1 (u ′ ) is a palindrome of odd length. Let |w| = 2j + 1. We then can write w = w ′ • w[j + 1] • w ′ , w ′ ∈ Σ * and ∆ -1 α (w) = ∆ -1 α (w ′ • w[j + 1] • w ′ ), for α ∈ Σ. There are two cases to consider: if |w ′ | is odd, then ∆ -1 α (w) = ∆ -1 α (w ′ )•∆ -1 α (w[j + 1])•∆ -1 α ( w ′ ) = ∆ -1 α (w ′ )•∆ -1 α (w[j + 1])• ∆ -1 α (w ′ ),
and if |w ′ | is even then

∆ -1 α (w) = ∆ -1 α (w ′ )•∆ -1 α (w[j + 1])•∆ -1 α ( w ′ ) = ∆ -1 α (w ′ )•∆ -1 α (w[j + 1])• ∆ -1 α (w ′ ).
The last equalities hold because of Property (3) of Section 2. In both cases each factor is a palindrome of odd length so that ∆ -1 α (w) is palindromic too. We conclude by using the fact that ∆ -1 α (w) are exactly the words Φ -1 (u) with |u| = k + 1. 2

We state now a fundamental result, showing that for odd alphabets the situation is much simpler than for the alphabet {1, 2}.

Theorem 12 Φ(m {a,b} ) = (ab) ω .

Proof. We proceed by induction on the length of the prefixes of u = Φ(m {a,b} ). Note first that m {a,b} starts with a, the smallest letter. One easily checks that Φ

-1 (ab) = a b ≺ a a b • w = Φ -1 (aax), for any x ∈ Σ, w ∈ Σ * . Assume now that Φ -1 ((ab) k ) is minimal, for every k ≤ n.
               a • •• • • • •• • • • •• • • a b • •• • • • •• • • • • b a • •• • • • a • • • • • • • b • • • • • 2n                a •• • • • •• • • •• • • • • a b •• • • • •• • • •• • b a •• • • • • a • • • • • • • b 1 •• • b a x • • • • •
               a • •• • • • •• • • • •• • • a b • •• • • • •• • • • • b a • •• • • • a • • • • • • • b 1 • •• b a x • • • • • b a b • • • • • • • x 2n -2                b • • • •• • • • •• • • • •• • • • • b a • • • •• • • • •• • • • •• •a b • • • •• • • • • b • • • • • • • a • • • •• • a b 1 • • • b a x • • • • a b a • • • • • • • b x Figure c) Figure d)
By the Glueing Lemma, Φ -1 ((ab) n x) = Φ -1 ((ab) n a)•Φ -1 ((ba) n-1 bx)s, for some s ∈ Σ * . Then, we deduce that the letter x is the one that makes Φ -1 ((ba) n-1 bx) minimal. In Figure d), we consider Φ -1 ((ba) n-1 bx). The letter x is the one that makes Φ -1 ((ab) n-1 x) minimal. By the induction hypothesis, we get Using the equality ∆(m {a,b} ) = ∆(M {a,b} ), we get free the computation of Φ for the maximal word:

x = a. It follows that if Φ -1 ((ab) n ) is minimal, then Φ -1 ((ab) n a) is so. 2n                a • •• • • • •• • • • •• • • • •• • a b • •• • • • •• • • • •• • • b a • •• • • • •• • a • • • • • • • b • •• • • • b a 1 • •• a a y • • • • • b a b • • • • • • • a y 2n                b • • • •• • • • •• • • • •• b a • • • •• • • • •• • • a b • • • •• • b • • • • • • • a 1 • • • a a y • • • • a b a • • • • • • • y
Corollary 13 Φ(M {a,b} ) = b(ba) ω .
The periodicity of Φ(m {a,b} ) yields a linear time algorithm generating the minimal (therefore the maximal) infinite smooth word for odd alphabets:

Corollary 14 Let α ∈ Σ = {a, b}.
The following transducer computes m {a,b} .

a b I ε/a b a/(b b a b ) a-1 2 α/(a b b b ) α-1 2 a b α/(b a a a ) α-1 2 b a
Permuting the letters a and b in the transducer above yields directly the transducer for the maximal smooth word.

Two long standing conjectures of Dekking [START_REF] Dekking | On the structure of self generating sequences, Séminaire de théorie des nombres de Bordeaux[END_REF] concern, on one hand the closure of the set F (K) of factors of the Kolakoski word by reversal and complementation, and on the other hand the recurrence of K. Dekking also showed that closure of F (K) by complementation would imply the recurrence property. These conjectures were stated for every infinite smooth word over {1, 2} in [START_REF] Brlek | Combinatorial properties of smooth infinite words[END_REF]. Although the existence of arbitrarily long palindromes in smooth words on {1, 2} remains an unsolved conjecture, their existence would imply the recurrence property, a fact that was first observed in [START_REF] Brlek | A note on differentiable palindromes[END_REF].

Corollary 9 (iii) implies that F (m {1,3} ) is not closed by complementation. However, for odd alphabets, the peculiar palindromic structure of smooth words (see Lemma 11) is powerful to establish the next result.

Proposition 15 For every infinite smooth word w, the set F (w) is closed under reversal and w is recurrent.

Proof. Let f be a finite factor of w. Then w = uf v for some u, f ∈ Σ * and v ∈ Σ ω . Since every smooth word w has, by Lemma 11, arbitrarily long palindromic prefixes, there exists a palindromic prefix p of w starting with uf , hence containing uf and the result follows.

For the recurrence property one extra step is necessary. Since p contains both f and f , any longer palindromic prefix q contains necessarily the same two occurrences of f and f . As p is both a prefix and a suffix of q, p and consequently f occurs twice in q. 2

Lyndon factorizations

We take now a closer look to the minimal words and start with a negative result.

Lemma 16 If a = 1, then m {a,b} / ∈ L ∞ . Proof. Computing Φ -1 ((ab) 2 ), we get w 1 = b, w 2 = a b , w 3 = (b a a a ) b-1
2 b a and the prefix of m {a,b} : In Lemma 16, we assumed a = 1 to ensure that the word was starting with a b b b . In the case a = 1, the situation is different and we establish that m {1,b} ∈ L ∞ . Before proving this fact, some technical results are required about the prefixes of smooth words. For k ≥ 1 we set

w 4 = Φ -1 ((ab) 2 ) = [(a b b b ) a-1 2 a b (b a a a ) a-1 2 b a ] b-1 2 (a b b b ) a-1 2 a b .
w 2k = Φ -1 ((1b) k ) and w 2k-1 = Φ -1 (b(1b) k ). ( 4
)
Proposition 17 Let Σ = {1, b}. Then the following conditions hold:

(i) w n = (w n-2 • w n-3 ) b-1 2 • w n-2 , for all n ≥ 4; (ii) w 2k w 2k-1 , w 2k w 2k+1 ∈ L, for all k ≥ 1; (iii) w 2k-2 w 2k-1 w 2k and w 2k ∈ Pref(w 2k-2 w 2k-1 ), for all k ≥ 2.
Proof. We proceed by induction. (i) Direct computation yields

w 1 = b, w 2 = 1 b , w 3 = (b1) b-1 2 b and w 4 = (1 b b) b-1 2 1 b . Since w 4 = (1 b • b) b-1 2 • 1 b = (w 2 • w 1 ) b-1 2 • w 2 , the claim is true for n = 4. Assume now that w m = (w m-2 w m-3 ) b-1 2 w m-2
, for all m ≤ n. Then, since the function ∆ -1 distributes nicely because all w i are palindromic of odd length by Lemma 11, we have:

w n+1 = ∆ -1 α (w n ), = ∆ -1 α (w n-2 w n-3 ) b-1 2 w n-2 , = ∆ -1 α (w n-2 w n-3 ) b-1 2 ∆ -1 α (w n-2 ), = ∆ -1 α (w n-2 )∆ -1 α (w n-3 ) b-1 2 ∆ -1 α (w n-2 ), = (w n-1 w n-2 ) b-1 2 w n-1 , with α = b if n even, α = 1 otherwise. (ii) From formulas (4), it follows that w 2 w 1 = 1 b b, w 2 w 3 = 1 b (b1) b-1 2 b ∈ L, so that the claim is true for k = 1. Assume now that w 2k w 2k-1 , w 2k w 2k+1 ∈ L for every k ≤ n. 1. w 2n+2 w 2n+1 = (w 2n w 2n-1 ) b-1 2
• w 2n w 2n+1 , by (i). Then, using the induction hypothesis, w 2n w 2n-1 , w 2n w 2n+1 ∈ L, so that

w 2n+2 w 2n+1 = u b-1 2 v, where u, v ∈ L with u ∈ Pref(v) implies u ≺ v. Now Corollary 4 applies, which concludes. 2. w 2n+2 w 2n+3 = w 2n+2 w 2n+1 • (w 2n w 2n+1 ) b-1
2 , by (i). Then, using (i) and the induction hypothesis, we deduce that w 2n+2 w 2n+1 , w 2n w 2n+1 ∈ L. Then,

w 2n+2 w 2n+3 = uv b-1 2 , where u, v ∈ L, v ∈ Suff(u) implies u ≺ v. Again Corol- lary 4 permits to conclude. (iii) For k = 2, w 2 w 3 = 1 b (b1) b-1 2 b = 1 b b1bs and w 4 = (1 b b) b-1 2 1 b = 1 b b11s ′ , s, s ′ ∈ Σ * .
Thus, the lemma is verified for k = 2. Assume now that it is true for all k ≤ n. Then,

w 2n w 2n+1 = w 2n w 2n-1 (w 2n-2 w 2n-1 ) b-1 2 and w 2n+2 = w 2n (w 2n-1 w 2n ) b-1
2 . Since w 2n-2 w 2n-1 w 2n , the conclusion follows. 2

Example. Let Σ = {1, 5}. Then Φ(m {1,5} ) = ( 15) ω and w 1 = 5, w 2 = 11111, w 3 = 51515. Proposition 17 (i) gives

w 4 = (w 2 w 1 ) 5-1 2 w 2 = w 2 w 1 w 2 w 1 w 2 = 11111511111511111.
Observe that w 2 w 1 = 111115 ∈ L and w 2 w 3 = 1111151515 ∈ L.

Proposition 18 Let Σ = {1, b} and let L n be the Lyndon factorization of w n defined in (4). Then for n ≥ 4:

L n =                       b-1 2 i=1 w n-2 w n-3    • L n-2 , if n even; L n-2 •    b-1 2 i=1 w n-3 w n-2    , if n odd,
where the dots separate the different Lyndon words of the factorization, as described in (2).

Proof. (By induction on n) Direct computations yield

w 1 = b, w 2 = 1 b , w 3 = (b1) b-1 2 b, w 4 = (1 b b) b-1 2 1 b , w 5 = ((b1) b-1 2 b1 b ) b-1 2 (b1) b-1
2 b and the corresponding Lyndon factorizations are:

L 1 = b, L 2 = b i=1 1, L 3 = b b-1 2 i=1 (1b), L 4 = b-1 2 i=1 (1 b b) b i=1 1
and Assume now that the equality holds for every m ≤ n. Using Proposition 17 we have for claims :

L 5 = b b-1 2 i=1 (1b) b-1 2 i=1 1 b (b1) b-1 2 b . As L 4 =    b-1 2 i=1 w 2 w 1    • L 2 and L 5 = L 3 •    b-1 2 i=1 w 2 w 3   , the
(i) if n even: w n+1 = (w n-1 w n-2 )

b-1 2 w n-1 ; since w n-1 w n-2 ∈ L with w n-1 as a proper prefix, we deduce the Lyndon factorization L n+1 .

(ii) if n odd: w n+1 = w n-1 (w n-2 w n-1 ) b-1 2 , and w n-2 w n-1 ∈ L with w n-1 as a proper suffix. It follows that w n-1

w n-2 w n-1 and that the last factor of L n-1 , w n-4 w n-3 , is greater than w n-2 w n-1 , since w n-4 w n-3

w n-2 and w n-2 / ∈ Pref(w n-4 w n-3 ). The conclusion follows. 2

We are now in a position to state the main result about the Lyndon factorization of the minimal infinite smooth word m {1,b} .

Theorem 19 Let Σ = {1, b}. Then :

(i) m {1,b} ∈ L ∞ ;
(ii) the Lyndon factorization of ∆(m {1,b} ) is an infinite sequence of finite Lyndon words.

Proof. It suffices to take the limit as n → ∞ of the statements in Proposition 18. 2

Letter frequencies

The Dekking conjecture about the frequency of 1's in the Kolakoski word still holds, but is solved for the minimal word on Σ = {1, b}.

Theorem 20 Let Σ = {1, b}. Then the frequency of b's in m Σ is

d b (m Σ ) = 1 √ 2b -1 + 1 . (5)
Proof. By Theorem 12 and Proposition 17 i), w 2n is a prefix of m {1,b} for all n ≥ 1 and we have the following recursive definition of m {1,b} :

w 1 = b; w 2 = 1 b ; w 3 = (b1) b-1 2 b; w k = (w k-2 w k-3 ) b-1 2 w k-2 ; m {1,b} = lim n→∞ w 2n .
Putting f n = |w n | b and g n = |w n | 1 , the recursive definition of w n yields the following recursive definitions for the number of occurences f n and g n :

f n = b -1 2 (f n-2 + f n-3 ) + f n-2 = b + 1 2 f n-2 + b -1 2 f n-3 , (6)
with the initial conditions f 1 = 1, f 2 = 0, f 3 = b+1 2 , and

g n = b + 1 2 g n-2 + b -1 2 g n-3 , (7)
with the initial conditions g 1 = 0, g 2 = b and g 3 = b-1 2 . To complete this proof, it suffices to solve the recurrences. Equation ( 6): the characteristic polynomial associated to the recurrence f n is

z 3 - b + 1 2 z - b -1 2 = 0,
which can be written as

(z + 1) z - 1 + √ 2b -1 2 z - 1 - √ 2b -1 2 = 0. It follows that f n = c 1 (-1) n + c 2 ( 1+ √ 2b-1 2 ) n + c 3 ( 1- √ 2b-1 2
) n , with c 1 , c 2 , c 3 ∈ R, except for b = 5 since the roots of the polynomial are -1, -1 and 2 and then, f n = c 1 (-1) n + c 2 n(-1) n + c 3 (2) n . This case will be done later.

Using the initial conditions, we find

c 1 = 2 b -5 , c 2 = b + √ 2b -1 √ 2b -1(1 + b + 2 √ 2b -1) , c 3 = - b -2 + √ 2b -1 √ 2b -1(b -5) .
We then have a closed formula for f n .

Equation [START_REF]Notes on the Kolakoski Sequence[END_REF]: proceeding in the same way, we find for b = 5:

g n = c ′ 1 (-1) n + c ′ 2 1 + √ 2b -1 2 n + c ′ 3 1 - √ 2b -1 2 n , with c ′ 1 = - b + 1 b -5 , c ′ 2 = b √ 2b -1 + 2b -1 √ 2b -1(1 + b + 2 √ 2b -1) , and
c ′ 3 = 2b -1 + √ 2b -1(b -2) √ 2b -1(b -5) .
Now, the frequency of b's is given by lim

n→∞ f 2n f 2n + g 2n = 1 √ 2b -1 + 1 .
For b = 5, using the initial conditions, we find c 1 = -2 9 , c 2 = -1 3 and c 3 = 2 9 , and c

′ 1 = 1 3 , c ′ 2 = 1 and c ′ 3 = 2 3 . Then, lim n→∞ f 2n f 2n + g 2n = 1 4
, which is equal to

1 √ 2•5-1+1 . 2 5

Extremal words over even alphabets

In this section, we assume that the letters of Σ = {a, b} are both even integers and such that a < b. Let start by a useful lemma.

Lemma 21 If w ∈ Σ + then for all α ∈ Σ, |∆ -1 α (w)| has even length.

Proof. Let |w| = n. Applying ∆ -1 α to w yields:

∆ -1 α (w) = ∆ -1 α (w[1]w[2] • • • w[n]) = ∆ -1 α (w[1])∆ -1 α (w[2]) • • • ∆ -1 β (w[n]) = α w[1] α w[2] • • • β w[n] where β = α if n is odd and β = α if n is even. Since |∆ -1 α (w)| = n i=1 w[i] the result follows. 2
As for odd alphabets, any extremal word w over even alphabets is characterized by the periodicity of Φ(w):

Theorem 22 Φ(M {a,b} ) = b ω .
Proof. We proceed by induction on the length of the prefixes of u = Φ(M {a,b} ). First, M {a,b} starts with the prefix b b and Φ(M {a,b} )[1] = b. One easily checks that Φ -1 (bb) Φ -1 (bas) for any s ∈ Σ: indeed, Φ -1 (bb) = b b and Φ -1 (bas) begins with b a a. Assume now that Φ

-1 (b k ) is maximal, for every k ≤ n. Set v = ∆ -1 b (x). It follows that if Φ(M {a,b} )[n + 1] = x then v = ∆ -1 b (x) = b x and consequently v[x + 1] = a. We have the following situation n                b •• • • • •• • • • •• • • • a b •• • • • •• • • • •• a b •• • • • • a • • • • • • • b 1 •• • b a x • • • • • b b b • • • • • • • x
where each prefix is of even length by Lemma 21, and therefore ends with the letter a. Next, using the Glueing Lemma (see Lemma 7), the letter x should be the one that makes the word Φ -1 (b n-1 x) the greatest. By induction hypothesis, it follows that x = b. 2

The equality ∆(m {a,b} ) = ∆(M {a,b} ) yields :

Corollary 23 Φ(m {a,b} ) = ab ω .
Therefore, M {a,b} = ∆(m {a,b} ) and hence is the generalized Kolakoski word K (b,a) . This last property yields a linear time algorithm generating prefixes of the minimal (hence the maximal by simply permuting the letters) infinite smooth word for an even alphabet, represented by the following transducer, where α ∈ {a, b}. This transducer has two cycles (one for each letter) with same base state, and therefore any infinite path runs through these two cycles. Since an equal number of a's and b's are written in each cycle, the frequency of both letters is 1 2 . This again is a surprising fact: for the well-known Kolakoski word K (1,2) it is still a challenging conjecture. Indeed, the best known bound is 0.50084 and is due to Chvátal [START_REF]Notes on the Kolakoski Sequence[END_REF], who designed an ingenious procedure for computing an approximation of the frequency.

The analogue of Lemma 11, showing the palindromic structure of the prefixes of smooth words on odd alphabets, is given now for even alphabets, where prefixes are repetitions.

Lemma 24 For all u ∈ Σ ≥2 , there exists p ∈ Σ 2m such that Φ -1 (u) = p . Then Lemma 11 applies and the conclusion follows. 2

This property may be used to show that extremal words are recurrent by adapting the proof provided in the case of odd alphabets. In fact the recurrence property holds for all infinite smooth words including the generalized Kolakoski words K (b,a) .

Theorem 25 Smooth words are recurrent.

Proof. Let u ∈ Σ ω and w = Φ -1 (u). Let f ∈ F (w). Let n be an index such that p = Φ -1 (u[1..n]) contains f as a factor. Let q = Φ -1 (u[1..(n + 2)]) and set α = u[n + 1] and β = u[n + 2]. By definition

∆ n (q) = ∆ -2 α,u[n] (β) = ∆ -1 u[n] (αα) • x
where ∆ -1 u[n] (αα) ends with the letter u[n] and x ∈ Σ * . Let q ′ be the prefix of q such that ∆ n+1 (q ′ ) = αα. Then w = q ′ w ′ for some word w ′ , and by using the Glueing Lemma, we have for every k such that 0 ≤ k ≤ n

∆ k (w) = ∆ k (q ′ ) • ∆ k (w ′ )
where ∆ k (q ′ ) starts with u[k] and ends with u[k], by using the length parity of Lemma 21. It follows that ∆ k (w ′ ) starts with u[k], and therefore, w ′ contains necessarily another occurrence of p, hence of f . 2

On the other hand, we have: Proposition 26 F (m {a,b} ) and F (M {a,b} ) are not closed under reversal and under complementation. Moreover, the work presented here raises a number of questions. It is quite surprising that for alphabets of same parity, some of the Dekking conjectures are rather easy to prove: recurrence, frequency for extremal words on even alphabets, closure by reversal for odd alphabets. The frequency problem remains open for odd alphabets, as well as all the conjectures for the alphabet {1, 2}, an instance of a different parities alphabet. The results presented here beg for an investigation of smooth words on different parities: study of the extremal words, combinatorial properties, Lyndon factorizations, closure properties, and so on. In another direction it would be interesting to compute the complexity function P (n) in the way Weakley did for the alphabet {1, 2}. The case of larger k-letter alphabets is also challenging.

  ) ω and Φ(M {1,3} ) = 3(31) ω ; (iii) 33 and 31313 ∈ F (m {1,3} ); 11 and 13131 ∈ F (M {1,3} ); (iv) Let m {1,3} = 11u, then ∆(m {1,3} ) = 3u. The close relation between the Fibonacci word and the minimal infinite smooth word also provides a recursive definition for m {1,3} : Proposition 10 [[13] Prop. 9] Let m {1,3} = 11u. Then u is defined as u = lim n→∞ u n where u 0 = 11, u 1 = 13, and ∀n ≥ 2,

  the transducer is used to compute m {1,3} .Read Write Prefix of m {1,3}

  Figure a) shows that since a and b are odd, the prefix defined by the vertical word (ab) n starts and ends with a. The same argument holds for each line, alternating a and b.

  2n

  Figure a) Figure b)

  2n

  Figure e)Figuref)

  Therefore, we can write m {a,b} = a b b b s, with s ∈ Σ ω . A suffix of m {a,b} is a b b a as ′ , with s ′ ∈ Σ ω . Then a b b a as ′ ≺ a b b b s, and hence, m {a,b} / ∈ L ∞ . 2 Example. The word m {3,5} = 3333355555333335553335553333355555 • • • has s = 33333555333 • • • as a smaller suffix, then m {3,5} / ∈ L ∞ .

  Lyndon factorization is verified for n = 4, 5.

  b αα/a α b α ε/a b-1

u[k] 2 .

 2 Proof. Let w = Φ -1 (u). We proceed by induction on the length of u. If |u| = 2, then u = αβ, α, β ∈ Σ and w = α β = (αα) β 2 , thus p = αα. Assume now that the statement holds for every u such that |u| ≤ k. Let v ∈ Σ * be such that|v| = k+1. Then Φ -1 (v) = ∆ -1 v[1] (Φ -1 (v[2..k+1])), and by induction hypothesis, we have for an even length p v =

Proof.

  Consider the prefix p = (b b a b ) b/2 of M {a,b} and assume that its reversal p = (a b b b ) b/2 ∈ F (M {a,b} ). Then, ∆( p) = b b , would be a factor in ∆(M {a,b} ) coding p in M {a,b} . By Lemma 21, any factor a a , a b , b a , b b in ∆(M {a,b} ) codes a factor in M {a,b} starting by b and ending by a. Contradiction. For the non closure under complementation, it suffices to observe that p = p. 2

  Observe that Algorithm 1 does not depend on letter parities. For different alphabets and for MaxLength = 47, we obtain the following words:

b}, MaxLength ; 0 : m {a,b} := a; 1 : loop 2 : if isSmooth (m {a,b} • a) then m {a,b} := m {a,b} • a; 3 : else m {a,b} := m {a,b} • b; 4 : end if; 5 : exit when length(m {a,b} )=MaxLength; 6 : end loop

Acknowledgements. This paper is an extended and enhanced version of a paper presented in Rennes (France) during the 11-th conference JM'06 [12]. We are also grateful to the anonymous referee for his valuable comments that improved paper's readability.

Lyndon factorization

We establish now that minimal smooth words over even alphabets are infinite Lyndon words. Some technical lemmas are required.

Lemma 27 Let w n = Φ -1 (b n ). Then, Proof. We proceed by induction on n. By direct computation, we have

Since aa ≺ bb, aa / ∈ Pref(bb), |aa| and |bb| even, the property is verified for n = 3. Assume now that the statement is true for all k ≤ n. Then,

2 ) b/2 for all n ≥ 3, w n denotes the word (v

Proof. We proceed by induction on n. By direct computation, we get

Assume now the 3 statements true for all k ≤ n.

(ii) By Lemma 27 and i),

∈ Pref(v 1 ) and v 2 ≺ v 1 , we have:

We also have that w n / ∈ Pref(w n ) and their lengths are respectively ab(v 1 + v 2 )/2 and b 2 (v 1 + v 2 )/2, which are even.

(iii) Using i) and ii), we get The frequency of letters in an infinite smooth word over {1, 2} is a still unsolved conjecture. Nevertheless for even alphabets this frequency is 0.5 for the extremal words. For odd alphabets of the type {1, b}, the inductive formulas in Proposition 17 enable us to compute the frequency for extremal words.