IRD Frédéric Giraut
email: fgiraut@wanadoo.fr

Brij Maharaj
email: maharajb@nu.ac.za

Pr Brij Maharaj

Dr François Moriconi-Ebrard

African municipal boundaries delineation process Les confins : du handicap à l'innovation ? "

Keywords: Recompositions territoriales, confronter et innover, Territorial restructurings, comparisons and innovations

l'innovation au coeur ou à la périphérie ?

In a process of territorial restructuring, there are potential disputes, which often reveal both local and national geopolitical challenges and issues. Two related questions concerning provincial and municipal demarcation are frequently at stake, firstly, the issue of the extent of administrative cities' hinterlands in terms of jurisdiction; and secondly the issue of political administrative leadership between cities fitted in a single territorial unit.

After presenting the theoretical hypothesis, this paper will focus on the issue of municipal delineation around secondary cities and small towns in post-apartheid South Africa.

Cities and local government demarcation: three main patterns

The geographical impact of local government restructuring is evident in the "changes effected in terms of relationships between function and area, and changes in the centre-periphery patterns associated with administrative space" (Barlow, 1995:386). Barlow emphasises the difference between functional and spatial change in the process of territorial restructuring: functional change takes the form of transfers between levels of government, between generalpurpose and special-purpose government bodies, or between the public and private sectors; spatial change involves an increase or decrease in territorial fragmentation, boundary 1 Certains éléments de cet article sont issus d'une communication faite en novembre 2001 au symposium de Lusaka "government, governance and urban territories in Southern Africa" et l'essentiel est repris dans un article à paraître dans le Geojournal canadien sous le titre "Contested terrains: Cities and hinterlands in post-apartheid boundary delimitations" qui prend également en compte les réalités métropolitaines à partir du cas de Durban. modifications, or locational changes with regard to administrative centres and service facilities.

There are numerous and significant advantages for a city to remain or to become a provincial or a local capital city. Firstly, there is the allocation of public services, infrastructures and civil servants by the central state. However, with the worldwide decline of the state capacities the significance of this aspect has been reduced [START_REF] Badie | La fin du territoire. Essai sur le désordre international et sur l'utilité sociale du respect[END_REF][START_REF] Burgel | Villes secondaires d'Afrique[END_REF][START_REF] Olowu | Decentralization Policies and Practices under Structural Adjustment and Democratization in Africa[END_REF]. Secondly, the leadership of the capital city can exert its political and economic hegemony over the periphery [START_REF] Gottmann | Center and Periphery, Spatial Variations in Politics[END_REF][START_REF] Reynaud | Société, espace et justice[END_REF]. And thirdly, the capital city has the ability to manage the relationship with international agencies or donors (NGOs, MNCs, International agencies: WB, UNDP, FAO…) as place of mediation within its jurisdiction [START_REF] Giraut | Innovation territoriale et référent identitaire. Du renouveau des provinces nigériennes à celui des "pays" français[END_REF]. This is why the interests of politicians, bureaucrats, business leaders and civic associations often coalesce in order to attract political and administrative functions to their own cities.

On the other hand, there are some disadvantages in centrality, namely the investment which is linked to the obligation to provide and sustain central infrastructures, and the obligation to share resources with the periphery. While the authorities responsible for demarcation would support the need to share resources, this could be rejected by local councils.

Against this background, three main methods of managing the territoriality of cities can be identified:

1) The City/hinterland separation pattern

The legacy of a previous unequal system from medieval or colonial origin can separate the city, formerly ruled by a free "bourgeois" council, and the country, formerly ruled by an aristocratic power [START_REF]The shifting stage of politics : new medieval and postmodern territorialities ?[END_REF][START_REF] Mandani | Citizen and Subject. Contemporary Africa and the Legacy of Late Colonialism[END_REF]. In some federal European systems (Germany, Switzerland) the existence of city-states encapsulated in a large state are examples of the survival of this pattern [START_REF] Coulbois | Aménagement du territoire : une méthode. Les exemples de l'Allemagne[END_REF]Leresche and Joye, 1995;Claval and Sanguin, 1997). At local level the former English boroughs or the renovated but still existing German Stadt Kreise also reflect this pattern [START_REF] Wollmann | Local government systems : from historic divergence towards convergence ? Great Britain, France and Germany as comparative cases in point[END_REF], as do the African urban municipalities surrounded by tribal authorities (Jaglin and Dubresson, 1993).

There has been a revival of this conception of asymmetrical territorial administration with the contemporary worldwide success of administrative metropolitan areas, which is an expression of territorial complexity and possibly post-modernity [START_REF] Barlow | Administrative systems and metropolitan regions[END_REF][START_REF] Moriconi-Ebrard F | De Babylone à Tokyo. Les grandes agglomérations du Monde[END_REF].

In South Africa, for example, there are six main metropolitan areas which have their own local government separated from their regional hinterland.

2) The rationalized territorial administration pattern A "wall to wall" demarcation with a single and centered urban administrative centre per unit.

This pattern was very useful during the period of setting up the territorial administration of the nation states. The French Revolution and the Napoleonian system adopted and promoted it systematically [START_REF]La formation des départements[END_REF]Godlewska and Smith, 1994). However, the success of this model has been extended beyond the French sphere of influence. Numerous post-colonial states have used the pattern in order to control and manage the national territory, for instance Bangladesh in the 1970's and Ghana in the early 1990's (Mawhood, 1993;[START_REF] Razin | The impact of local government organization on development and disparities-a comparative perspective[END_REF].

3) The multi-centred pattern: Sharing centrality A variant of the previous pattern was used frequently by the British imperialists as one form of indirect rule. The practice was that in one territorial unit the administrative functions were distributed amongst several localities in order to avoid centralization at one point. This could be an application of the "divide and rule" principle [START_REF] Spate | Factors in the development of capital cities[END_REF][START_REF] Raffestin | Pour une géographie du pouvoir[END_REF].

The South African background: using the three methods simultaneously

The South African approach to territorial engineering (Christopher, 1994), has simultaneously used the three patterns. More specifically, a heterogeneous demarcation and the city/hinterland differentiation with a segregative goal was used at different scales: white municipality and black township (formerly "location"), and at another level, urban area and homeland (formerly "Native reserve"). At the same time the rational model was used permanently by the Magisterial District which was the spatial tool of state administration. The establishment of the Regional Services Councils towards the end of the apartheid era was a desperate attempt at a regional level to institute rational territorial administration despite the homeland policy [START_REF] Seethal | Restructuring the local state in South Africa : Regional Services Councils and crisis revolution[END_REF]. Historically, sharing the administrative and political functions between cities is illustrated by the existence of double or triple capital cities which started in the middle of the nineteenth century in the Cape Colony. Significantly, as this paper will demonstrate, even in post-apartheid South Africa combinations of the above models have been used in the process of territorial demarcations and socio-spatial restructuring.

In the debate on provincial demarcation, the issue of the choice of provincial capital was at stake and rivalries between cities could occur (Gervais Lambony, 1996 &1998;[START_REF] Muthien | Demarcating the New Provinces: A critical reflection on the process[END_REF]. The issue is still acute, especially in KwaZulu-Natal, between Pietermaritzburg and Ulundi [START_REF] Maharaj | A Tale of Two Capitals: Pietermaritzburg versus Ulundi[END_REF] and in Eastern Cape with the political and economic decline of Umtata, former capital of Transkei [START_REF] Siyongwana | The rise and fall of Umtata[END_REF].

In the municipal demarcation process, the issue of choosing the local headquarters has appeared less problematic, except for some places at district level, than it was for the issue of demarcating the urban areas.

Transitional Local Councils: Urban units between integration and exclusion

In the apartheid era, the dual system of white municipalities and black local authorities (or homelands administration) ignored the functional unity of urban areas (HRC, 1992) Although the duration of the TLC was very short (5 years), it provides a unique opportunity to study the merger of functional cities separated during the apartheid era. The majority of the TLCs were constituted by mergers of former white municipalities and their official black townships. It is useful to discuss some examples of such mergers.

In the Western Cape, the Hermanus TLC consisted of the merging of the original town, several large seaside suburbs and black and coloured townships. The local tourist map continues to ignore the township of Zwelihle despite its location between the old town and the residential suburbs, but the administrative amalgamation was done easily. In the Eastern Cape, the Grahamstown TLC amalgamated the white, coloured and black areas without disputes. In the King William's Town and the East London TLCs there was an amalgamation of the inner cities with the huge black townships and black settlements developed in the former Ciskei (Zwelisha, Bisho, Mdantsane).

If the townships were quite far away from the city, the TLC could be constituted in different blocks. For instance in KwaZulu-Natal, the small industrial town of Estcourt and the township of Wembezi, ten kilometres away on the other side of the N3 highway, were both parts of a non-contiguous TLC.

However, in some cases there was exclusion of some parts of a single morphologically functional urban area. For example, a huge part (Murchinson, Nsimbini tribal authorities) of the Port Shepstone agglomeration (south of KwaZulu-Natal) was excluded from its jurisdiction because of opposition from the traditional authorities and the IFP to amalgamation [START_REF] Guyot | Evolution of political territories and post-apartheid challenges of management of the Port Shepstone area[END_REF][START_REF] Naidoo | Chimera or guiding vision ? : local economic development and the town of Port Shepstone in Kwazulu-Natal[END_REF][START_REF] Harrison | The role of planners and planning in shaping urban space[END_REF]. But an institutional alternative emerged with the establishment of the "Sibambene Development Board", which comprised TLC elected leaders, tribal authorities and community representatives in order to organize service deliveries at the level of the urban area. Similarly, in the North-West province, the Mafikeng-Mmabatho TLC did not include the area historically called "The Stadt" as well as the south-western peripheral settlements because the ruling tribal authority refused to accept local municipal authority in their traditional jurisdiction. [START_REF] Bekker | Local government transition in five eastern seaboard South African towns[END_REF] study of five eastern seaboard towns also illustrates contradictions linked to rural/urban dichotomies in the local restructuring process. The study relates how 17 small nearby villages (the Healdtown complex) were excluded from the TLC of Fort Beaufort at the request of the white ratepayers and voters of the former city council with the help of representatives from the townships. The intention was to demonstrate the "rurality" of these settlements, despite the protestations on the part of the local residents.

In Somerset West and Howick, the previous city councils endeavored to stay independent from the Cape Metropolitan area and from the Pietermaritzburg area, respectively. In both these cases the reason for this was the non-metropolitan character of the periurban locality as claimed by the local leaders. It was successful for the second case (Howick) but not for the first one (Somerset West). Simultaneously as non-metropolitan local councils, Howick and Somerset West tried unsuccessfully to include surrounding farms areas into their jurisdictional zones. In some cases displaced urban areas were excluded from TLCs.

TLCs and Displaced Urban Areas

The issue of the displaced urban areas, which developed due to the homeland policy was still more complex. The distance to the dependant city was often between 20 and 60 kilometres.

With such a distance, the displaced urban area begins to develop a functional autonomy in terms of services, activities and identity (Allanic, 2003, see article in these proceedings; McCarthy and Bernstein, 1996). The borders of these displaced urban areas were also not clear because they were characterised by informal settlements, low densities and mixed rural and urban forms [START_REF] Graaf | The present state of urbanisation in the South African Homelands and some future scenario[END_REF]. Furthermore, some of these displaced urban areas could have been functionally dependent on two formal cities. Thus, the TLC amalgamation ignored almost all the displaced urban areas.

For instance in KZN, eSikhaweni which was located far away from Empangeni and Richard's Bay was not included in either of the two TLCs. Significantly, because of its location, there is now a dispute over the issue of the place of the toll plaza on the road between Richard's Bay and Empangeni. If the toll plaza is located to the east or to the west of the T junction with the road to eSikhaweni, the road link will be free between Richard's Bay and eSikhawini (mainly daily work relationships) or between eSikhawini and Empangeni (mainly weekly shopping relationships). At risk is the cost of transportation for commuters from eSikhawini but also the orientation of the commercial flows from the township to the shops of one or the other city.

Loskop in KwaZulu-Natal is close to the industrial town of Estcourt (20 km by railway and road). Simultaneously Loskop is functionally linked to the rural borough of Bergville (25 km away by railway and road) and the medium sized city of Ladysmith (50 km by road). So due to this typical location the displaced urban area of Loskop did not appear in any TLC.

The much debated issue of local development in Stutterheim, in the Eastern Cape is also an interesting example. It has been evaluated as a success story (Nel, 1994) and as a failure by others [START_REF] Bond | Local economic development and the municipal services crisis in post Apartheid South Africa. The case of Stutterheim[END_REF]. These contradictory evaluations of the process are related to the issue of TLC boundaries. [START_REF] Bond | Local economic development and the municipal services crisis in post Apartheid South Africa. The case of Stutterheim[END_REF] maintains that the local development process in Stutterheim cannot be assessed within the perimeter of the TLC. He argues that despite the alliance between the official townships and the former white municipality, the majority of the Stutterheim functional urban areas do not benefit from local economic development strategies. With a less radical conclusion, [START_REF] Donaldson | Amalgamation of the former homeland border-township of Seshego and the conservative apartheid city Pietersburg during transition[END_REF] makes a similar case for the process of the amalgamation of Pietersburg and Seshego (a township in the former Lebowa homeland now in Limpopo Province) into a single TLC: "In contrast to other former Lebowa homeland towns, Seshego 'benefited' most from the integration process, to the detriment of the traditional rural transition zone adjacent to Seshego" (Donaldson, 2001:213).

The Groblersdal experience is also a very significant case study. This white city is surrounded by large and populous settlements approximately 20 km to the north east and to the south west which were formerly located in two homelands: Lebowa and KwaNdebele. The opposition to the municipal amalgamation came from both the previous white local council and the tribal authorities from the former homelands. The issue was complicated by the provincial demarcation between Mpumalanga and Northern Province. Each stakeholder used the argument of Provincial affiliation in order to oppose the TLC merger. The result was the failure of all attempts to merge the town with the fragmented displaced black urban areas [START_REF] Ramutsindela | Unfrozen Ground: South Africa's Contested Spaces[END_REF].

New Municipal Demarcations and displaced urbanization

The new local government demarcation process has been driven by the "wall to wall" principle in order to form large sized municipalities. So the doctrine of the Municipal Demarcation Act of 1998 is at odds with, and a radical departure from, the Local Government Transitional Act of 1993, which proclaimed the administrative urban/rural dichotomy. A key issue was whether the functional urban units (including those that were displaced) now fitted into a single municipality.

The Demarcation Board in the first phase of the process (1999) identified 11 potential "metropolitan council nodal points", the 6 previous metropolitan council areas and 5 which could be "regarded as aspirant Metropolitan areas": Greater Vereeniging-Kopanong; Greater Pietermaritzburg, Greater East-London; Greater Bloemfontein and Greater Richard's Bay.

They were presented as conurbations including all the high density enumerated areas within the five "aspirant metropolitan areas" are constituted of large conurbations including displaced urban areas.

This was the case for some new municipalities. For example, the new municipality of East London now includes King William's Town with all the townships and the numerous border towns of the former Ciskei, including Bisho the capital city of the Province and former capital of the 'independent homeland'. The Mangaung Municipality (formerly Bloemfontein) includes the displaced urban and industrial areas of Botshabello and Thaba N'chu, the former enclave of Bophutatswana, which are both separate black urban areas 50 km to the east. This was also the case for smaller municipalities such as the new Maluti Phofung within Harrismith which is now amalgamated with Phuthaditjhaba (former QwaQwa Capital), which is located as a "cul de sac" against the Lesotho border with a direct access route to Harrismith.

Groblersdal stands now in a Cross Boundaries Local municipality which includes the small white town, its separated township (Motetema) and the settlements of former Lebowa (Tafelkop) and KwaN'debele (Moutse 3) [START_REF] Ramutsindela | Unfrozen Ground: South Africa's Contested Spaces[END_REF].

However, such mergers have not been the norm in KwaZulu-Natal, due to the municipal autonomy of displaced urban areas or informal peripheral settlement which were ruled by traditional leaders close to the IFP and who were opposed to the amalgamation with adjacent local councils, especially if it was controlled by the African National Congress. The resistance of traditional authorities to the demarcation process is an expression of the political opposition between regionalist and centralist parties with their rural and urban support base in Kwazulu-Natal [START_REF] Crouzel | La chéfferie traditionnelle face à la démocratisation des pouvoirs locaux[END_REF][START_REF] Ramutsindela | Unfrozen Ground: South Africa's Contested Spaces[END_REF]. In fact the political survival of traditional leaders demands a demarcation that does not divide their jurisdictions and which does not include them in an area where traditional authority could be undermined.

The new municipality of Estcourt (Umtshezi Local Municipality, less than 50 000 inhabitants in 1996) is demarcated to the west by the township of Wembesi. All the western populous settlements at the foot of the Drakensberg mountains are functionally linked to the town, including the displaced urban area of Loskop station, are ruled by traditional leaders and they constitute an autonomous municipality (Imbabazane Local Municipality, more than 110 000 inhabitants in 1996). The two municipalities are ruled by the IFP and official physical address of the mayor of the Imbabazane Municipality is Ladysmith! These trends suggest that the rural/urban political opposition is actually quite complex.

Richard's Bay is another example of a very complex situation. The new municipality (uMhlathuze) is the amalgamation of two cities (Richard's Bay and Empangeni) and a displaced township (eSikhaweni) that constitutes the link between the two. The informal townships situated north of Richard's Bay are not included, because of the political issue of traditional areas and also because of the sharing of tax resources from the big companies in the town. This is due to the fact that the Richard's Bay Mineral mining site is located in the neighbouring rural municipality (Mbonambi). More generally, some peripheral industrial, mining or tourist places are thus not included in an urban municipality in order to provide some financial resources for a rural municipality. It is therefore evident that in this new phase of demarcation, the issue of rural/urban dichotomies still feature strongly, despite the fact that the principle of the amalgamation was accepted.

Many farmers' associations made desperate attempts to stay outside the municipal system and were against local government in rural areas. For instance, the Weenen and District Farmers' Association asked for the exclusion of all agricultural areas from the Weenen municipal areas because these farming lots do not receive any services. A key concern was the costs associated with municipal rates. Other farmers mobilized to stay outside the major metropolitan areas and preferred to be included in a simple local municipality. For instance, the United Farmers' Association of Cato Ridge pleaded for recognition of rural reality in terms of activity and type of service delivery. According to the Association "Category A 1 municipal services would be inappropriate and not affordable in these sparsely populated areas where the average annual income includes the poorest of the poor". Also, "urban and peri-urban by-laws are inappropriate in rural areas, and would be almost impossible to administer. e.g. The number of dogs/cattle/chickens etc allowed". The increase in crime contributed to the decline of industrial activity in the region and opportunity for development linked to agriculture and eco-tourism. The Association argued that "by-laws need to be aimed at rural development to facilitate agriculture and eco-tourism and would be complicated by category A municipal by-laws" (Letter from the United Farmers' Association to the Chairman 1 Category A refers to the one tier system of metropolitan municipality, categories B & C refer to the local municipality and district municipality which constitute both a two tier local government system outside the metropolitan areas.

of the Municipal Demarcation Board, 30 September 1999). The entire area was presented as a rural complex, which was polarized in administrative terms by the Magisterial District headquarters of Camperdown far away, but the huge displaced urban area of Mpumalanga in the neighborhood was ignored. The struggle of farmers against metropolitan inclusion was similar to that of the tribal authorities.

So the new local municipalities mainly deal with the geopolitical issue of functional urban areas including or not displaced urban areas and rural periurban areas. The TLCs rather dealt with the geopolitical issue of morphological urban areas in trying to define the city as a whole with its different fragments. In both cases, the issue of competition between cities for political leadership is not crucial because the debates concern a functional area and its hinterland. Nonetheless, it could appear for few cities when they are included in the same local municipality: Richard's Bay and Empangeni (uMhlathuze Municipality); King William's Town and East London (Buffalo City); Welkom & Virginia (Matjhabeng Municipality), Nelspruit & White River (Mbombela Municipality).... But all these cases are in the process of constituting conurbations in the context of metropolization. According to this process, the Municipal demarcation board has created municipalities shaped for including these conurbations and not for including two different cities in a single municipality. So, for these places and few others, the Demarcation Board has planned to transform the actual local municipalities in metropolitan municipalities [START_REF] Sutcliffe | Study on Metropolitan and large Category B Areas[END_REF].

Actually, the study of potential rivalries between separate cities needs to shift to higher levels of local government.

The new district dispensation: looking for a new generation of headquarters?

The study of the new district demarcation and of the determination of their headquarters offers a third scale of analysis. It deals not only with rural/urban relationships but also with city to city relationships as the provincial demarcation process did at upper level.

In the new South African territorial dispensation, the district will be the tier for rural local development and the urban headquarter will certainly be the place of mediation and exchanges between local communities and external partnership (State services, NGO's, international agencies, international municipal cooperation...), a new perspective with new resources for some small or medium size towns. The potentially conflicting issue of the

  . The Transitional Local Council (TLC) experiment was an attempt to merge the different parts of the fragmented functional cities. For instance in KZN, TLCs were constituted by the merging of urban spaces established in terms of four different statutes: a) Local Authority Ordinance: the former white cities; b) Section 30: areas of ownership authorized for black people e.g. Inanda or Clermont in the Durban area; c) Section 33: municipal townships with Black local authority; d) Regulation 293: townships of the homeland of KwaZulu, which could be contiguous (e.g. Kwamashu or Umlazi in the Durban area) or quite distant (e.g. Esikhaweni in the Richard's Bay and Empangeni area).

  choice of the new districts headquarters has been avoided by the Demarcation board and the official final choice or non choice depends now on the new councils. The list of the places where the Demarcation board held its first meetings in each new district (in order to present the Municipal GIS SA Explorer in April 2001) give already an unofficial idea of the location of the headquarters. Some surprises occur. The main one is certainly the promotion of several former homeland capital cities without urban history. They supplant a range of old magisterial district headquarters. For instance, Thohoyandou lead the Vhembe District in front of Louis Trichard, Giyani lead the Mopani District in front of Tzaneen and Phutaditjhaba lead the Thabo Mofutsanyane District in front of Harrismith and Bethlehem. In KwaZulu-Natal, Ulundi lead the widest district including the far away city of Vryheid and a part of the coal mine fields. Some new disputes between cities of different generations are surely on the way; they would reveal now the rule of some general process and the dynamic of a post apartheid political geography.

Annex

Maps from the Municipal Demarcation Board: local municipalities with former TCLs perimeters.

1) Mangaung (Bloemfontein), FS 172 2) Umtshezi (Estcourt-Wembezi, Weenen), KZ 234 3) Greater Groblersdal, CBLC 4 4) Buffalo City (King William's Town-East London), EC 125 5) Mafikeng, NW 383 6) uMhlatuze (Richard's Bay-Empangeni), KZ 282 7) Amahlati (Stutterheim, Keikammahoek), EC 124


Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Costas Iliopoulos

Marcin Kubica
email: [kubica@mimuw.edu.pl

Jakub Radoszewski

Wojciech Rytter
email: rytter@mimuw.edu.pl

Tomasz Waleń
email: walen]@mimuw.edu.pl

Extracting Powers and Periods in a String from its Runs Structure

. In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem.

Introduction

The structure of all runs in a string provides succinct and very useful information about periodic properties of the string. Several basic applications of this structure were given in [START_REF] Kolpakov | On maximal repetitions in words[END_REF]. We present some other algorithmic applications of runs and simplify already known algorithms.

First we consider the problem of computing all distinct kth powers in a string of length n, for a given k. It is a known fact that the number of distinct squares (k = 2) does not exceed 2n [START_REF] Fraenkel | How many squares can a string contain?[END_REF][START_REF] Ilie | A simple proof that a word of length n has at most 2n distinct squares[END_REF][START_REF] Ilie | A note on the number of squares in a word[END_REF] and for cubes (k = 3) there is a 0.8n bound [START_REF] Kubica | On the maximal number of cubic subwords in a string[END_REF], which implies same bound for any value k ≥ 4. Gusfield & Stoye [START_REF] Gusfield | Linear time algorithms for finding and representing all the tandem repeats in a string[END_REF] present an O(n) time algorithm for computing all the distinct squares. Unfortunately, this algorithm is complicated and uses suffix trees which are a rather heavyweight data structure and add a logarithmic factor depending on the size of alphabet in most implementations. We present a much simpler O(n) time algorithm which computes all distinct kth powers in a string of length n using suffix arrays instead of suffix trees.

Another application of the runs structure is the computation of local periods which are related to the critical factorizations of a string [START_REF] Crochemore | Jewels of Stringology[END_REF]. The known O(n) time algorithm by Duval et al. [START_REF] Duval | Linear-time computation of local periods[END_REF] employs several different techniques modified in a non-trivial way. We present an equally efficient but simpler algorithm using the solution of the Manhattan Skyline Problem.

Finally, we consider factor-primitivity queries, which consist in checking, for any factor of a given word, whether it is primitive and what is its primitive root. This problem has potential applications in data compression, in particular, in run-length encoding and its derivatives. We provide a solution to this problem with O(n log ǫ n) preprocessing time, for any ǫ > 0, and O(log n) query time.

Preliminaries

Let u be a word of length n, u = u [1 . . n], over a bounded alphabet Σ. We say that an integer p is the (shortest) A run v (a maximal repetition) in the word u is an interval [i . . j] such that the shortest period p = per(v) of the associated factor u[i . . j] satisfies 2p ≤ ji + 1, and the interval cannot be extended to the left nor to the right without violating the above property, that is,

period of u[1 . . n] (notation: p = per(u)) if p is the smallest positive integer such that u[i] = u[i + p] holds for all 1 ≤ i ≤ n -p.
u[i -1] = u[i + p -1] and u[j -p + 1] = u[j + 1]
, provided that the respective letters exist. Denote by R(u) the set of all runs in u, each represented as a triple (i, j, p). It is known that |R(u)| = O(n) [START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF] and all elements of R(u) can be computed in O(n) time [START_REF] Kolpakov | On maximal repetitions in words[END_REF] (a more practical algorithm for computing all runs is given in [START_REF] Chen | Fast and practical algorithms for computing all the runs in a string[END_REF]).

If w k = u (k is a positive integer) then we say that u is the kth power of the word w. A square (cube) is the 2nd (3rd) power of a nonempty word. The primitive root of a word u, denoted root(u), is the shortest word w such that w k = u for some positive integer k. We call a word u primitive if root(u) = u, otherwise it is called non-primitive.

Let us recall two useful data structures in string processing.

Suffix Arrays. The suffix array of the word u consists in three tables: SUF, LCP and RANK. The SUF array stores the list of positions in u sorted according to the increasing lexicographic order of suffixes starting at these positions, i.e.:

u[SUF[1] . . n] < u[SUF[2] . . n] < . . . < u[SUF[n] . . n].
Thus, indices of SUF are ranks of the respective suffixes in the increasing lexicographic order. The LCP array is also indexed by the ranks of the suffixes, and stores the lengths of the longest common prefixes of consecutive suffixes in SUF. Denote by lcp(i, j) the length of the longest common prefix between u[i . . n] and u[j . . n] (for 1 ≤ i, j ≤ n). Then, we set LCP[1] = -1 and, for 1 < r ≤ n, we have:

LCP[r] = lcp(SUF[r -1], SUF[r]).
Finally the RANK table is an inverse of the SUF array:

SUF[RANK[i]] = i for i = 1, 2, . . . , n.
All tables comprising the suffix array can be constructed in O(n) time [START_REF] Crochemore | Algorithms on Strings[END_REF].

Range Minimum Queries. Define the range minimum query data structure (RMQ, in short) as follows. Assume that we are given an array A[1 .

. n] of integers. This array is preprocessed to answer the following form of queries: for an interval [a . . b] (for 1 ≤ a ≤ b ≤ n), find the minimum value

A[k] for a ≤ k ≤ b.
The best known RMQ data structures have O(n) preprocessing time and O(1) query time, using only O(n) bits of space [START_REF] Fischer | A new succinct representation of RMQ-information and improvements in the enhanced suffix array[END_REF][START_REF] Sadakane | Succinct data structures for flexible text retrieval systems[END_REF]. The RMQ data structure on the LCP array enables the computation of longest common extensions, i.e., longest common prefixes between any two suffixes of a string in O(1) time, with O(n) time preprocessing.

Lyndon Representations of Runs

Let u be a word of length n. By rot(u, c) let us denote a cyclic rotation of the word u obtained by moving (c mod n) first letters of u to its end. We say that the words u and rot(u, c) are cyclically equivalent. A word that is both primitive and lexicographically minimal in the class of its cyclic rotations is called a Lyndon word. We define the Lyndon root of a word u, lroot(u), as the (only) Lyndon word cyclically equivalent to root(u). We define the Lyndon root of a run v = (i, j, p) in u, lroot(v), as lroot(u[i . . i + p -1]), note that this notion is slightly different from the corresponding notion for words.

Denote by u (a) a prefix of the word u of length a and by u (a) a suffix of u of length a. Each run v can be uniquely represented (Lyndon representation) in the following form:

v . = λ (a) • λ m • λ (b) (1)
where λ = lroot(v) and 0 ≤ a, b < per(v), see Fig. 2. We say that v is a λ-run.

We will divide all runs of R(u) into maximal groups of λ-runs.

λ = lroot(v) λ λ λ (b) λ (a) m occurrences suf (v) Fig. 2. A graphical view of the Lyndon representation of a run v = λ (a) • λ m • λ (b)
For a run v = (i, j, p), define suf (v), suf (v) ≥ i, as the smallest index for which:

u[suf (v) . . suf (v) + p -1] = lroot(v),
see Fig. Proof. We start the proof of the theorem with the following claim. is at least per(v 1 ). Recall that longest common prefixes of arbitrary suffixes can be computed using RMQ on the LCP array, which proves the first part.

Claim 2 The equality of Lyndon roots of runs (represented as pairs of the form

(per(v), rank (v))) in u can be tested in O(1) time with O(n) preprocessing time. Moreover, if L = v 1 , v 2 , . . . ,
As for the second part of the claim, assume that for three runs v 1 , v 2 and v 3 we have per(

v 1 ) = per(v 2 ) = per(v 3 ) = p, rank (v 1 ) < rank (v 2 ) < rank (v 3 ) and lroot(v 1 ) = lroot(v 3 ). Then lcp(suf (v 1 ), suf (v 3 )) ≥ p,
however due to the rank inequalities we have

lcp(suf (v 1 ), suf (v 3 )) = min(lcp(suf (v 1 ), suf (v 2 )), lcp(suf (v 2 ), suf (v 3 ))). Therefore lcp(suf (v 1 ), suf (v 2 )) ≥ p and consequently lroot(v 1 ) = lroot(v 2 ) = lroot(v 3 ). ⊓ ⊔ Using Claim 2,
v ⊜ (i, j, p, a, m, b, ℓ) (2)
where ℓ is the length of v and a, m, b are defined as in the (ordinary) Lyndon representation [START_REF] Chazelle | A functional approach to data structures and its use in multidimensional searching[END_REF]. Due to the following lemma, the compact Lyndon representations of runs can be computed efficiently: Proof. For a run v = (i, j, p) of length ℓ = ji + 1, knowing the value of suf (v) the compact Lyndon representation of v can be computed using the following additional formulas:

a = suf (v) -i, m = ⌊(ℓ -a)/p⌋ , b = ℓ -a -mp.
Hence, the statement is a consequence of Lemma 1. ⊓ ⊔

Inferring Powers from Runs

Denote by #powers(u, k) the total number of distinct kth powers in a string u.

In this section we present an algorithm for efficiently computing this function as well as reporting the corresponding powers. By reporting we mean returning the vector POWERS such that, for each i, POWERS [i] is the set of periods of all kth powers which have the last occurrence starting at position i. These sets have cardinality at most two [START_REF] Fraenkel | How many squares can a string contain?[END_REF][START_REF] Ilie | A simple proof that a word of length n has at most 2n distinct squares[END_REF][START_REF] Ilie | A note on the number of squares in a word[END_REF]. Each kth power w k (for k ≥ 2) occurring in u corresponds to a run v containing this occurrence for which per(v) = |root(w)|, we say that w k is induced by the run. If lroot(w) = λ then we call w k λ-compatible. Note that two runs may induce the same power only if their Lyndon roots are equal.

For a λ-run v define maxpower(v) as the maximal natural β such that some cyclic rotation of λ kβ is induced by v.

Observation 4 If v is a run of length ℓ with period p then maxpower(v) = ⌊ℓ/(kp)⌋.

The following lemma shows a correspondence between Lyndon representation of a run and the set of induced distinct kth powers. Theorem 2. For a given word u of length n, the value #powers(u, k) can be computed and all distinct kth powers in u can be reported in O(n) time.

Proof. The value #powers(u, k) can be computed using the formulas from Lemma 6, assuming that we have the decomposition of R(u) from Theorem 1 and the compact Lyndon representations of all runs, which are necessary to compute the values of β(λ) and I(v) (see the formulas in Lemma 5). The only difficulty is to find the size of the union of the sets I(v) for a given group of λ-runs R y in O(|R y |) time. Note that this can be performed in a simple way if the sets to be unionned form a list of intervals sorted in non-decreasing order (intervals treated as pairs). Due to Lemma 5, each set I(v) can be divided into a constant number of intervals. Finally, all intervals across all the groups R y can be sorted using radix sort in O(n) time.

The algorithm reporting all powers is a natural extension of the algorithm computing #powers(u, k) using the exact formulas from Lemma 5, we omit the technical description of the algorithm in this version of the paper.

⊓ ⊔

Denote by #occ-powers(u, k) the total number of occurrences of kth powers in a string u. We end this section presenting a formula for #occ-powers(u, k) which can be evaluated in a straightforward manner to obtain an O(n) time algorithm, where n = |u|. Note that the value of the formula can be Θ(n 2 ).

Theorem 3.

#occ-powers(u, k) = (i,j,p)∈R(u) c(i, j, p) • (j -i + 2 -kp/2) -c(i, j, p) 2 • kp/2 where c(i, j, p) = j -i + 2 kp . ( 3
)
The proof of the theorem will be included in the full version of the paper.

Computation of Local Periods

By P = {p 1 , p 2 , . . . , p n-1 } we denote the set of inter-positions that are located between pairs of consecutive letters of u[1 .

. n]. We say that a square ww is centered at inter-position p i of u if both of the following conditions hold, for x = u[1 .

. i] and y = u[i + 1 .

. n]:

w is a suffix of x or x is a suffix of w w is a prefix of y or y is a prefix of w.

We define the local period at inter-position p i (notation: localper[i]) as |w|, where ww is the shortest square centered at this inter-position, see also Fig Fig. 4. A Fibonacci string with local periods at all its inter-positions. Local period at inter-position p9 of the string is 3, since the smallest period q of a run which completely covers the factor of the string corresponding to the interval [9 -q + 1 . . 9 + q] equals 3

Case A: |w| ≤ min(|x|, |y|), i.e., ww is an internal square of u. Case C: max(|x|, |y|) < |w|, i.e., ww is a both-sides-external square.

We handle Cases A-C separately. In Case A we use the structure of runs in u and perform a reduction to the Manhattan Skyline Problem. In Cases B and C we use the border array from the Morris-Pratt algorithm, which is a simple alternative to a modified Boyer-Moore shift function used for this purpose in [START_REF] Duval | Linear-time computation of local periods[END_REF].

Case A: internal local periods. The problem of the internal local periods can be reduced in O(n) time to the (restricted min-version) of the following problem:

Restricted Manhattan Skyline Problem Input: given a set S of O(n) subintervals of [1 . . n -1] with natural heights of size O(n); Output: the table f [t] = min{height([i . . j]) : t ∈ [i . . j], [i . . j] ∈ S}, t ∈ [1 . . n-1].
Indeed, note that any internal local period corresponds to a primitively rooted square in u, induced by one of the runs of u, see also Fig. 4. Each run v = (a, b, q) in u induces such squares with root q at inter-positions p a+q-1 , p a+q , . . . , p b-q . Thus for each inter-position p i we need to find the shortest period of a run (i.e., height of an interval from the Manhattan Skyline Problem) inducing a square at this inter-position.

The following two lemmas show how to utilize the described reduction to construct a linear time algorithm for computing internal local periods.

{ list-all-elements([i . . j] \ X); X ← X ∪ [i . . j]; } (4)
can be implemented in O(m) time.

Proof. The implementation uses a restricted version of the find/union data structure, in which we are allowed to union only adjacent subintervals. Thus the structure of union operations forms a static tree (here it is a path graph) and therefore O(m) find/union operations can be performed in O(m) time [START_REF] Gabow | A linear-time algorithm for a special case of disjoint set union[END_REF]. In the algorithm the universe [1 . . m + 1] (extended to the right by a sentinel) is partitioned into maximal segments of elements of X followed by a single element which is not in X: all elements in such a segment form a single find/union component which stores the index of its rightmost position. The operations (4) are implemented by traversing the components intersecting the interval [i . . j], reporting their rightmost elements and unionning them one by one.

⊓ ⊔ Lemma 8. The internal local periods can be computed in linear time.

Proof. We showed that the problem can be reduced to the restricted Manhattan Skyline Problem. This problem can be solved in O(n) time as follows.

Sort intervals from S according to their heights (in increasing order); Initialize X = ∅; for each interval [i . . j] ∈ S (in the sorted order) do for each t ∈ list-all-elements([i .

. j] \ X) do f [t] ← height([i . . j]); X ← X ∪ [i . . j];
According to Lemma 7, the set operations in the above pseudocode can be implemented in linear time. This completes the proof.

⊓ ⊔

Case B: one-side-external local periods. Recall that a word that is both a prefix and a suffix of a word u is called a border of the word u; a border of u is called proper if it is shorter than u. Denote by border[i], for i = 1, 2, . . . , n, the length of the longest proper border of u[1 . . i]. Recall that the border array can be computed in O(n) time, as in the Morris-Pratt algorithm [START_REF] Crochemore | Jewels of Stringology[END_REF].

The following lemma shows how the border array can be used to compute left-external local periods, the case of right-external local periods is symmetric and can be treated similarly by considering the reversed word u. The proof of the lemma will be present in the full version of the paper. . i], i.e., the longest suffix of the former word which is also a prefix of the latter word, then localper[i] = nb, see Fig. 5. Note that b is the length of the longest border of u which is not longer than min(i, ni). Recall that the lengths of all proper borders of u are iterations of the form border (j) [n]. This concludes an O(n) time algorithm which updates the localper array obtained after the previous cases considering all both-sides-external local periods, filling the array from its middle to its sides.

Combining the solutions to Cases A-C, we obtain the following result. 6 Factor-Primitivity Queries For a given string u of length n, we define a factor-primitivity query as follows: for the indices a, b, 1 ≤ a ≤ b < n, check whether the factor u[a . . b] is primitive, and if not, find the length of its primitive root. Let us introduce a notion relating runs with factor-primitivity queries. We say that a run (i, j, p) completely covers an occurrence of a factor u[a . . b] in u if i ≤ a, b ≤ j. Proof. Assume first that q def = |root(w)| < |w|. Then also per(w) = q, see [START_REF] Crochemore | Jewels of Stringology[END_REF]. Hence, w is completely covered by a run with period q and, obviously, by no run with period smaller than q.

On the other hand, if |root(w)| = |w| then any run completely covering w and having period p satisfies p = |w| or p ∤ |w|. This concludes the proof.

⊓ ⊔

The conclusion of Lemma 10 can again be interpreted using the notion of Manhattan skyline, see Fig. 6.

i j

Fig. 6. The buildings in the skyline correspond to runs in a string u and their heights correspond to their periods. When checking primitivity of a factor w = u[i . . j] we look for the lowest building such that w is completely "under its roof"

In our algorithm we utilize yet another interpretation of the problem. To each run (i, j, p) in a word u (|u| = n) we assign a point (i, j) in the 2-dimensional plane, and define the value of this point as f ((i, j))

b a a b a b a a b a b bFig. 1 .

 1 Fig.1. The structure of runs in the word baababaababb. The word contains 3 runs with period 1, 2 runs with period 2, 1 run with period 3 and 1 run with period 5

2 .Lemma 1 .Theorem 1 .

 211 This parameter, together with the period per(v), provides a unique characterization of the Lyndon root of the run. Additionally define rank (v) = RANK[suf (v)]. The values of suf (v) and rank (v) for any run v in a word u of length n can be computed in O(1) time assuming O(n) time preprocessing. Proof. Let v = (i, j, p). The value of rank(v) can be computed using RMQ on the interval I = [i . . i + p -1] of the table RANK. Indeed, the prefixes of length p of the suffixes {u[d . . n] : d ∈ I} are exactly all cyclic rotations of lroot(v). Recall that RMQ for an array of length n can be implemented with O(n) preprocessing time and O(1) query time. Finally, suf (v) = SUF[rank (v)]. ⊓ ⊔ The set R(u) of all runs within u can be decomposed into pairwise disjoint classes R 1 , R 2 , . . . , R t corresponding to runs with equal Lyndon roots in O(n) time, where n = |u|.

  the requested decomposition of R(u) can be obtained in O(n) time in the following three steps, recall that |R(u)| = O(n).1. Compute the values of suf (v) and rank (v) for all runs in R(u) -O(n) time in total due to Lemma 1. 2. Represent all runs v in u as pairs (per(v), rank(v)), sort all such pairs lexicographically -O(n) time using radix sort. 3. Group runs with equal Lyndon roots -due to Claim 2 the groups consist in consecutive runs in the sorted order of pairs, and equality of Lyndon roots of runs can be tested in O(1) time with O(n) time preprocessing, what gives O(n) time complexity of this step. ⊓ ⊔ Define the compact Lyndon representation of a run v = (i, j, p) as a tuple:

Lemma 3 .

 3 The compact Lyndon representation of runs (represented as (i, j, p)) in a word u of length n can be computed in O(1) time with O(n) time preprocessing.

Lemma 5 .Lemma 6 .Fig. 3 .

 563 Fig. 3. The run λ (2) λ 4 λ (2) with the Lyndon root λ = abbcccc induces all possible distinct squares cyclically equivalent to λ 2 and 5 squares cyclically equivalent to λ 4 , that is, maxpower(v) = 2 and I(v) = [0 . . 2] ∪ [5 . . 6]

  . 4. Clearly, for any p i there are three possible cases: a b a a b a b a a b a a b a b a a b a b a

  Case B: min(|x|, |y|) < |w| ≤ max(|x|, |y|), i.e., ww is a left-external square (if |w| > |x|) or a right-external square (if |w| > |y|).

Lemma 7 .

 7 Assume initially X = ∅ and all considered intervals [i . . j] are from the universe [1 . . m]. Then the sequence of O(m) pairs of operations:

Lemma 9 .

 9 (a) If the local period at inter-position p i is left-external (and not right external) then there exists j > i such that border[j] = i and localper[i] = ji. (b) If border[j] = i for any j = 2, 3, . . . , n and i > 0 then localper[i] ≤ ji. Due to Lemma 9, the localper array can be updated in O(n) time by considering all left-external local periods corresponding to the values border[j] for all j = 1, 2, . . . , n. Case C: both-sides-external local periods. Consider a both-sides-external local period at inter-position p i of u. If b is the longest overlap between u[i+1 . . n] and u[1 .

Fig. 5 .

 5 Fig. 5. The correspondence between both-sides-external local periods and borders

Theorem 4 .

 4 All local periods of a string u of length n can be computed in O(n) time (in a simple way) using the runs structure of u and the border array.

Lemma 10 .

 10 Let p be the minimum period of a run completely covering an occurrence of a factor w in a string u (or p = ∞ if no such run exists). If p < |w| and p | |w| then |root(w)| = p; otherwise w is primitive.

  def = p. Denote the set of all such points by V . By Lemma 10, to find the primitive root of any factor u[a . . b] of u, it suffices to compute the value min{f((i, j)) : 1 ≤ i ≤ a, b ≤ j ≤ n, (i, j) ∈ V }.This is exactly a 2D range search for minimum query, which can be answered in the RAM model in: O(log 1+ǫ m) query time with O(m) preprocessing time, O(log m log log m) query time with O(m log log m) preprocessing time, or O(log m) query time with O(m log ǫ m) preprocessing time, where m = |V | = |R(u)| and ǫ is an arbitrary positive real [1]. Thus we obtain the next result.

  The Lyndon roots of two runs v 1 and v 2 are equal if and only if per(v 1 ) = per(v 2 ) and the longest common prefix of suffixes at positions suf (v 1 ) and suf (v 2 )

v a is a list of all runs in u with period p sorted in ascending order of the values of parameter rank , then all runs in u with the same Lyndon root λ, |λ| = p, form a sublist of L composed of a number of consecutive elements.

Proof.

Theorem 5. For a given string u of length n, using the runs structure of u we can answer factor-primitivity queries in O(n log ǫ n) preprocessing time, for any ǫ > 0, and O(log n) query time.


Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

German Tischler
email: german.tischler@kcl.ac.uk

Gapped Suffix Arrays: a New Index Structure for Fast Approximate Matching

Approximate searching using an index is an important application in many fields. In this paper we introduce a new data structure called the gapped suffix array for approximate searching in the Hamming distance model. Building on the well known filtration approach for approximate searching, the use of the gapped suffix array can improve search speed by avoiding the merging of position lists.

Introduction

Pattern matching in textual data is a much studied question in Computer Science and large parts of books on algorithms on strings and sequences are devoted to the question (see e.g. [START_REF] Crochemore | Algorithms on Strings[END_REF]). Several types of applications require approximate matching rather than exact matching of the patterns. This is typically the situation for motif search and inference in biological molecular sequences because they allow some diversity without altering the basic information they carry. But this is not by far the only domain demanding approximate matching solutions. A main technique to deal with the question is the notion of alignment, which admits a considerable number of variants and is parameterised by the costs of allowed elementary operations (see e.g. [START_REF] Böckenhauer | Algorithmic Aspects of Bioinformatics[END_REF]).

However there are actually two sub-problems depending on which are known first, patterns to be searched for or data to be searched. They admit totally different types of solutions. The paradigm solution for searching for approximate occurrences of a fixed pattern under the notion of Levenshtein operations is due to Landau and Vishkin [START_REF] Landau | Fast string matching with k differences[END_REF], and the same authors designed a simpler version when only mismatches are considered [START_REF] Landau | Efficient string matching with k mismatches[END_REF]. The second type of solution appears when the data is to be searched for multiple patterns. It is then appropriate to index the data for accelerating their future inspection and analysis.

Indexing for approximate searches is the problem we address in the article, but with one important restriction: patterns are of fixed size. Moreover the proposed solution accommodates only few mismatches to be feasible with reasonable resources.

In this paper we introduce what we call the gapped Suffix Array. It is a data structure enhancing the standard suffix array and tailored to accept searches for patterns up to some mismatches.

Let throughout this paper Σ be a finite ordered alphabet and let Σ * denote the set of all finite strings over Σ. We denote the empty string by ǫ and the length of a string u by |u|. Let y = y[0] . . . y[n -1] denote a string of finite length n over Σ which we call the text. We denote the factor starting at position i and ending at position j of some string x by x[i . . j]. It is defined by x[i . . j] = x[max(0, i)]x[max(0, i)+1] . . . x[min(j, |x|-1)] for max(0, i) ≤ min(j, |x|-1) and x[i . . j] = ǫ otherwise. A prefix of a string x is x[0 . . i] for any position i and a suffix of x is x[i . . |x| -1] for any position i. A string u ∈ Σ * is lexicographically smaller than a string v ∈ Σ * (which we denote by u < v), if u = v and either

u = ǫ or u = ǫ = v and u[0] < v[0] or u = ǫ = v and u[0] = u[0] and u[1 . . |u| -1] < v[1 . . |v| -1]
. The array SA of length n is defined by SA[r] being the start position of the r'th lexicographically smallest non empty suffix of y, i.e. we obtain the relation

y[SA[0] . . n -1] < y[SA[1] . . n -1] < . . . < y[SA[n -1] . . n -1] .
The array SA can be computed from the string y in linear time if |Σ| ∈ O(n c ) for some constant c (in particular for c = 0, i.e. alphabets of constant size, cf. [START_REF] Crochemore | Algorithms on Strings[END_REF]). Let the array ISA be defined by ISA[SA[r]] = r for 0 ≤ r < n. The length of the longest common prefix of u, v ∈ Σ * , which we denote by is lcp(u, v), is the largest l ≤ max(|u|, |v|) such that u[0 . . l -1] = v[0 . . l -1]. We denote the length of the longest common prefix of the two suffixes starting at position i and j of y by lcp y (i, j) and we define lcp r (r, q) = lcp y (SA[r], SA[q]) for 0 ≤ r, q < n. We define the LCP array by LCP[r] = lcp r (r -1, r) for 1 ≤ r < n and by LCP[0] = 0. It is well known that the identity lcp r (r, q) = min{LCP[r + 1], LCP[r + 2], . . . , LCP[q]} holds for 0 ≤ r < q < n. The LCP array can be computed from the string y and the array SA in linear time (cf. [START_REF] Crochemore | Algorithms on Strings[END_REF]). The pair of arrays (SA, LCP) is commonly known as the suffix array of the string y.

For two strings u, v such that |u| = |v| = m the Hamming distance d(u, v) of u and v is defined as the number of differences between u and v. For sake of completeness we define d(u, v) = ∞ for strings u, v such that |u| = |v|.

Approximate String Matching

We consider approximate string matching by the well known procedure called filtration or partitioning into exact matches (cf. [START_REF] Navarro | Indexing methods for approximate string matching[END_REF][START_REF] Navarro | A guided tour to approximate string matching[END_REF]). Let x ∈ Σ * be a pattern of length m. We want to find occurrences of x in the text y with up to k mismatches under the Hamming distance. Partitioning into exact matches works as follows. We partition x into q > k fragments x 0 , . . . x q-1 ∈ Σ + . We search the lists occurrences X i of x i . For each of the possibilities of choosing qk of the q fragments, we merge the respective lists of positions using the respective position offsets. This provides us with q q-k candidate position lists. The union X of these merged lists is a superset of the positions of occurrences of x in y with up to k mismatches. We obtain the list of occurrences of x in y by filtering X using an online algorithm for testing if the candidate positions designate occurrences with at most k mismatches.

As an example consider a pattern x we partition into three fragments x 0 , x 1 and x 2 for searching its occurrences with 1 mismatch. We have to consider three pairs of fragments: (x 0 , x 1 ), (x 1 , x 2 ) and (x 0 , x 2 ). The first two combinations are easily found using an index for y. We need only search for the patterns x 0 x 1 and x 1 x 2 . The third requires merging of lists in the conventional scheme. If we have an index supporting searching patterns with gaps however, merging is no longer necessary. Supporting the search of patterns with gaps is the purpose of the gapped suffix array. [START_REF] Grossi | High-order entropy-compressed text indexes[END_REF] The Gapped Suffix Array

Definitions

We define a generalisation of the notion of lexicographical order which we call (g 0 , g 1 )-lexicographical order, where g 0 , g

1 ∈ N. A string u ∈ Σ * is (g 0 , g 1 )- lexicographically smaller than a string v ∈ Σ * -if u[0 . . g 0 -1] = v[0 . . g 0 -1] then iff u < v -otherwise (u[0 . . g 0 -1] = v[0 . . g 0 -1]), if min(|u|, |v|) > g 0 + g 1 then iff u[0 . . g 0 -1]u[g 0 + g 1 . . |u| -1] < v[0 . . g 0 -1]v[g 0 + g 1 . . |v| -1] -otherwise (u[0 . . g 0 -1] = v[0 . . g 0 -1], min(|u|, |v|) ≤ g 0 + g 1 ), iff |u| < |v|
Informally the definition means that we compare u and v ignoring the presence of the letters in the position interval [g 0 , g 0 + g1), where we have to take some care about those strings which end inside the gap area. The (g 0 , g 1 )-lexicographical order is a total order on a set of strings such that each string has a different length. We define the (g 0 , g 1 )-gapped suffix array of y, which we denote by (g 0 , g 1 ) -gSA (or shorter gSA, if the parameters g 0 and g 1 are clear from the context), as the array containing the starting positions of the non-empty suffixes of y in (g 0 , g 1 )-lexicographically ascending order. The (g 0 , g 1 )-prefix of the string u ∈ Σ * , which we denote by D(g 0 , g 1 , u), is defined as u[0 . . g 0 -1] if |u| ≤ g 0 +g 1 and as u[0 . . g 0 -1]u[g 0 + g 1 . . |u| -1] if |u| > g 0 + g 1 . We define the (g 0 , g 1 )-gLCP array (we use the shorter notation gLCP, if the parameters g 0 and g 1 are clear from the context) for the string y based on its (g 0 , g 1 )-gSA array by

gLCP[r] = lcp(D(g 0 , g 1 , y[gSA[r -1] . . n -1]), D(g 0 , g 1 , y[gSA[r] . . n -1]))
for r > 0 and gLCP[r] = 0 for r = 0.

Searching using the gapped suffix array

Assume we are given a query x of length m > g 0 + g 1 and we want to find all occurrences of patterns in x[0 . . g 0 -1]Σ g1 x[g 0 + g 1 . . m -1] in a text y using the array (g 0 , g 1 )-gSA for y. The search method we use is analogous to the one we would use for searching an ungapped pattern using the array SA. The only major difference is that we suitably substitute the lexicographic order by the (g 0 , g 1 )-lexicographic order in the binary search for the interval of gapped suffix matching x. Thus the time required to report the occ gapped occurrences of x in y is O((mg 1 ) log n + occ) if we do not use an adjoint (g 0 , g 1 )-gLCP array and O((mg 1 ) + log n) if we do.

Computing the gapped suffix array

For the rest of the section assume we have fixed two natural numbers g 0 and g 1 and want to compute the arrays (g 0 , g 1 )-gSA (short gSA) and (g 0 , g 1 )-gLCP (short gLCP). We now show how to deduce the sorting in gSA in linear time O(n) from the suffix array of y.

Let GRANK[r] be defined as the number of ranks r ′ < r such that LCP[r] < g 0 . GRANK contains the ranks of factors of y with length up to g 0 . The largest number we can find in GRANK is n.

If GRANK[ISA[i]] < GRANK[ISA[j]
] for two positions i, j, then the suffix at position i is lexicographically and (g 0 , g 1 )lexicographically smaller than the one at position j. Thus the order of the suffixes between SA and gSA can only differ if GRANK[r] = GRANK[q] for two ranks r and q. If GRANK[r] = GRANK[q], then we can determine the order of the respective gapped suffixes in gSA by checking

ISA[SA[r] + g 0 + g 1 ] and ISA[SA[q] + g 0 + g 1 ],
given that these two are defined. A problem occurs for such ranks r where SA[r]+g 0 +g 1 ≥ n because the obtained value is not a valid position on y and thus ISA is not defined for it. According to the definition of the (g 0 , g 1 )-lexicographic order, this problem can be solved by sorting along the array HRANK given by

HRANK[r] = ISA[SA[r] + g 0 + g 1 ] + g 0 + g 1 if SA[r] + g0 + g1 < n n -1 -SA[r] otherwise
The range of numbers found in the array HRANK is [0, n+g 0 +g 1 -1], in particular the upper bound is O(n). We can compute a representation of the array gSA by sorting the sequence of ranks 0, . . . , n -1 by the pair (GRANK[r], HRANK[r]). This can be performed efficiently in linear time using a two stage radix sort, where we first sort by HRANK and then by GRANK. The concrete array gSA can then be obtained from this intermediate representation by mapping each rank on the suffix array to the respective position.

Theorem 1. Given a string y of length n and its suffix sorting SA, the gapped suffix array (g 0 , g 1 )-gSA of y can be computed in linear time O(n).

Computing the gapped LCP array gLCP

We show how to compute the gapped LCP array gLCP from the suffix array and the array (g 0 , g 1 ) -gSA (short gSA) in linear time. We require a constant time solution of the range minimum query (RMQ) problem after linear time preprocessing (see e.g. [START_REF] Fischer | A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array[END_REF]). We can obtain the array (g 0 , g 1 )-gLCP (short gLCP) by setting

gLCP[r] =                LCP[r] if LCP[r] < g 0 g 0 if max(gSA[r] + g 0 + g 1 , gSA[r -1] + g 0 + g 1 ) ≥ n g 0 + l otherwise, where l = min(LCP[p] + 1, . . . , LCP[q]) for p ′ = ISA[gSA[r -1] + g 0 + g 1 ] q ′ = ISA[gSA[r] + g 0 + g 1 ] p = min(p ′ , q ′ ) and q = max(p ′ , q ′ )
As every single step in the computation takes constant time and we have n steps, the runtime for computing gLCP is O(n).

Theorem 2. Given a string y of length n and its suffix sorting SA, the gapped LCP array (g 0 , g 1 )-gLCP of y can be computed in linear time O(n).

Representing the array gSA in reduced space

The uncompressed version of the gSA array requires n⌈log n⌉ bits. The text however can be stored in n⌈log |Σ|⌉ bits. In applications the size of the alphabet is fixed an small. Thus the space taken by the gSA will often be much larger than the space required for the text. The array SA is compressible (cf. [START_REF] Grossi | Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching[END_REF]). Unfortunately, methods for compressing SA cannot be applied for compressing the array gSA, as the compression of SA requires the sorting of the suffixes according to the lexicographical order, which in general is not the same as the (g 0 , g 1 )-lexicographical order. We provide a simple method for storing the array gSA using less than n log n bits space on average. Decoding the compressed representation of gSA will require the array SA. We limit our description to the aspects necessary for searching using the array gSA, i.e. our description allows accessing values in gSA corresponding to a provided query string. The more general case of accessing gSA for a given rank r without knowing a corresponding string can be facilitated using some additional succinct data structures. We omit the description for lack of space. We assume that the query string has a length of at least g 0 . For shorter strings searching on the suffix array is sufficient. This may enumerate occurrences in a different order. However, this is not critical in most applications.

Let R

[r] = {r ′ |HRANK[r ′ ] = r}. Each R[r]
is given as an interval of ranks. Observe that the sequences found in SA and gSA in each such interval are permutations of each other. On average we can expect each interval to have a size of n |Σ| g 0 . Thus the permutation transforming gSA into SA can be stored using ⌈log |R[r]|⌉ bits per number for each interval r. Each interval R[r] is assigned to a unique prefix u(r) ∈ Σ * of length at most g 0 . The left bound low(r) and right bound up(r) of the interval R[r] can be obtained by searching u(r) on the suffix array. Knowing low(r) and up(r) we can compute the number of bits b(r) = ⌈log up(r)low(r) + 1⌉ used to store the numbers in the interval. Let L be defined by L(r) = b(R -1 [r]). L can be stored and indexed for rank queries via a wavelet tree (cf. [START_REF] Grossi | High-order entropy-compressed text indexes[END_REF]) using n⌈log⌈log n⌉⌉ + o(n log log n) bits. Let C[r] denote the permutation mapping the portion R[r] of gSA to SA and let C i denote the concatenation of all C[r] such that b(r) = i. We can obtain gSA[r] for the query v as C b(u -1 (v[0..g0-1])) [rank b(u -1 (v[0..g0-1])) (r)] in time O(log log n). The size of the data structure on average is n(log ng 0 log |Σ|) + n log log n + o(n log log n) bits. Using a space efficient wavelet tree data structure, the size is dominated by the first two terms in practice.

Conclusion

In this paper we have presented the gapped suffix array as a new efficient data structure for approximate matching under the Hamming distance. We obtained the same query time as for the conventional suffix array. The gapped suffix array can be derived in linear time from a text and its suffix sorting. Open problems include an improved query time independent of the text size, a succinct representation in n log Σ + o(n log Σ) space and whether the gLCP array can be computed in linear time without using RMQ queries.


Golnaz Badkobeh
email: golnaz.badkobeh@kcl.ac.uk

Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Finite-Repetition threshold for infinite ternary words

Keywords: combinatorics on words, repetition, repeat, word powers, word exponent, repetition threshold, pattern avoidability, word morphisms. MSC: 68R15 Combinatorics on words

The exponent of a word is the ratio of its length over its smallest period. The repetitive threshold r(a) of an a-letter alphabet is the smallest rational number for which there exists an infinite word whose finite factors have exponent at most r(a). This notion was introduced in 1972 by Dejean who gave the exact values of r(a) for every alphabet size a as it has been eventually proved in 2009.

The finite-repetition threshold for an a-letter alphabet refines the above notion. It is the smallest rational number FRt(a) for which there exists an infinite word whose finite factors have exponent at most FRt(a) and that contains a finite number of factors with exponent r(a). It is known from Shallit (2008) that FRt(2) = 7/3.

With each finite-repetition threshold is associated the smallest number of r(a)-exponent factors that can be found in the corresponding infinite word. It has been proved by Badkobeh and Crochemore (2010) that this number is 12 for infinite binary words whose maximal exponent is 7/3.

We show that FRt(3) = r(3) = 7/4 and that the bound is achieved with an infinite word containing only two 7/4-exponent words, the smallest number.

Based on deep experiments we conjecture that FRt(4) = r(4) = 7/5. The question remains open for alphabets with more than four letters.

Introduction

The article deals with repetitions in strings and their avoidability. The question is grounded on the notion of the exponent of a word: it is the ratio of its length over its smallest period. A word of exponent e is also called an e-power.

An infinite word is said to avoid e-powers or to be e-power free if the exponents of its finite factors are smaller than e.

The repetitive threshold r(a) of an a-letter alphabet is the smallest rational number for which there exists an infinite word whose finite factors have exponent at most r(a). The word is said to be r(a) +power free. It is known from Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF] that r(2) = 2. Indeed, the notion was introduced in 1972 by Dejean [START_REF] Franc ¸oise Dejean | Sur un Théorème de Thue[END_REF] who proved that r(3) = 7/4 and gave the exact values of r(a) for every alphabet size a > 3. Her conjecture was eventually proved in 2009 after partial proofs given by several authors (see [START_REF] Rao | Last cases of Dejean's conjecture[END_REF][START_REF] James | A proof of Dejean's conjecture[END_REF] and references therein).

A generalised version of the repetitive threshold is by Ilie et al. [START_REF] Ilie | A generalization of repetition threshold[END_REF]. The authors introduce the notion of (β , p)-freeness: a word is (β , p)-free if it contains no factor that is a (β ′ , p ′ )-repetition (i.e. a word of period p ′ and exponent β ′ ) for β ′ ≥ β and p ′ ≥ p; it is (β + , p)-free if β ′ > β instead. Their generalized repetition threshold R(a, p) defined for an a-letter alphabet as the real number α for which either (a) there exists an (α + , p)-free infinite word and all (α, p)-free words are finite, (b) or there exists an (α, p)-free infinite word and for all ε > 0, (α -ε, p)-free words are finite.

where p is the minimum avoided period. The proof of boundary of this threshold for all alphabet sizes is presented in [START_REF] Ilie | A generalization of repetition threshold[END_REF], and R(k, 1) is essentially Dejean's repetition threshold.

For infinite words whose maximal exponent of factors is bounded, it is legitimate to ask whether they can contain only a finite number of r(a)-powers. This is an extra constraint on the word. When such words exist, it is as legitimate to exhibit the minimal number of r(a)-powers they can contain, which adds another measure of the word complexity. The first result of this type is by Fraenkel and Simpson [START_REF] Aviezri | How Many Squares Must a Binary Sequence Contain?[END_REF] for the binary alphabet. They showed that an infinite binary word can contain only 3 squares, not less. Two simple proofs of the result are by Harju and Nowotka [START_REF] Harju | Binary Words with Few Squares[END_REF] and the present authors [START_REF] Badkobeh | An infinite binary word containing only three distinct squares Submitted[END_REF].

The above consideration leads to the notion of finite-repetition threshold associated with an a-letter alphabet. It is the smallest rational number, noted FRt(a), for which there exists an infinite word whose finite factors have exponent at most FRt(a) and that contains a finite number of r(a)-powers. It is known from Shallit [START_REF] Shallit | Simultaneous avoidance of large squares and fractional powers in infinite binary words[END_REF] that FRt(2) = 7/3 (see also [START_REF] Rampersad | Avoiding large squares in infinite binary words[END_REF]). The present authors [START_REF] Badkobeh | Fewest repetitions in infinite binary words[END_REF] proved that the associated minimal number of squares is 12 if the infinite word contains two 7/3-powers. Badkobeh [START_REF] Badkobeh | Fewest repetitions vs maximal-exponent powers in infinite binary words[END_REF] even refined the results by showing the number is 8 if the infinite word admits two 5/2-powers, extending the result of Fraenkel and Simpson [START_REF] Aviezri | How Many Squares Must a Binary Sequence Contain?[END_REF] recalled above for which it is 3 if two cubes are allowed.

In this article, we consider the finite-repetition threshold of the ternary alphabet. We show that FRt(3) = r(3) = 7/4. We provide a direct proof of the result and another proof based on a previous result on word morphisms by Ochem [START_REF] Ochem | A generator of morphisms for infinite words[END_REF].

The experiments reported in the conclusion show that the finite-repetition threshold of the 4-letter alphabet FRt( 4) is likely to be r(4) = 7/5, which we conjecture. The hypothetical property FRt(a) = r(a) (for a > 2) would be equivalent to say that infinite words whose maximal exponent of factors is Dejean's repetition threshold can be constrained to containing a finite number of factors with that exponent.

Repetitions in ternary words

Let A be a finite alphabet. A word w in A * of length |w| = n is a sequence of letters w[0]w [START_REF] Badkobeh | Fewest repetitions vs maximal-exponent powers in infinite binary words[END_REF]

. . . w[n - 1] also noted w[0 . . n -1].
The period of w is the smallest positive integer period(w) = p for which w[i] = w[i + p] whenever both sides of the equality are defined. The exponent of w is the rational ratio |w|/period(w). Thus, the exponent of a word is a rational number that is at least 1. For example, a square is a nonempty word with an even integer exponent and 1020102 of exponent 7/4 can be written (1020) 7/4 . A word of exponent e is also called an e-power.

An infinite word is a function from the natural number to the alphabet A. An infinite word is said to avoid e-powers (resp. e + -powers) if the exponents of its finite factors are smaller than e (resp. not more than e). In this case we also say that the word is e-power free (resp. e + -power free).

The repetitive threshold r(a) of an a-letter alphabet is the smallest rational number for which there exists an infinite word whose finite factors have exponent at most r(a). The word is then r(a) + -power free.

The finite-repetition threshold for the alphabet of a letters is defined as the smallest rational number FRt(a) for which there exists an infinite word that both avoids FRt(a) + -powers and contains a finite number of r-powers, where r is Dejean's repetitive threshold.

The above notion is inspired by the following results of Karhumäki and Shallit. [START_REF] Shallit | Simultaneous avoidance of large squares and fractional powers in infinite binary words[END_REF] Theorem 1 (Karhumäki and Shallit [START_REF] Karhumäki | Polynomial versus exponential growth in repetition-free binary words[END_REF]) For all t ≥ 1, there are no infinite binary words that simultaneously avoid all squares yy with |y| ≥ t and 7/3-powers.

Theorem 2 (Shallit [13])

There is an infinite binary word that simultaneously avoids all squares yy with |y| ≥ 7 and 7/3 + -powers.

When an infinite binary word avoids 7/3 + -powers and contains a finite number of squares it is natural to ask more on these few squares. The previous theorem shows that their period can be bounded by 7. The next result goes slightly beyond by showing that their number is at least 12. But the two properties cannot be satisfied simultaneously.

Theorem 3 (Crochemore and Badkobeh [START_REF] Badkobeh | Fewest repetitions in infinite binary words[END_REF]) The smallest number of squares occurring in a 7/3-power free infinite binary word is 12.

Showing that no infinite word satisfying the conditions can contain less squares is done by mere computation. The second part is done by producing an infinite word satisfying the condition and containing exactly 12 squares. Following Shallit's hierarchy of infinite binary words in [START_REF] Shallit | Simultaneous avoidance of large squares and fractional powers in infinite binary words[END_REF], the previous result was refined by Badkobeh [START_REF] Badkobeh | Fewest repetitions vs maximal-exponent powers in infinite binary words[END_REF] The main result of the present article is the following theorem.

Theorem 4

The finite-repetition threshold of the 3-letter alphabet is its Dejean's repetition threshold, that is, 7/4. The smallest number of 7/4-powers occurring in a 7/4 + -power free infinite ternary word is 2.

On the alphabet {0, 1, 2}, the two unavoidable 7/4-powers occurring in the word below are, up to a permutation of letters, (0121) 7/4 = 0121012 and (2010) 7/4 = 2010201.

Computation shows that the longest ternary words with only one 7/4-power are 102 letters long. However we may think of having a larger threshold as in the binary case. But even if we increase the threshold to e < 2, the maximal length of words stays at 102 with only one e-power.

If we relax further the maximal exponent condition, it can be shown that there exists an infinite ternary word in which occur only one square, namely 00 up to a permutation of letters, and no e-power with 7/4 ≤ e < 2.

Since the repetition threshold for a 3-letter alphabet is 7/4, to prove this ratio is also its finiterepetition threshold it is sufficient to show (contrary to the binary case) that there exists a 7/4 + -free infinite ternary word with finitely many 7/4-powers. To do it, we use the fact that the repetition threshold of 4-letter alphabets is 7/5 and provide a translation morphism from 4 letters to 3 letters with suitable conditions.

Finite-Repetition threshold for infinite ternary words

We consider the morphism g from {a, b, c, d} * to {0, 1, 2} * defined by:

                                       g(a) = 0102101202102010210121020120210120102120121020120210121 0212010210121020102120121020120210121020102101202102012 10212010210121020120210120102120121020102101210212, g(b) = 0102101202102010210121020120210120102120121020120210121 0201021012021020121021201021012102010212012102012021012 10212010210121020120210120102120121020102101210212, g(c) = 0102101202102010210121020120210120102120121020102101202 1020121021201021012102010212012102012021012102010210120 21020102120121020120210120102120121020102101210212, g(d) = 0102101202102010210121020120210120102120121020102101202 1020102120121020120210121020102101202102012102120102101 21020102120121020120210120102120121020102101210212.
The morphism is uniform with codeword length 160. Another presentation of the morphism g is:

       g(a) = uv02120121020120210121020102101202102012102120102101yz, g(b) = uv21021201021012102010212012102012021012102010210120yz, g(c) = uw01021012021020121021201021012102010212012102012021xz, g(d) = uw12010210121020102120121020120210121020102101202102xz,
where u, v, w, x, y and z are:

u = 01021012021020102101210201202101201021201210201, v = 2021012102, w = 0210120210201, x = 2102010212, y = 0121021201021, z = 0121020120210120102120121020102101210212.
The word u is the longest common prefix of the codewords, |u| = 47, and z is their longest common suffix, |z| = 40. Theorem 4 is a direct consequence of the next proposition.

Proposition 1

The morphism g translates any infinite 7/5 + -free word on the alphabet {a, b, c, d} into a 7/4 + -free ternary word containing only two 7/4-powers, the fewest possible.

We present two proofs of Proposition 1. The first one is a direct proof that involves the longest common prefix and the longest common suffix of the codewords to derive a contradiction from the existence of any 7/4-power other than 0121012 and 2010201 in the image by g of a 7/5 + -free word. The second proof is derived from a lemma on morphisms stated by Ochem in [START_REF] Ochem | A generator of morphisms for infinite words[END_REF].

Direct proof of Proposition 1

Let us assume that g(s) contains a non-extensible repetition, excluding the two 7/4-powers 0121012 and 2010201, with exponent at least 7/4. The repetition can be written pq where |p| is its period. Then |pq|/|p| ≥ 7/4. A simple computation verifies that no image of a 7/5 + -free word with length at most 3 contains the repetition. Therefore the repetition is long and occurs in the image by g of a word of length at least 4.

We consider two cases.

• Case |p| ≤ |q|. The word pq is of the form

pq = u 1 • • • v 1 u 1 • • • v 1 • • •
where u 1 v 1 is codeword. Indeed it starts with the square pp of the form

u 1 g(s ′ )v 1 u 1 g(s ′ )v 1
where s ′ ∈ {a, b, c, d} * . Note that s ′ cannot be the empty word because pq would occur in the image of a triplet. Let α ∈ {a, b, c, d} be such that g(α) = v 1 u 1 . Therefore s ′ αs ′ is a factor of s. The letter occurring before s ′ in s and the letter occurring after it must differ from α to avoid the squares αs ′ αs ′ or s ′ αs ′ α since s is 7/5 + -power free). Then u 1 is not longer than the longest common prefix between two different codewords, that is,

|u 1 | ≤ |uw| = 60. Symmetrically, v 1 is not longer than the longest common suffix of two different codewords, that is, |v 1 | ≤ |yz| = 53. But then |v 1 u 1 | ≤ 113
and cannot be a complete codeword, a contradiction.

• Case |p| > |q|. The word pq is of the form

pq = u 1 • • • v 1 • • • u 1 • • • v 1
More precisely a 0 pqb 1 is of the form where g(s ′′ ) = v 1 q -1 pu 1 because the morphism is synchronizing (no codeword occurs in the concatenation of two codewords). Therefore g(s ′ )g(s ′′ )g(s ′ ) is a factor of g(s) thus s ′ s ′′ s ′ is a factor of s and since s is 7/5

a 0 u 1 g(s ′ )v 1 a 1 • • • b 0 u 1 g(s ′ )v 1 b 1 where s ′ ∈ {a, b, c, d} * , a 0 , a 1 , b 0 , b 1 ∈ {0, 1,
(s ′ )| ≤ 2|g(s ′′ )| (1)
because the morphism g is uniform.

Furthermore pq = u 1 g(s ′ )g(s ′′ )g(s ′ )v 1 and p = u 1 g(s ′ )g(s ′′ )u 1 -1 so its exponent satisfies

|u 1 g(s ′ )g(s ′′ )g(s ′ )v 1 | |g(s ′ )g(s ′′ )| ≥ 7 4
which rewrites as

|g(s ′ )| + 4|u 1 v 1 | ≥ 3|g(s ′′ )| (2)
Using Equations 1 and 2 we get

9|g(s ′ )| ≤ 6|g(s ′′ )| ≤ 2(|g(s ′ )| + 4|u 1 v 1 |)
and then

|g(s ′ )| ≤ 8 7 |u 1 v 1 |.
But since |u 1 v 1 | ≤ 113 as in the first case, this implies that s ′ is empty. Therefore the repetition pq is a factor of the image of a triplet, a contradiction.

This completes the direct proof of Proposition 1.

Proof based on Ochem's result

Here we split the proof in two parts: first we show that g(s) is 7/4 + -free, second we show the only 7/4-powers are the ones mentioned above. The proof depends on the following result. In the statement, Σ s (resp. Σ e ) is an alphabet with s (resp. e) letters; and the morphism h :

Σ * s → Σ * e is synchronizing if for any a, b, c ∈ Σ s and v, w ∈ Σ * e , h(ab) = vh(c)w implies either v = ε and a = c or w = ε and b = c. Lemma 1 (Ochem [10]) Let α, β ∈ Q, 1 < α < β < 2, and p ∈ N * . Let h : Σ * s → Σ *
e be a synchronizing q-uniform morphism (with q ≥ 1). If h(w) is (β + , p)-free for every α + -free word w such that |w| < max{ 2β

β -α , 2(q-1)(2β -1)

q(β -1)
}, then h(t) is (β + , p)-free for every (finite or infinite) α + -free word t.

To apply the lemma to the morphism g above, we have α = 7/5 and q = 160. We choose β = 17/10 and p = 5. Then we can show that the morphism is (17/10 + , 5)-free if g(w) is (17/10 + , 5)-power free for all words w for which |w| < max{ 2β βα , 2(q -1)(2β -1) q(β -1) }, which implies |w| < 12. This set is finite and a simple computation can verify the claim. Since every (7/4 + , 5)-power is also a (17/10 + , 5)-power then we can claim the morphism is (7/4 + , 5)power free.

So the only possible 7/4-powers with period less that 5 are: (0121) 7/4 , (0212) 7/4 , (1020) 7/4 , (1202) 7/4 , (2010) 7/4 , and (2101) 7/4 . Any of those strings must be either a factor of a codeword or a factor of the image of a doublet. We immediately conclude the words (1020) 7/4 and (2101) 7/4 are the only factors of g(s).

This concludes the whole proof of Theorem 4.

Repetitions for larger alphabets

Experiments show that a word on a 4-letter alphabet for which the maximal exponent of factors is 7/5 and that contains at most one 7/5-power has maximal length 230. However if the constraint on the number of 7/5-powers is relaxed to 2 the length grows to at least 100000. This experiment intrigued us to study the string further and to state the following conjecture.

Conjecture 1

The finite-repetition threshold of 4-letter alphabets is 7/5 and their exist an infinite 7/5 +power free word containing only two 7/5-powers. The two 7/5-powers are (0231203213) Note the above words have period 10, the smallest possible period, since there is no 7/5-power with period 5 that is 7/5 + -free.

The experiments are done with a mere backtracking technique to generate the suitable words. It implements efficient algorithms for testing the properties.

  2} and a 0 = b 0 and a 1 = b 1 , because pq is inextensible. It rewrites as a 0 u 1 g(s ′ )g(s ′′ )g(s ′ )v 1 b 1

7 5 and (1230213203) 7 5

 77 up to a permutation of the letters.

  according to the next table.

	Maximal Allowed number Smallest number
	exponent e	of e-powers	of squares
	7/3	2	12
		1	14
	5/2	2	8
		1	11
	3	2	3
		1	4

Acknowledgments

We warmly thank Pascal Ochem for pointing his powerful result on word morphisms and for profitable discussions.