Souheïl Hanoune
email: souheil.hanoune@ensea.fr

Mathias Quoy
email: quoy@ensea.fr

Philippe Gaussier
email: gaussier@ensea.fr

An architecture for online chunk learning and planning in complex navigation and manipulation tasks

When a robot is brought into a new environment, it has a very limited knowledge of what surrounds it and what it can do.

Either to navigate in the world, or to interact with humans, the robot must be able to learn complex states, using input information from sensors. For navigation task, visual information are commonly used for localisation. Other signals are usually employed: ultrasounds, lasers and path integration are as many data that can be taken into account. For human-robot interactions the proprioceptive information, like the values of the articulations and the grip state, are additional degrees in the system that can to be enrolled in the analysis. All those signals have different dynamics, and the system must manage all those differences. To do so, a solution is to introduce different learning levels. An architecture able to create complex multimodal contexts, to recognise them and to use them afterwords in higher level strategies would give the capacity to resolve such situations.

In this paper, a model has been introduced for complex categorisation problems, patterning and chunk learning. It is used in a complex architecture to create multimodal states for a cognitive map and to resolve ambiguities. Tests were performed in both a simulated navigation task and in a complex arm manipulation and localisation experiment.

I. INTRODUCTION

Autonomous robots have to learn more and more complex categories, either autonomously or with the help of a caregiver. To do so, the robot must be able to recognise new situations, categorise them in order to use them. Commonly, simple associations between input signals are used, which can include ambiguities in the categorisation. Visuo-motor associative learning and a motor controller can provide the basis to let low level immediate imitation emerge as a result of simple mechanisms [START_REF] Andry | Proprioception and imitation: on the road to agent individuation[END_REF]. The system learns the body configuration using visuo-motor associations, and due to a perception ambiguity, caused by limited visual capabilities, the robot can confuse the hand of the teacher with its own.

In a navigation task [START_REF] Hirel | Biologically inspired neural networks for spatio-temporal planning in robotic navigation tasks[END_REF], the authors used a cognitive map strategy for navigation [START_REF] Cuperlier | Neurobiologically inspired mobile robot navigation and planning[END_REF]. The goals were associated with a transition, according to colored place cell. The color and the place cell are nearly correlated, but this correlation is not interpreted in the system.

Transition categories were obtained by combining the two last events received. The time difference estimated in this case is only based on the last event, and every new reception erases the old one [START_REF] Hirel | Codage hippocampique par transitions spatio-temporelles pour l'apprentissageautonome de comportements dans des tâches de navigation sensori-motrice et de planification en robotique[END_REF]. In this situation, a temporal relation between two event, strongly correlated, but separated in time by another one is not possible. Until now, the signals given to the system were always relevant: visual information, color detection, sound in navigation, proprioceptive information and the grip of the hand in the case of an arm manipulation task. However, if we want to trend to a generic architecture, the large number of signals does not guarantee their pertinence for the event. In such case, using a model able to detect correlations, between signals globally close in time, is necessary.

A solution is to introduce different levels of learning. An architecture able to create complex multimodal contexts, recognise them and use them afterwords in higher level conditioning would give the capacity to resolve such situations.

The aim of this paper is to present a bio-inspired model for generic patterning and chunk learning. The article exposes some preliminary works using the model.

We tested our architecture in two learning tasks. First, a navigation simulation task, exposing the ability of the system to capture correlations between signals close in time even if they are separated by another one. The second one is a robotic experiment, including navigation and arm manipulation. In this experiment, the architecture is used for contexts categorisation. In a human-robot interaction task, the multimodal states are learned based on signals used in the navigation and the proprioceptive information of the arm.

In the next section we present the architecture, the different parts and the learning equations. We also raise the different possible uses of such a model. In section III, we propose two possible application of this model, a navigation experiment and an arm manipulation one are investigated. Finally, the section IV present the perspectives for the next steps to improve the model, and also the future uses for such an architecture.

II. A BIO-INSPIRED MODEL FOR CHUNKING AND CONTEXT

LEARNING

Chunks learning is used on many levels, in low level visiomotor learning [START_REF] Kuniyoshi | From visuo-motor self learning to early imitation -a neural architecture for humanoid learning[END_REF], and also in high level interaction like for talking or singing [START_REF] Yamashita | Developmental learning of complex syntactical song in the bengalese finch: A neural network model[END_REF]. To encode the inforamtion, two different methodes can be used: either the input signals categorisation is saved in some neuron [START_REF] Sandamirskaya | Learning in dynamic neural fields model for sequence generation[END_REF], or the categorisation is based on population coding or a dynamic field activity [START_REF] Zhou | Error-driven hmm-based chunk tagger with contextdependent lexicon[END_REF], [START_REF] Durán | A dynamic field architecture for the generation of hierarchically organized sequences[END_REF].

In [START_REF] Schmajuk | Stimulus configuration, classical conditioning, and hippocampal function[END_REF], Schmajuk and DiCarlo presented a model for context learning. The paper treated the functional concept of the model. The principal aspect is that the authors used, in addition to the direct pathway commonly used for multimodal fusion, a hidden layer in wich the correlations between the inputs are learned. The second pathway is used to detect chunks and associate time correlated signals. The final categorisation will be conditionned by either the direct pathway with rough input signals, or the chunks learned previously.

The model we present in this paper is based on Schmajuk's and Dicarlo's architecture introduced in [START_REF] Schmajuk | Stimulus configuration, classical conditioning, and hippocampal function[END_REF], where they presented a functional bio-inspired model, exposing the error calculation, the different brain areas involved pointing out the various signals included in the learning mechanism. For our model, we derived this architecture to obtain a more generic one that can be implies in different robotic application.

The architecture we propose is presented in figure 1. The direct pathway can only perform rough learnings of the inputs values. This pathway does not take the possible time associations between the inputs. The indirect pathway is used to encode the trace conditioning.

The conditioning of the weights in the hidden layer of the model is implemented based on a simple reactive architecture. We use a network inspired from the Adaptive Resonance Theory [START_REF] Carpenter | title = Adaptive resonance theory[END_REF]. The states are encoded on the weights of the input links of recruited neurons. The computation of the activity (eq. 1) and learning (eq. 2) for those neurons is given by the following equations:

A i = 1 - 1 N j | w ij -e j | (1)
∆w ij = ǫ(e j -w ij ) if A i > vigilance ∆w ij = (e j -w ij ) else ( 2
)
where N is the dimension of the input layer, A i is the activity of the ith neuron of the output layer, ǫ the learning rate and w ij is the weight of the connection between an output neuron i and the j th neuron of the input layer whose activity is e j . H is the Heaviside function. As in the ART initial model, a vigilance factor is used to tune the granularity of the recruitment, that is to say the decision of recruiting a new chunk, vs averaging the winning (higher A i ) value.

In addition to the inputs, the chunks are used to predict the desired signal in a Least Mean Square (LMS) learning group. This group uses a modified Widrow-Hoff learning rule [START_REF] Widrow | Adaptive switching circuits[END_REF] described in eq. 3. The output of the neuron is computed as described in eq. 4

dW i,j = µ(t).(D j -O p j ).C i (3)
where D j is the activity of the unconditional stimulus, µ(t), W i,j the weights for each input, C i the context signal and O p j the predicted output. The equation for the neural activity computing is:

X i (t) = f ( j W ij .X j ) (4)
The architecture will capture correlations between close inputs. If there is no correlation, the hidden layers weights tend to 0; otherwise, those weight heighten up and the direct ones tend to 0.

To illustrate the learning behavior we present a simple example. We simulate three inputs, and according to the inputs configuration we will show how the system will react. In the figure 3 we can see the inputs signals in the 3 first graphics.

The chunks are learned according to the equations presented in 12. The recruting signal is activated each time the activity in the output decreases under a certain threshold. In Figure 3, we can see the output activity of the chunks in the 4th graphic. In the next section we will test the model in two robotic experiments in order to explore the usability of such an architecture.

A. Complex categorisation in autonomous navigation task

This a navigation simulation task. The simulated robot is able to learn it environment using a strategy based on hippocampal place cells presented in [START_REF] O'keefe | The hippocampus as a spatial map. preliminary evidence from unit activity in the freely-moving rat[END_REF]. This approach discriminates the space into different "places" recognised independently, from one another, during the navigation. The architecture uses the place cell in order to form transition cells, based on the model of Banquet et al. [START_REF] Banquet | Space-time, order and hierarchy in fronto-hippocamal system: A neural basis of personality[END_REF], successfully used in the past by Cuperlier et al. [START_REF] Cuperlier | Neurobiologically inspired mobile robot navigation and planning[END_REF] and by Hirel et al. [START_REF] Hirel | Biologically inspired neural networks for spatio-temporal planning in robotic navigation tasks[END_REF] for robotic navigation tasks. Transitions between visual place cells were learned and used in navigation with a planning strategy based on a cognitive map of transitions. However, no timing was learned for the spatial transitions between places. The cognitive map provided information about the available paths between spatial states, but not about the time needed to shift from one state to the next. In order to use the cognitive map for the navigation we need to activate goals to reach, so the activation is propagated throw the cognitive map to find out the fastest path.

In the simulation, we use a multimodal goal. It is a combination of a red colored place cell and a sound, activated 300ms after the robot inters in the red place cell. The time delay is modelized by Granular cells (DG) activations. Those granular cells are commonly used in time prediction models, for instance [START_REF] Grossberg | Neural dynamics of adaptive timing and temporal discrimination during associative learning[END_REF] and [START_REF] Moga | Apprendre par imitation : une nouvelle voie d'apprentissage pour les robots autonomes[END_REF] [START_REF] Gaussier | From perceptionaction loops to imitation processes: A bottom-up approach of learning by imitation[END_REF].

To test the architecture, we use a square environment, in which two places are red, one in the south-est and the other on the north-west of the arena, but only the first one can activate the sound.

The architecture used is described in figure 4. Our architecture allows the robot to learn the correlation between the red place cell and the time delayed sound. The condition based learning between the sensory inputs and the reward is known as positive patterning. It is largely studied by Schmajuk and DiCarlo in [START_REF] Schmajuk | Stimulus configuration, classical conditioning, and hippocampal function[END_REF]. Such a conditioning occurs when the two stimuli, in addition to the condition are presented, if only one of the stimuli is present, the condition is not satisfied.

In figure 5, we can see the arena with the two goals. As exhibit, both A and B fires the prediction neurons. This result is obtained in the early stages of the learning. We can see that, even if the neurons fires in A, the red color is less intense. The association detection resulting in a reward, we see in figure 6 the result after some time. In figure 6, we see that even if, at the start of the learning, the robot was associating the place A with the reward prediction, during time, this association is lost and only place B is taken into consideration for the reward prediction. This is the result of the positive patterning. The hidden layer in the model learns the association between the time delay from DG and the red place cell, when at the same time, it looses the direct association learned in place A, because of the reward ws not obtained.

B. Context capture in arm manipulation behaviour

This experiment is derived from De Rengervé's previous work described in [START_REF] De Rengervé | A state-action neural network supervising navigation and manipulation behaviors for complex task reproduction[END_REF]. It is a combination of the work done by Lagarde et al in [START_REF] Andry | Proprioception and imitation: on the road to agent individuation[END_REF] and by Calinon et al. in [START_REF] Calinon | Handling of multiple constraints and motion alternatives in a robot programming by demonstration framework[END_REF], for learning a navigation task in association with a guided arm manipulation for future reproduction.

The experiment goes like this: the robot navigates to a certain point in the environment, must wait for an object to be placed in its gripper, then takes the object to another point to be released. There are different actions possible depending of the objects size. Figure 7 shows a global view of the experiment. The actions are taught to the robot by the human teacher. The aim of the experiment is to use the model presented in section II to learn arm contexts, according to the different inputs (grip, localisation, arm position,...) so that the robot knows when to drop or the release the object. The adaptation of the architecture is presented in figure 8. In this case, the model learns the contexts based on conditional associations. When the robot is in a certain place cell (to take an object for example), the teacher provides the guideline for this object. When the robot arrives to the destination (to release it for instance), a conditional learning is triggered. According to a concatenation of the action done, the actual place cell, the grip state (in fact, the size of the object) and the time passed waiting, the system makes the association with the concatenation of the place cell, the ultrasound sensors, the grip state and the action. First, the possible correlations between those inputs are learned, then the global context is encoded giving the ability to recognise it in the future.

III. DISCUSSION AND CONCLUSION

In this paper, we presented a neural architecture for multimodal states categorisation in a multi-task problem. The system has been tested on a simulated of a navigation task, and a robotic arm manipulation associated with a navigation task, in order to show the different contexts where it can be used. The architecture allows to create contexts in order to use them in a long term learning like in the cognitive map [START_REF] Cuperlier | Neurobiologically inspired mobile robot navigation and planning[END_REF] for example. With this architecture, stable states can be built, from correlations between multimodal signals. If we add new modalities to categorise, we will obtain more possible situations, but also an explosion in the system's complexity. The presented model deals with such a problem by including the correlation between in the categorisation, in addition to the inputs themselves.

The error in the model is automatically calculated depending on the reward. In [START_REF] Giovannangeli | Navigation autonome bio-inspirée en environnement intérieur et extérieur: Apprentissages sensori-moteurs et planification dans un cadre interactif[END_REF], Giovannangeli exposed some bases for auto-evaluation in autonomous robotics. Coupling such a system with the given model could give an interesting advance in non-supervised learning tasks.

This work exposed some preleminary work in the tests of the given architecture. The analysis needs to be more accurate in order to have the limitations for such categorisation an to explore new possible improvments.

A next step is to introduce a loop in the learning process, in order to reuse the past learned states as possible inputs for next categorisation. A system with this ability can be built by including a memory describing the past learned contexts. This modification oblige us to study the robustness and the stability of such a system. Another possible direction is the ability to forget unused categories. If the system can categorise using past learned states, the obsolete one have to be less implied in future categories. Those are possible improvements for our architecture. As we have seen in the arm-navigation task, even if complex states are learned by the system, the human is still a key in the learning process. Allowing the human to directly correct the robot gives a good recognition contexts for the demanded experience and the teaching is less tedious for the human. The implication of the human in the leaning process or in any other interaction, implies a more complex analysis, because of all the synchronies and the timings introduced in any interactions, and in this case, the model can be a solution.

In [START_REF] Ogata | Open-end human robot interaction from the dynamical systems perspective: mutual adaptation and incremental learning[END_REF], the author notices the lack of stability in long term learnings. The system is most likely to lose its stability and the generalisation is less efficient. A system that consolidates its memory would be more precise: during sleep, short therm memory is re-encoded in the neocortex to become long term memory. A system including such a regulation will use past experience to develop new states, causing an improvement in generalisation while being more robust to noise.

Figure 1 .

 1 Figure1. There are two pathways for the inputs in the architecture. The direct pathway is just a direct injection of the inputs into the neurons. The second one, passes through a hidden layer, where the correlations between the inputs are learned.

Figure 2 .

 2 Figure2. The prediction is exposed in the last graphic (LMS), after few iteration the prediction is stabilised and the response is coherent.

Figure 3 .

 3 Figure 3.The three first graphics present the inputs. The first one is composed by 5 neurons corresponding to each color. The chunks (SAW) learning is shown in the 4th graphic, we can see an example of a positive patterning (activated when the 2nd and 3rd inputs are activated), and a negative patterning (activated when the inputs are inactivated).

Figure 4 .

 4 Figure 4. Architecture used for the multimodal goal learning. When the robot enters in a red colored place cell, waits for 300ms, a sound is perceived giving the reward. The timing is generated by the temporal activities in the granular cells. The red-time-sound association is then learned to obtain the reward .

Figure 5 .

 5 Figure 5. Both goals A and B are red colored place cells. The red color is the activation of the neurons predicting the occurrence of the sound.

Figure 6 .

 6 Figure 6. The A goal have disappeared, the model learned that the association red-sound is present only in place B.

Figure 7 .

 7 Figure 7. Overview of the task. At the grasping point, the robot chooses what action to do (drop or release) depending on the objects size. The navigation is based on vision, enabling a robust self-localisation.

Figure 8 .

 8 Figure 8. Architecture used for the arm context learning. Each state is an association based on the grip, the place cell, the amount of time the robot waited and the gesture tough by the human. According to the encoded association, the robot will be able to identify this context according to the ultrasound sensors, the place cell, the action and the grip state.

ACKNOWLEGMENTS

This work was supported by the Neurobot project ANR-BLAN-SIMI2-LS-100617-13-01.


Keywords: run in a string, Lyndon word, Fibonacci string

A run is an inclusion maximal occurrence in a string (as a subinterval) of a factor in which the period repeats at least twice. The maximal number of runs in a string of length n has been thoroughly studied, and is known to be between 0.944 n and 1.029 n. The proofs are very technical. In this paper we investigate cubic runs, in which the period repeats at least three times. We show the upper bound on their maximal number, cubic-runs(n), in a string of length n: cubic-runs(n) < 0.5 n. The proof of linearity of cubic-runs(n) utilizes only simple properties of Lyndon words and is considerably simpler than the corresponding proof for general runs. For binary strings, we provide a better upper bound cubic-runs 2 (n) < 0.48 n which requires computer-assisted verification of a large number of cases. We also construct an infinite sequence of words over binary alphabet for which the lower bound is 0.41 n.

Introduction

Repetitions and periodicities in strings are one of the fundamental topics in combinatorics on words [START_REF] Berstel | Combinatorics on words: a tutorial[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF]. They are also important in other areas: lossless compression, word representation, computational biology etc. Repetitions are studied from different points of view: classification of words not containing repetitions of a given exponent, efficient identification of factors being repetitions of different types and, finally, computing the bounds on the number of repetitions of a given exponent that a string may contain, which we consider in this paper.

Both the known results in the topic and a deeper description of the motivation can be found in a survey by Crochemore et al. [START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF].

The concept of runs (also called maximal repetitions) has been introduced to represent all repetitions in a string in a succinct manner. The crucial property of runs is that their maximal number in a string of length n (denoted as Kolpakov & Kucherov [11]. This fact is the cornerstone of any algorithm computing all repetitions in strings of length n in O(n) time. Due to the work of many people, much better bounds on runs(n) have been obtained.

runs(n)) is O(n), see
The lower bound 0.927 n was first proved by Franek & Yang [START_REF] Franek | An asymptotic lower bound for the maximal number of runs in a string[END_REF]. Afterwards, it was improved by Kusano et al. [START_REF] Kusano | New lower bounds for the maximum number of runs in a string[END_REF] to 0.944565 n employing computer experiments, and recently by Simpson [START_REF] Simpson | Modified Padovan words and the maximum number of runs in a word[END_REF] to 0.944575712 n. On the other hand, the first explicit upper bound 5 n was settled by Rytter [START_REF] Rytter | The number of runs in a string: Improved analysis of the linear upper bound[END_REF], afterwards it was systematically improved to 3.48 n by Puglisi et al. [START_REF] Puglisi | How many runs can a string contain?[END_REF], 3.44 n by Rytter [START_REF] Rytter | The number of runs in a string[END_REF],

1.6 n by Crochemore & Ilie [START_REF] Crochemore | Analysis of maximal repetitions in strings[END_REF][START_REF] Crochemore | Maximal repetitions in strings[END_REF] and 1.52 n by Giraud [START_REF] Giraud | Not so many runs in strings[END_REF]. The best known result runs(n) ≤ 1.029 n is due to Crochemore et al. [START_REF] Crochemore | Towards a solution to the "runs" conjecture[END_REF], but it is conjectured [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] that runs(n) < n. The maximal number of runs was also studied for special types of strings and tight bounds were established for Fibonacci strings [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Rytter | The structure of subword graphs and suffix trees in Fibonacci words[END_REF] and more generally Sturmian strings [START_REF] Baturo | The number of runs in Sturmian words[END_REF].

The combinatorial analysis of runs is strongly related to the problem of estimation of the maximal number of squares in a string. In the latter problem the gap between the upper and lower bound is much larger than for runs [START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF][START_REF] Crochemore | Squares, cubes, and time-space efficient string searching[END_REF].

However, a recent paper [START_REF] Kubica | On the maximal number of cubic subwords in a string[END_REF] by some of the authors shows that introduction of integer exponents larger than 2 may lead to obtaining tighter bounds for the number of corresponding repetitions.

In this paper we introduce and study the concept of cubic runs in which the period is at least three times shorter than the run itself. We show the following bounds on their maximal number, cubic-runs(n), in a string of length n:

0.41 n < cubic-runs(n) < 0.5 n .
The upper bound is achieved by analysis of Lyndon words (i.e. words that are primitive and minimal/maximal in the class of their cyclic equivalents) that appear as periods of cubic runs (Section 4). In Section 6 we improve this bound for binary words to 0.48 n by examining short factors of the string.

As for the lower bound, we describe an infinite family of binary words that contain more than 0.41 n cubic runs (Section 5). The proof of this property utilizes results obtained by analyzing the structure of cubic runs in Fibonacci strings, described in Section 3.

Preliminaries

We consider words (strings) u over a finite alphabet Σ, u ∈ Σ * ; the empty word is denoted by ε; the positions in u are numbered from 1 to |u|. By Σ n we denote the set of all words of length n from Σ * . By u R we denote the reversed word u. By Alph(u) we denote the set of all letters of u. For u = u 1 u 2 . . . u n , let us denote by u[i . . j] a factor of u equal to u i . . . u j (in particular u

[i] = u[i . . i]).
Words u[1 . . i] are called prefixes of u, and words u[i . . n] -suffixes of u.

We say that a positive integer q is the (shortest) period of a word u = u 1 . . . u n (notation: q = per(u)) if q is the smallest positive number, such that

u i = u i+q holds for all 1 ≤ i ≤ n -q. If u = w k (k is a non-negative integer), that is u = ww . . . w (k times), then
we say that u is the k th power of the word w. A square is the 2 nd power of some non-empty 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. We say that words A run (also called a maximal repetition) in a string u is an interval [i .

. j] such that:

• the period q of the associated factor u[i . . j] satisfies 2q ≤ ji + 1,

• the interval cannot be extended to the left nor to the right, without violating the above property, that is, u[i -1] = u[i + q -1] and u[jq + 1] = u[j + 1], provided that the respective letters exist.

By R(u) we denote the set of runs in u.

A cubic run is a run [i . . j] for which the shortest period q satisfies 3q ≤ ji + 1. By CR(u) we denote the set of cubic runs in u, additionally denote cubic-runs(u) = |CR(u)|. For positive integer n, by cubic-runs(n) we denote the maximum of cubic-runs(u) for all u ∈ Σ * of length n, and by cubic-runs 2 (n) we denote the maximum over all such binary strings.

For simplicity, in the rest of the text we sometimes refer to runs or cubic runs as to occurrences of corresponding factors of u.

Example. All cubic runs for an example Fibonacci word are shown in Figure 1.

n cubic-runs 2 (n) u 3

Fibonacci Strings

Let us start by analyzing the behavior of function cubic-runs for a very common benchmark in text algorithms, i.e. the Fibonacci strings, defined recursively as:

F 0 = a, F 1 = ab, F n = F n-1 F n-2 for n ≥ 2 .
Denote by Φ n = |F n |, the n th Fibonacci number (we assume that for n < 0, Φ n = 1) and by g n the word F n with the last two letters removed.

Lemma 1. [START_REF] Mignosi | Repetitions in the Fibonacci infinite word[END_REF][START_REF] Rytter | The structure of subword graphs and suffix trees in Fibonacci words[END_REF] Each run in F n is of the form

F k • F k • g k-1 (short runs) or F k • F k • F k • g k-1 (long runs), each of the runs of period Φ k .
Obviously, in Lemma 1 only runs of the form F 3 k • g k-1 are cubic runs.

Denote by #occ(u, v) the number of occurrences (as a factor) of a word u in a word v.

Lemma 2. For every k, n ≥ 0, #occ(F 3 k • g k-1 , F n ) = #occ(F 3 k , F n ) .
Proof. Each occurrence of F 3 k within F n must be followed by g k-1 , since otherwise it would form a run different from those specified in Lemma 1.

Lemma 3. For every k ≥ 2 and m ≥ 0, a) #occ(F 3 k , F m+k ) = #occ(aaba, F m ), b) #occ(aaba, F m ) = Φ m-3 -1.
Proof. Recall the Fibonacci morphism ϕ:

ϕ(a) = ab, ϕ(b) = a .
Recall that F n = ϕ n (a). The following claim provides a useful tool for the proof of items (a) and (b).

Claim 4. Assume F n = uvw, where u, v, w ∈ {a, b} * , v[1] = a and either w[1] = a or w = ε. Then there exist unique words u ′ , v ′ , w ′ such that u = ϕ(u ′ ), v = ϕ(v ′ ), w = ϕ(w ′ ), F n-1 = u ′ v ′ w ′ . And conversely, if v ′ is a factor of some F n-1 and v = ϕ(v ′ ) then v is a factor of F n .
Proof. It is a straightforward consequence of the definition of ϕ and the fact that F n = ϕ(F n-1 ).

Now we proceed to the actual proof of the lemma.

We prove item (a) by induction on k. For k = 2 we show the following equalities:

#occ(abaabaaba, F m+2 ) = #occ(ababaa, F m+1 ) = #occ(aaba, F m ) . (1)
As for the first of the equalities (1), the occurrence of F 3 2 within F m+2 cannot be followed by the letter a (since this would imply a larger run, contradicting Lemma 1) and cannot be a suffix of F m+2 (since either F 4 or F 5 is a suffix of

F m+2 ). Thus, #occ(abaabaaba, F m+2 ) = #occ(abaabaabab, F m+2 ) = #occ(ababaa, F m+1 ) .
The latter of the above equalities holds due to Claim 4, which applies here since no occurrence of abaabaabab in F m+2 can be followed by the letter b (bb is not a factor of any Fibonacci string).

To prove the second equality (1), we apply a very similar approach: ababaa is not a suffix of F m+1 and its occurrence cannot be followed by the letter a, since no Fibonacci string contains the factor aaa. Hence, by Claim 4,

#occ(ababaa, F m+1 ) = #occ(ababaab, F m+1 ) = #occ(aaba, F m ) .
Finally, the inductive step for k ≥ 3 also follows from Claim 4. Indeed, F 3 k starts with the letter a and any of its occurrences in F m+k is followed by the letter a, since, by Lemma 1, it is a part of a larger run This concludes the proof of the lemma.

F 3 k • g k-1 . Thus, #occ(F 3 k , F m+k ) = #occ(F 3 k-1 , F m+k-1 ) .
Lemma 5. For n > 5, the word F n contains (see Fig. 1):

• Φ n-5 -1 cubic runs F 3 2 • g 1 • Φ n-6 -1 cubic runs F 3 3 • g 2 • . . . • Φ 1 -1 cubic runs F 3 n-4 • g n-5 .
Words F 0 , F 1 , . . . , F 5 do not contain any cubic runs.

Proof. It is easy to check that words F n for n ≤ 5 do not contain any cubic runs. Let n > 5 and k ∈ {2, 3, . . . , n -4}. Denote m = nk. Combining the formulas from Lemmas 2 and 3, we obtain that: We are now ready to describe the behaviour of the function cubic-runs(F n ). The following theorem not only provides an exact formula for it, but also shows a relationship between the number of cubic runs and the number of distinct cubes in Fibonacci words. This relationship is even more elegant than the corresponding relationship between the number of (ordinary) runs and the number of (distinct) squares in Fibonacci words, which always differ exactly by 1, see [START_REF] Mignosi | Repetitions in the Fibonacci infinite word[END_REF][START_REF] Rytter | The structure of subword graphs and suffix trees in Fibonacci words[END_REF].

#occ(F 3 k • g k-1 , F n ) = #occ(F 3 k • g k-1 , F m+k ) = #occ(F 3 k , F m+k ) = = #occ(aaba, F m ) = Φ m-3 -1 = = Φ n-k-3 -1 .
Theorem 6. a) cubic-runs(F n ) = Φ n-3 -n + 2. b) lim n→∞ cubic-runs(Fn) |Fn| = 1 φ 3 ≈ 0.2361, where φ = 1+ √ 5 2
is the golden ratio.

c) The total number of cubic runs in F n equals the number of distinct cubes in

F n .
Proof. a) From Lemma 5 we obtain:

cubic-runs(F n ) = n-5 i=1 (Φ i -1) = Φ n-3 -3 -(n -5) = Φ n-3 -n + 2 .
b) It is a straightforward application of the formula from (a):

lim n→∞ cubic-runs(F n ) |F n | = lim n→∞ Φ n-3 -n + 2 Φ n = 1 φ 3 .
c) It suffices to note that the number of distinct cubes of length 3Φ k+1 in

F 3 k+1 •g k is |g k | + 1 = Φ k -1,
and thus the total number of distinct cubes in F n equals:

n-5 k=1 (Φ k -1) = Φ n-3 -n + 2 = cubic-runs(F n ).

Upper Bound of 0.5 n

Assume that Σ is totally ordered by ≤, what induces a lexicographical order on Σ * , also denoted by ≤. We say that λ ∈ Σ * is a Lyndon word if it is primitive and minimal or maximal in the class of words that are cyclically equivalent to it. It is known (see [START_REF] Lothaire | Combinatorics on Words[END_REF]) that a Lyndon word has no non-trivial prefix that is also its suffix.

Let u ∈ Σ n . Let us denote by I = {p 1 , p 2 , . . . , p n-1 } the set of inter-positions in u that are located between pairs of consecutive letters of u. Definition 7. We say that F : R(u) → subsets(I) is a handle function for the runs in word u if the following conditions hold:

F (v 1 ) ∩ F (v 2 ) = ∅ for any v 1 = v 2 .
(2)

|F (v)| ≥ 2 for any v ∈ CR(u). (3)
We say that F (v) is the set of handles of the run v.

Clearly, if a word u ∈ Σ n admits a handle function then cubic-runs(u) ≤ n-1 2 .

We define a function H : R(u) → subsets(I) as follows. Let v be a run with period q and let w be the prefix of v of length q. Let w min and w max be the As for the property (P1), by the definition of w min and w max we know that these words are lexicographically minimal and maximal respectively, hence it suffices to show that both words are primitive. This follows from the fact that, due to the minimality of q, w is primitive and that w min and w max are cyclically equivalent to w.

w 2 = v 2 [1] = b = w min 2 = w max 2 .
We show property (P2) by contradiction. Assume that |w min | ≥ 2. By property (P1), w min = w max is a Lyndon word. Therefore it contains at least two distinct letters, let us say: a = w min [START_REF] Baturo | The number of runs in Sturmian words[END_REF] and b = w min

[i] = a. If b < a (b > a)
then the cyclic rotation of w min = w max by i -1 letters is lexicographically smaller than w min (greater than w max ) and w min = w max -a contradiction.

Hence, the above assumption is false and

|w min | = 1.
Using properties (P1) and (P2), in the following two claims we show that H satisfies conditions ( 2) and (3). and v 2 would be the same. Without the loss of generality, we can assume that |w 1 | < |w 2 |. Thus the word w 1 is both a prefix and a suffix of w 2 (see Fig. 3), what contradicts the fact that w 2 is a Lyndon word. Proof. Let v be a cubic run. Recall that 3q ≤ |v|, where q = per(v).

If w max = w min , then, by property (P2),

|w min | = 1 and |H(v)| = |v| -1 ≥ 2.
If w max = w min , then it suffices to note that the first occurrences of each of the words w min and w max within v start no further than q positions from the beginning of v. Of course, they start at different positions. Hence, w 2 min and w 2 max are both factors of v and contribute different handles to H(v). Thus we have showed that H satisfies both conditions of a handle function, what concludes the proof of the lemma.

Theorem 11 (Weak Bounds for cubic-runs).

1. cubic-runs(n) < 0.5 n.

2.

For infinitely many n we have: 0.4 n ≤ cubic-runs(n).

Proof. The upper bound is a corollary of Lemma 8.

As for the lower bound, define:

u = 0 3 1 3 , v = 1 3 2 3 , w = 2 3 0 3 , x k = ( u 2 0 3 v 2 1 3 w 2 2 3 ) k .
Observe that for any k ≥ 1, the word x k contains at least 18k -1 cubic runs.

Indeed, we have 15k cubic runs with period 1, of the form 0 3 , 1 3 or 2 3 . Moreover, there are 3k -1 cubic runs with period 6: 2k cubic runs of the form 0 3 1 3 3 or 1 3 2 3 3 , fully contained within each occurrence of x 1 in x k = (x 1 ) k , and k -1 cubic runs of the form 2 3 0 3 3 , overlapping the concatenations of consecutive

x 1 's.
Note that for k ≥ 3, the whole word x k forms an additional cubic run.

Hence, in this case the word x k has length 45k and contains at least 18k cubic runs. Thus:

cubic-runs(x k ) ≥ 0.4 |x k | = 0.4n for k ≥ 3.
The lower bound can be improved in two ways: restricting strings to be over binary alphabet and improving 0.4 to 0.41. The coefficient in the upper bound will be also slightly improved, for the case of binary alphabet (decreased by 1 50 ). However even such small improvements require quite technical proofs.

Improving the Lower Bound

In this section we show an example sequence of binary words which gives the bound of 0.41 n. For this, we use the following morphism, which was found experimentally using a genetic algorithm:

ψ(a) = 001110, ψ(b) = 0001110 .
Recall that F n is the n-th Fibonacci word.

Theorem 12 (Improving Lower Bound

). There are infinitely many binary Proof. Denote w n = ψ(F n ), see Table 3. We will show, that for sufficiently large n we have rn ℓn > 0.41. Note that

strings ψ(F n ) such that r n ℓ n > 0.41 , where r n = cubic-runs(ψ(F n )), ℓ n = |ψ(F n )|. n r n ℓ n r n /ℓ n w n 0 1 6 0.16667 0 2 1 3 0 1 3 13 0.23077 0 2 1 3 0 4 1 3 0 2 5 19 0.26316 0 2 1 3 0 4 1 3 0 3 1 3 0 3 10 32 0.31250 0 2 1 3 0 4 1 3 0 3 1 3 0 3 1 3 0 4 1 3 0 4 17 51 0.33333 0 2 1 3 0 4 1 3 0 3 1 3 0 3 1 3 0 4 1 3 0 3 1 3 0 4 1 3 0 3 1
ℓ n = ℓ n-1 + ℓ n-2 . (4)
Additionally, we have:

w n = ψ(F n ) = ψ(F n-1 F n-2 ) = ψ(F n-1 )ψ(F n-2 ) = w n-1 w n-2 .
Let us start the analysis of cubic runs in w n with the following corner case.

Claim 13. Each word w n contains exactly 2Φ n -1 cubic runs with period 1.

Proof. Each letter of F n contributes two cubic runs with period 1 to w n = ψ(F n ), except the first letter, which contributes just one such run. Each ψ(b) contributes runs: 0 3 and 1 3 . ψ(a) contributes one or two such runs, depending on whether the considered occurrence of a is the first letter of F n , or not. If not, then it is either preceded by a or b. In both cases it contributes two cubic runs (conf. ψ(aa) and ψ(ba)). Finally, recall that each F n starts with the letter a.

Now, let us define recursively a sequence:

t n = r n for n ≤ 5 t n = t n-1 + t n-2 + n -4 for 2 | n and n ≥ 6 t n = t n-1 + t n-2 + n -3 for 2 ∤ n and n ≥ 7 . (5)
Claim 14. r n ≥ t n .

Proof. For each word w n we will identify t n cubic runs appearing in it. First, we will show that the runs identified in w n-1 and w n-2 do not merge in w n = w n-1 w n-2 . Hence, we obtain the recursive part (t n-1 + t n-2 ) of the equations defining t n . Then, we will identify a number of new cubic runs overlapping the concatenation w n = w n-1 • w n-2 . We start the analysis by considering several small and corner cases.

Let us first consider cubic runs with period 1. It is straightforward to check that they are the only cubic runs in w 0 , w 1 and w 2 . Thus, using Claim 13, we obtain the values of t n = r n for n ≤ 2. Additionally, by Claim 13, for n ≥ 3 the cubic runs with period 1 from w n-1 and w n-2 do not merge and for each n we obtain one new cubic run overlapping the concatenation w n-1 • w n-2 (due to the first letter, a, of F n-2 ).

For w 3 = ψ(abaab) we obtain one additional cubic run ψ(baa)00 = (0 3 1 3 ) 3 0 3 overlapping the concatenation w 2 • w 1 . Note, that it is not extendable, either to the left or to the right, therefore it does not merge with any other runs in any

w n . Thus t 3 = r 3 = t 2 + t 1 + 2 = 10.
In w 4 = ψ(abaababa) we obtain one additional cubic run with period 13 overlapping the concatenation, that is: 0ψ(aababa) = (0 3 1 3 0 3 1 3 0) 3 . It cannot be extended to the left, but we have to show that when w 4 is used to build longer words w n , the considered cubic run does not merge with any other cubic run. Let us note that in such a case it is always followed by w 3 which starts with ψ(a). Hence, this cubic run can extend to the right, but only for 2 characters 00, and does not merge with any other cubic runs. In conclusion, t 4 = r 4 = 17.

Now, let us consider words w n for n ≥ 5. We have shown that cubic runs contributed by w 0 , . . . , w 4 used to build w n do not merge and can be counted separately.

A new type of cubic runs that appears in w n for n ≥ 5 are runs present in the words F n -each cubic run v in F n corresponds to a cubic run ψ(v) in w n .

Due to Theorem 6, we obtain

cubic-runs(F n ) -cubic-runs(F n-1 ) -cubic-runs(F n-2 ) = = Φ n-3 -n + 2 -(Φ n-4 -n + 3) -(Φ n-5 -n + 4) = n -5
such cubic runs overlapping the concatenation of F n-1 and F n-2 , and consequently new cubic runs overlapping the concatenation of w n-1 and w n-2 . Obviously, these runs do not merge with the ones that were considered previously.

Moreover, they do not merge with each other. Indeed, if v is a run in F n that ends before the last letter of F n then the corresponding occurrence of ψ(v) in w n extends to the right exactly by the longest common prefix of ψ(a) and ψ(b), that is by two letters 00 only.

We group all the remaining cases into even and odd values of n. For odd n we have n -2 new cubic runs: n -5 from F n , one with period 1, and two additional cubic runs: the first one is ψ(baa)00 which we have already considered in the case of w 3 (it is not extendable to either side) and the second one is a cubic run with period 19: ψ(babaabaab) = (0 3 1 3 0 3 1 3 0 4 1 3 ) 3 0, not extendable to the left, but possibly extendable to the right:

. . . abaa baba | abaab . . .

For the latter cubic run we need to be more careful: in the special case of w 5 it is a suffix of the whole word, but for w n and n ≥ 7 it forms the same cubic run as the following run from F n :

. . . aab aba | abaaba ba . . . Thus, t 5 = r 5 = 30, and t n = t n-1 + t n-2 + n -3 for n ≥ 7, as declared in [START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF].

For even n we have n -3 new cubic runs: n -5 from F n , one with period 1 and one, already mentioned for w 4 , 0ψ(aababa) with period 13. However, in this case we also need to consider the troublesome run ψ(babaabaab) from the special case of w 5 separately, since w 5 is a suffix of w n-1 (as F 5 is a suffix of F n-1 ). Indeed, this cubic run is merged with the following cubic run from F n :

. . . ab abaabaab | a ba . . .

Thus, t n = t n-1 + t n-2 + n -4,
r n -0.41 • ℓ n ≥ t n -0.41 • ℓ n ≥ t n-1 + t n-2 -0.41(ℓ n-1 + ℓ n-2 ) > 0 .
This concludes the inductive proof and also the proof of the whole theorem.

Remark. A naive approach to obtain arbitrarily long binary words with large number of cubic runs would be to concatenate many copies of the same word ψ(F 20 ). However, it would not work, since some boundary runs can be glued together. Hence, a more advanced machinery was needed to prove Theorem 12.

Improving the Upper Bound in the Case of Binary Alphabet

Let u ∈ {0, 1} n . Recall that I = {p 1 , p 2 , . . . , p n-1 } is the set of all inter-positions of u. These are all candidates for handles of cubic runs from CR(u).

Recall also the definition of the handle function H. We have observed that the maximal number of cubic runs would be obtained when there are n-1 2 cubic runs, and H assigns to each of them exactly two handles. Some cubic runs can have more than two handles and some inter-positions can be not a handle of any cubic runs. Such inter-positions are called here free inter-positions. The key to the improvement of the upper bound is the localizations of free inter-positions and cubic runs with more than two handles.

Denote:

Y = { 0, 01, 0001, 0111, 000111, 1, 10, 1000, 1110, 111000 } .

By an internal factor of a word w we mean any factor of w having an occurrence which is neither a prefix nor a suffix of w. An internal factor can also have an occurrence at the beginning or at the end of w. For example, ab is an internal factor of ababa, but not of abab.

Let X be the set of binary words w which satisfy at least one of the properties:

(1) w has an internal factor which is a non-cubic run containing a square of a word from Y .

(2) w has a factor which is a cube of a word in Y \ {0, 1}.

(3) w has a factor 0000 or 1111.

The words x ∈ X have several useful properties. For example, if x = 110001000101 then the center of the square 00010001 is a free inter-position in x, since it could only be a handle of a cubic run with period 4, but the run with period 4 containing this square is not cubic. The word 1000100010 is a non-cubic run which is an internal factor of x.

On the other hand, if x contains a factor 000100010001 then it implies a cubic run with 3 handles -the centers of the squares 00010001 and 10001000 (0001 is the minimal rotation and 1000 is the maximal rotation of the period of the run).

The words in X can be checked to satisfy the following simple fact. This completes the proof.

  The proof of item (b) goes by induction on m. For m ≤ 3 one can easily check that #occ(aaba, F m ) = 0, and there is exactly one occurrence of aaba in F 4 . The inductive step is a conclusion of the fact that for m ≥ 5 the word F m contains all occurrences of aaba from F m-1 and F m-2 and one additional occurrence overlapping their concatenation: . . . ab a | aba ab . . . The case of 2 ∤ m. . . . ab aab | a ba . . . The case of 2 | m.

Figure 1 :

 1 Figure 1: The structure of cubic runs in the Fibonacci word F 9 . The cubic runs are distributed as follows: 1 run F 3 5 • g 4 , 2 runs F 3 4 • g 3 , 4 runs F 3 3 • g 2 , and 7 runs F 3 2 .

  minimal and maximal words (in lexicographical order) cyclically equivalent to w. H(v) is defined as follows: a) if w min = w max then H(v) contains all inter-positions in the middle of any occurrence of w 2 min in v, and in the middle of any occurrence of w 2 max in v, b) if w min = w max then H(v) contains all inter-positions within v. Example. Let us consider a word (aabab) 3 aab 4 , see Fig. 2. It contains two cubic runs: v 1 = (aabab) 3 aab and v 2 = b 4 . For v 1 we have per(v 1 ) = 5, w 1 = v 1 [1 . . 5] = aabab = w min 1 and w max 1 = babaa. For v 2 we have per(v 2 ) = 1,

b a b a a b a b a a b a b a a 1 Figure 2 :Lemma 8 .

 128 Figure 2: An example of a word with two cubic runs v 1 and v 2 . For v 1 we have w min 1 = w max 1 and for v 2 the corresponding words are equal to b (a single-letter word). The inter-positions belonging to the sets H(v 1 ) and H(v 2 ) are pointed by arrows.

Claim 9 .

 9 H(v 1 ) ∩ H(v 2 ) = ∅ for any two different runs v 1 and v 2 in u. Proof. Assume, to the contrary, that p i ∈ H(v 1 ) ∩ H(v 2 ) is a handle of two different runs v 1 and v 2 . By the definition of H and properties (P1) and (P2), p i is located in the middle of two squares of Lyndon words: w 2 1 and w 2 2 , where |w 1 | = per(v 1 ) and |w 2 | = per(v 2 ). Note that w 1 = w 2 , since otherwise runs v 1

Figure 3 : 2 1 and w 2 2 . 10 .

 32210 Figure 3: A situation where p i is in the middle of two different squares w 2 1 and w 2 2 .

Figure 4 :

 4 Figure 4: Illustration of the definition of H and Claim 10. The arrows in the figure point to the elements of H(v) for cubic runs.

Observation 15 .

 15 Let u ∈ {0, 1} n . (a) If a factor u[i . . j] contains any factor satisfying point (1) of the definition of X then there is at least one free inter-position in u amongst p i , p i+1 , . . . , p j-1 . (b) If a factor u[i . . j] contains any factor satisfying point (2) or (3) then there are at least 3 inter-positions in u amongst p i , p i+1 , . . . , p j-1 which are handles of the same cubic run.This implies directly the following fact.Theorem 16 (Improving Upper Bound).

2 • n - 1 -

 21 cubic-runs 2 (n) ≤ 0.48 n . Proof. Each binary word of length 25 contains a factor from X. It has been shown experimentally by checking all binary words of size 25. Let u ∈ {0, 1} n . Let us partition the word u into factors of length 25: u[1 . . 25], u[26 . . 50], . . . (possibly discarding at most 24 last letters of u). By Observation 15, it is possible to remove one inter-position from every one of these factors so that each cubic run in u has at least two handles in the set of remaining inter-positions. The total number of inter-positions in u is n -1 and we have shown that at least n-1 25 of them can be removed and each cubic run will have at least two handles among remaining inter-positions. Hence: cubic-runs(u) ≤ 1

Table 1 :

 1 The maximum number cubic-runs 2 (n) of cubic runs in a binary string of length n for n = 3, . . . , 29. Example binary words for which the maximal number of cubic runs is attained are shown in the following Table2. u and v are cyclically equivalent (or that one of them is a cyclic rotation of the other) if u = xy and v = yx for some x, y ∈ Σ * . It is a simple and well-known observation, that if u and v are cyclically equivalent then |root(u)| = |root(v)|.

Table 2 :

 2 Lexicographically smallest binary words u ∈ {0, 1} n , for which cubic-runs(u) = cubic-runs 2 (n) (see also Table1).

		1	000
	6	2	000111
	9	3	000111000
	12	4	000100010001
	14	5	00010001000111
	17	6	00010001000111000
	18	7	000111000111000111
	21	8	000111000111000111000
	24	9	000111000111000111000111
	26	10	00010001000111000111000111
	29	11	00010001000111000111000111000

Table 3 :

 3 Characteristics of a first few elements of the sequence (wn).

  what concludes the proof of Claim 14.Completing the proof of Theorem 12. We prove by induction, that for n ≥ 20, r n ≥ 0.41 • ℓ n . The following inequalities:

	r 20 ℓ 20	≥	46 348 113 031	> 0.41 ,
	r 21 ℓ 21	≥	75 005 182 888	> 0.41 ,

are consequences (obtained by heavily using a calculator) of the formulas (4), (

5

) and Claim 14. The inductive step (for n ≥ 22) follows from:


Maxime Crochemore

Costas S Iliopoulos

Solon P Pissis
email: pississo@dcs.kcl.ac.uk

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

Cover array string reconstruction

come

Introduction

The notion of periodicity in strings is well studied in many fields like combinatorics on words, pattern matching, data compression and automata theory (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF][START_REF] Lothaire | Applied Combinatorics on Words[END_REF]), because it is of paramount importance in several applications, not to talk about its theoretical aspects.

The concept of quasiperiodicity is a generalisation of the notion of periodicity, and was defined by Apostolico and Ehrenfeucht in [START_REF] Apostolico | Efficient detection of quasiperiodicities in strings[END_REF]. In a periodic repetition the occurrences of the single periods do not overlap. In contrast, the quasiperiods of a quasiperiodic string may overlap. We call a proper factor u of a nonempty string y a cover of y, if every letter of y is within some occurrence of u in y. In this paper, we consider the so-called aligned covers, where the cover u of y needs to be a border (i.e. a prefix and a suffix) of y. The array C is called the minimal-cover (resp. maximalcover) array of the string y of length n, if for each i, 0 ≤ i < n, C [i] stores either the length of the shortest (resp. longest) cover of y[0 . . i], when such a cover exists, or zero otherwise. In particular, we do not consider a string to be a cover of itself.

Apostolico and Breslauer [START_REF] Apostolico | Of periods, quasiperiods, repetitions and covers[END_REF][START_REF] Breslauer | An on-line string superprimitivity test[END_REF] gave an online linear runtime algorithm computing the minimal-cover array of a string. In their definition, a string is a cover of itself, but it is straightforward to modify their algorithm to accommodate our definition. Li and Smyth [START_REF] Li | Computing the cover array in linear time[END_REF] provided an online linear runtime algorithm for computing the maximal-cover array.

In this paper, we present a constructive algorithm checking if an integer array is the minimal-cover or maximal-cover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. For our validity checking algorithm, we use the aforementioned algorithms that compute cover arrays.

All algorithms run in linear time. This is essentially due to a combinatorial property of cover arrays: the sum of important values in a cover array is bounded by twice the length of the string.

The result of the paper completes the series of algorithmic characterisations of data structures that store fundamental features of strings. They concern Border arrays [START_REF] Duval | Border array on bounded alphabet[END_REF][START_REF] Franek | Verifying a Border array in linear time[END_REF], Parameterized Border arrays [START_REF] Inenaga | Counting parameterized border arrays for a binary alphabet[END_REF] and Prefix arrays [START_REF] Clement | Reverse engineering prefix tables[END_REF] that stores periods of all the prefixes of a string, as well as the element of Suffix arrays [START_REF] Bannai | Inferring strings from graphs and arrays[END_REF][START_REF] Franek | Reconstructing a Suffix Array[END_REF] that memorises the list of positions of lexicographically sorted suffixes of the string. The question is not applicable to complete Suffix trees or Suffix automata since the relevant string is part of these data structures. The algorithms may be regarded as reverse engineering processes and, beyond their obvious theoretical interest, they are useful to test the validity of some constructions. Their linear runtime is an important part of their quality.

The rest of the paper is structured as follows. Section 1 presents the basic definitions used throughout the paper and the problem. In Section 2, we prove some properties of minimal-cover arrays used later for the design or the analysis of algorithms. In Section 3, we describe our constructive cover array validity checking algorithms. Section 4 provides some combinatorially interesting numerical data on minimal-cover arrays.

Definitions and Problems

Throughout this paper we consider a string y of length |y| = n on an unbounded alphabet. It is represented as y[0 . . n -1]. A string w is a factor of y if y = uwv for two strings u and v. It is a prefix of y if u is empty and a suffix of y if v is empty. A string u is a period of y if y is a prefix of u k for some positive integer k, or equivalently if y is a prefix of uy. The period of y is the shortest period of y. A string x of length m is a cover of y if both m < n and there exists a set of positions P ⊆ {0, . . . , n -m} satisfying y[i . . i + m -1] = x for all i ∈ P and i∈P {i, . . . , i + m -1} = {0, . . . , n -1}. Note that this requires x to be a prefix as well as a suffix of y. The minimal-cover array C of y is the array of integers C [0 . . n -1] for which C [i], 0 ≤ i < n, stores the length of the shortest cover of the prefix y[0 . . i], if such a cover exists, or zero otherwise. The maximal-cover array C M stores longest cover at each position instead. The following table provides the minimal-cover array C and the maximal-cover array C M of the string y = abaababaababaabaababaaba. We consider the following problems for an integer array A: Problem 1 (Minimal Validity Problem). Decide if A is the minimal-cover array of some string.

Problem 2 (Maximal Validity Problem).

Decide if A is the maximal-cover array of some string.

Problem 3 (Minimal Construction Problem).

When A is a valid minimalcover array, exhibit a string over an unbounded alphabet whose minimalcover array is A.

Problem 4 (Maximal Construction Problem).

When A is a valid maximalcover array, exhibit a string over an unbounded alphabet whose maximalcover array is A.

Properties of the Minimal-Cover Array

In this section, we assume that C is the minimal-cover array of y. Its first element is 0, as we do not consider a string to be a cover of itself. Next elements are 1 only for prefixes of the form a k for some letter a. We will use the following fact in our argumentation. For the rest of the section we assume that n > 1 and prove several less obvious properties of the minimal-cover array.

j -C [j] > i -C [i] of Lemma 2 (i ′ = i -C[i] + 1, j ′ = j -C[j] + 1). Lemma 1. If 0 ≤ i < n and C [i] = 0, then C [C [i] -1] = 0. Proof. Immediate from Fact 1.
⊓ ⊔ Lemma 2. Let i and j be positions such that

j < i, j -C [j] ≥ i -C [i], C [i] = 0 and C [j] = 0. Furthermore let r = j -(i -C [i] + 1). If i -C [i] = j -C [j] then C [r] = 0, otherwise if i -C [i] < j -C [j], then C [r] = C [j]. Proof. First assume that i -C [i] = j -C [j]. Then C [j -(i -C [i] + 1)] = C [j -(j -C [j] + 1)] = C [C [j] -1] = 0 according to Lemma 1. Now assume that i -C [i] < j -C [j]
. This situation is depicted in Figure 1.

The string u = y[j -C [j] + 1 . . j] of length C [j] covers the string y[0 . . j]. By precondition (j < i, j -C [j] > i -C [i]) u also covers y[0 . . r],
Then (i -C [i]) -(j -C [j]) > C [j]/2.
Proof. For ease of notation let p = C [i], q = C [j] and r = (i-p)-(jq). Assume the statement does not hold, i.e. r ≤ q 2 . Let u = y[0 . . r -1]. Then due to the overlap of y[ip + 1 . . i] and y[jq + 1 . . j] both y[0 . . p -1] and y[0 . . q -1] are powers of u. Let y[0 . . q -1] = u e for some exponent e.

Observe that e = q/r ≥ q/(q/2) = 2. However y[0 . . q -1] is also covered by v = u 1+e-⌊e⌋ . As |v| < q we obtain a contradiction.

⊓ ⊔

Definition 1. A position j = 0 of C is called totally covered, if there is a position i > j for which C [i] = 0 and i -C [i] + 1 ≤ j -C [j] + 1 < j.
Let C p be obtained from C by setting C [i] = 0 for all totally covered indices i on C . We call C p the pruned minimal-cover array of y. The next table shows the pruned minimal-cover array of the example string above. Proof.

Let I i = {i -C [i] + 1, i -C [i] + 2, . . . i} for i = 0, . . . , n -1 if C [i] = 0 and I i = ∅ otherwise. Let I ′ i denote the lower half of I i (if C [i] is uneven, the middle element is included). According to Lemma 3, i = j implies I ′ i ∩ I ′ j = ∅. Thus the relation n-1 i=0 |I ′ i | ≤ n holds, which in turn implies n-1 i=0 |I i | ≤ n-1 i=0 2|I ′ i | ≤ 2n. ⊓ ⊔
The bound of Lemma 4 is asymptotically tight. For an integer k > 1, let x k = (a k ba k+1 b) n/(2k+3) . For k = 2 and n = 23 we get: i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 y[i] a a b a a a b a a b a a a b a a b a a a b a a C p [i] 0 0 0 0 0 0 0 0 5 0 0 0 0 7 0 5 0 0 0 0 7 0 5 It is straightforward to see that all segments of length 2k + 3 of C p contain the values 2k + 1 and 2k + 3, except at the beginning of the string. Therefore the sum of elements in C p is (4k + 4)( n 2k+3 -1), which tends to 2n when k (and n) goes to infinity.

Reverse Engineering a Cover Array

We solve the stated problems in three steps: array transformation, string inference and validity checking.

Transforming Maximal to Minimal-Cover Arrays We first show how to transform a maximal-cover array into a minimal-cover array in linear time. The following algorithm Maxtomin converts the maximal-cover array C of y to its minimal-cover array in linear time.

Maxtomin(C , n)

1

for i ← 0 to n -1 do 2 if C [i] = 0 and C [C [i] -1] = 0 then 3 C [i] ← C [C [i] -1]
The algorithm works in the following way. Assume the for loop is executing for some i > 0. At this time the prefix C [0 . . i -1] of the array has been converted to a minimal-cover array and we want to determine the value The nonzero values in C induce an equivalence relation on the positions of every string that has the minimal-cover array C . More precisely, if we find the value ℓ = 0 in position i of C , then this imposes the constraints

of C [i]. If C [i]
y[k] = y[i -ℓ + 1 + k]
for k = 0, . . . , ℓ -1. We say that the positions k and iℓ + 1 + k are bidirectionally linked. Let the undirected graph G(V, E) be defined by V = {0, . . . , n -1} and

E = i=0,...,n-1 j=0,...C [i]-1 ({(j, i -C [i] + 1 + j)}) .
Then the nonzero values in C state that the letters at positions i and j of any word y such that C is the minimal-cover array of y need to be equal, if i and j are connected in G. According to Lemma 2, we do not lose connectivity between vertices of G, if we remove totally covered indices from C , i.e. the graph induced by C has the same connected components as the one induced by its pruned version C p . The number of edges in the graph induced by C p is bounded by 2n according to Lemma 4. The pruned minimal-cover array C p can be obtained from the minimal-cover array C using the following algorithm Prune in linear time.

Prune(C , n) 1 ℓ ← 0 2 for i ← n -1 downto 0 do 3 if ℓ ≥ C [i] then 4 C [i] ← 0 5 ℓ ← max(0, max(ℓ, C [i]) -1) 6 return C A non-zero value at index i in C defines an interval [i -C [i] + 1, i].
The algorithm scans C from large to small indices, where the value ℓ stores the minimal lower bound of all the intervals encountered so far. If an interval starting at a smaller upper bound has a greater lower bound than ℓ, we erase the corresponding value in C by setting it to zero. Thus we remove all totally covered indices from C and obtain the pruned array C p . So far we know how to extract information from the non-zero values of C by computing connected components in a graph which has no more than 2n edges. The vertices in each connected component designate positions in any produced string which need to have equal letters. By assigning a different letter to each of these components, we make sure not to violate any constraints set by the zero values in C . The following algorithm MinArrayToString produces a string y from an array A assumed to be a pruned minimal-cover array. The first two for loops produce the edges E in the graph G induced by A, where we implement the transition relation by assigning a linear list of outgoing edges to each vertex. The third for loop computes the connected components in the graph by using depth first search and assigns the letters to the output string. Each connected component is assigned a different letter. The runtime of the algorithm is linear in the number of edges of the graph, which is bounded by 2n. Validity Checking In the third step we use the MinArrayToString algorithm as a building block for our validity checking algorithm. Thus we have to ensure some basic constraints so that the algorithm does not firstly access any undefined positions in the input and secondly runs in linear time. As a first step, we have to make sure that the algorithm will not try to define edges for which at least one vertex number is not valid. This check is performed by the following algorithm Precheck, which runs in linear time.

MinArrayToString(A, n) 1 ⊲ Produce edges 2 for i ← 0 to n -1 do 3 E[i] ← empty list 4 for i ← 0 to n -1 do 5 for j ← 0 to A[i] -1 do 6 E[i -A[i] + 1 + j].add(j), E[j].add(i -A[i] + 1 + j) 7 ⊲
Precheck(A, n) 1 for i ← 0 to n -1 do 2 if i -A[i] + 1 < 0 then 3
return false 4 return true If Precheck returns true, then MinArrayToString will only generate edges from valid to valid vertices. If we are checking for validity of a maximal-cover array, we then pass the array through the algorithm Max-ToMin as a next step. In both cases (minimal and maximal) the next step is to prune the array using the algorithm Prune. After this, we can call the algorithm MinArrayToString with the so-modified array, but it may not run in linear time, as the constraints imposed by Lemma 3 may not hold if the original input array is invalid. We avoid this situation with the following algorithm Postcheck.

Postcheck(A, n)

1 j ← -1 2 for i ← 0 to n -1 do 3 if A[i] = 0 then 4 if j = -1 and (i -A[i]) -(j -A[j]) ≤ A[j]

Conclusion

In this paper, we have provided linear runtime algorithms for checking the validity of minimal-and maximal-cover arrays and algorithms to infer strings from valid minimal-and maximal-cover arrays. The linear time inference of strings using the least possible alphabet size from cover arrays remains an open problem.

  15 16 17 18 19 20 21 22 23 y[i] a b a a b a b a a b a b a a b a a b a b a a b a C [i] 0

Fact 1 (

 1 Transitivity) If u and v cover y and |u| < |v|, then u covers v.

Fig. 1 .

 1 Fig. 1. Case j -C [j] > i -C [i] of Lemma 2 (i ′ = i -C[i] + 1, j ′ = j -C[j] + 1).

Lemma 3 .

 3 as there exists an occurrence of u at position r -C [j] + 1. Thus we have C [r] ≤ C [j]. The assumption C [r] < C [j] leads to a contradiction to the minimality of C . Thus we have C [r] = C [j].⊓ ⊔ Let i and j be positions such that j < i and j-C [j] < i-C [i].

Lemma 4 .

 4 12 13 14 15 16 17 18 19 20 21 22 23 y[i] a b a a b a b a a b a b a a b a a b a b a a b a C [i] 0 The sum of the elements of C p does not exceed 2n.

Theorem 1 .

 1 The problems Minimal Construction Problem and Maximal Construction Problem are solved in linear time by the algorithm MinAr-rayToString and the sequence of algorithms MaxToMin and MinAr-rayToString respectively.

IfFig. 2 .

 2 Fig.2. Maximal ratio of sum over pruned minimal-cover array and word length for words over the binary alphabet of even length 8 to 30

  is zero then there is no cover and we leave the value as it is. If C [i] is not zero, then we know from Fact 1 that if there is a shorter cover, then it covers y[0 . .C [i] -1]. Thus we look up C [C [i] -1] to see ifthere is a shorter cover we can substitute for C [i]. As the segment before index i is already the minimal-cover array up to this point, we know that such a value is minimal.String Inference In this step, we assume that the integer array C of length n is the minimal-or maximal-cover array of at least one string. From what we wrote above, we can assume without loss of generality that C is a minimal-cover array.

we can call MinArrayToString and be sure that it will run in linear time. At this point we have obtained a string from the input array in linear time. We know that if the input array is valid, the minimal-or maximal-(depending on what kind of input we are given) cover array of this string matches the input. If the input array is not valid, we cannot obtain it by computing the minimal-or maximal-cover array from the obtained string. Thus we can check whether an array A is a valid maximal-cover array using the following algorithm CheckMaximal.

Experiments and Numerical Results

Figure 2 shows the maximal ratio of sums of elements of pruned minimalcover array, for all words over a two-letter alphabet, using even word lengths 8 to 30. These ratios are known to be smaller than 2 by Lemma 4. However, values close to this bound are not observed for small word length.

We were able to verify the linear runtime of our algorithm in experiments. The implementation for the CheckMinimal function is available at the Website http://www.dcs.kcl.ac.uk/staff/tischler/src/recovering-0.0.0.tar.bz2, which is set up for maintaining the source code and the documentation.


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

Marek Cygan
email: [cygan@mimuw.edu.pl

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

Algorithms for Three Versions of the Shortest Common Superstring Problem

The input to the Shortest Common Superstring (SCS) problem is a set S of k words of total length n. In the classical version the output is an explicit word SCS(S) in which each s ∈ S occurs at least once. In our paper we consider two versions with multiple occurrences, in which the input includes additional numbers (multiplicities), given in binary. Our output is the word SCS(S) given implicitly in a compact form, since its real size could be exponential. We also consider a case when all input words are of length two, where our main algorithmic tool is a compact representation of Eulerian cycles in multigraphs. Due to exponential multiplicities of edges such cycles can be exponential and the compact representation is needed. Other tools used in our paper are a polynomial case of integer linear programming and a min-plus product of matrices.

Introduction

The algorithmic aspects of the SCS problem are thoroughly studied in theoretical as well as in practical computer science. In this paper we consider two variations of the SCS problem related to the number of occurrences of input words: Uniform Multiple Occurrences SCS (SUM-SCS) and Multiple Occurrences SCS Problem (MULTI-SCS). Our algorithms use several interesting combinatorial tools: Eulerian cycles in multigraphs, shortest paths via matrix multiplication and integer linear programming with a constant number of variables.

The SCS problem and its variations are studied in their own and also from the point of view of computational biologists. Recent advances, based either on sequencing by synthesis or on hybridisation and ligation, are producing millions of short reads overnight. An important problem with these technologies is how to efficiently and accurately map these short reads to a reference genome [START_REF] Li | Mapping short DNA sequencing reads and calling variants using mapping quality scores[END_REF] that serves as a framework. The Genome Assembly Problem is as follows: given a large number of short DNA sequences (often called "fragments") generated by a sequencing machine like the ones mentioned above, put them back together to create a representation of the chromosome that sequences were taken from (usually a single organism). There are several software tools for this (called assemblers), to name a few: Celera Assembler [START_REF] Myers | A whole-genome assembly of drosophila[END_REF] (mostly long reads), SSAKE [START_REF] Warren | Assembling millions of short DNA sequences using SSAKE[END_REF], SHARCGS [START_REF] Dohm | SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing[END_REF], SHRAP [START_REF] Sundquist | Whole-genome sequencing and assembly with high-throughput, short-read technologies[END_REF], Velvet [START_REF] Zerbino | Velvet: algorithms for de novo short read assembly using de Bruijn graphs[END_REF]. When the problem of genome assembly arisen, computer scientists came up with the above abstraction of the SCS Problem, which they showed to be NP-hard [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], and developed several efficient approximation algorithms for it (see for example [1-3, 7, 15]). However, the SCS problem actually does not address the following issue of the biological Genome Assembly Problem -multiple occurrences of the fragments in the assembly. The shortest common superstring algorithms result in a shortest word but ignore repeated occurrences. In our paper we consider some variations of the problem in which we deal with multiple occurrences. First we consider a special case of SCS in which all fragments are of length 2. It happens that even this simple version is nontrivial in presence of multiplicities. Then a special case of constant number of words in S is considered. It is also nontrivial: we use sophisticated polynomial time algorithms for integer linear programs with constant number of variables.

Definitions of problems.

Let S = {s 1 , s 2 , . . . , s k } be the set of input words, s i ∈ Σ * . In all the problems defined below, we assume that S is a factor-free set, i.e. none of the words s i is a factor of any other word from S. Let n denote the total length of all words in S. Let #occ(u, v) be the number of occurrences (as a factor) of the word u in the word v. We consider three problems:

SUM-SCS(k):

Given a positive integer m, find a shortest word u such that

k i=1 #occ(s i , u) ≥ m . MULTI-SCS(k):
Given a sequence of non-negative integers m 1 , m 2 , . . . , m k , find a shortest word u such that: #occ(s i , u) ≥ m i for each i = 1, 2, . . . , k.

MULTI-SCS 2 (k):

A special case of the MULTI-SCS(k) problem where all input words s i are of length 2.

We assume, for simplicity, that the binary representation of each of the numbers in the input consists of

O(n) bits, i.e. m = O(2 n ) in SUM-SCS(k) and m i = O(2 n ) in MULTI-SCS(k)
. Moreover, we assume that such numbers fit in a single memory cell in the RAM model, and thus operations on such numbers can be performed in constant time (if this is not the case, one would need to multiply the time complexities of the algorithms presented here by a polynomial of the length of binary representation of numbers). Also, the total size of input data in each of the problems is O(n).

By finding the SCS in each of the problems we mean computing its length and its compressed representation which is of size polynomial in n, that can be used to reconstruct the actual word in a straightforward manner in O(ℓ) time, where ℓ is the length of the word (this could be a context-free grammar, a regular expression etc).

Preliminaries

Let the overlap ov(s, t) of two non-empty words, s and t, be the longest word y, such that s = xy and t = yz for some words x = ε and z. We define ov(s, t) = ε if s = ε or t = ε. Also, let the prefix pr(s, t) of s, w.r.t. t, be the prefix of s of length |s| -|ov(s, t)| -therefore s = pr(s, t)ov(s, t). For a given set S = {s 1 , s 2 , . . . , s k } of words, the prefix graph of S is a directed graph with labeled and weighted edges defined as follows. The set of vertices is {0, 1, 2, . . . , k, k + 1}; vertices 1, 2, . . . , k represent the words s 1 , s 2 , . . . , s k and 0, k + 1 are two additional vertices called source and destination, each of which corresponds to an empty word s 0 = s k+1 = ε. The edges are labeled with words, and their lengths (weights) are just the lengths of the labels. For all 0 ≤ i, j ≤ k + 1, i = k + 1, j = 0, there is an edge (s i , s j ) labeled with pr(s i , s j ). Note that, for a factor-free set S, the concatenation of labels of all edges in a path of the form 0 = v 1 , v 2 , v 3 , . . . , v p-1 , v p = k + 1, i.e. pr(s v1 , s v2 )pr(s v2 , s v3 ) . . . pr(s vp-1 , s vp ) , represents a shortest word containing words s v2 , s v3 , . . . , s vp-1 in that order. The prefix graph can easily be constructed in O(k • k i=1 |s i |) time, using the prefix function from the Morris-Pratt algorithm [START_REF] Crochemore | Jewels of Stringology[END_REF]. However, this can also be done in the optimal time complexity O( [START_REF] Gusfield | An efficient algorithm for the all pairs suffix-prefix problem[END_REF]. Let A and B be matrices of size (k + 2) × (k + 2) containing non-negative numbers. The min-plus product A ⊕ B of these matrices is defined as:

k i=1 |s i | + k 2 ) -see
(A ⊕ B)[i, j] = min{A[i, q] + B[q, j] : q = 0, 1, . . . , k + 1} .
We assume that the reader is familiar with a basic theory of formal languages and automata, see [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF].

MULTI-SCS 2 (k) problem

First, let us investigate a variant of the MULTI-SCS(k) problem in which all input words s i are of length 2. Note that in such a case n = 2k. It is a folklore knowledge that MULTI-SCS 2 (k) can be solved in polynomial time when all multiplicities m i are equal to one. We prove a generalization of this result for the MULTI-SCS 2 (k) problem: Any solution for the MULTI-SCS 2 (k) problem can be viewed as a path in some supergraph G ′ = (V, E ∪ E ′ ) of G, passing through each edge e ∈ E at least c(e) times. We are interested in finding the shortest solution, consequently we can reduce the problem to finding the smallest cardinality multiset of edges E ′ such that the multigraph (V, E ∪ E ′ ) has an Eulerian path. To simplify the description, we find the smallest multiset E ′ for which the graph (V, E ∪ E ′ ) has an Eulerian cycle, and then reduce the cycle to a path (if

E ′ = ∅).
MULTI-SCS 2 (k) can be solved using the following algorithm: Proof. In the trivial case, when G already has an Eulerian cycle, we return

1: construct the multigraph G = (V, E) 2: find the smallest cardinality multiset of edges E ′ such that G ′ = (V, E ∪ E ′ )
E ′ = ∅. Let C 1 , C 2 , . . . , C q (C i ⊆ V ) be connected components in the undirected version of the multigraph G.
For each component we compute its demand D i defined as follows:

D i = v∈Ci max(indeg(v) -outdeg(v), 0)
where indeg(v) (resp. outdeg(v)) is the in (resp. out) degree of a vertex v. Let the demand of the vertex v be defined as

d(v) = |indeg(v) -outdeg(v)|. Let V + (C i ) (resp. V -(C i )) be the set of vertices v ∈ V (C i ), such that indeg(v) > outdeg(v) (resp. indeg(v) < outdeg(v)).
We describe an algorithm that computes the smallest cardinality multiset E ′ of the size:

|E ′ | = q i=1 max(1, D i ) .
First, let us observe that an edge e = (u, v) ∈ E ′ can have one of the following contributions:

if u, v ∈ C i then e can decrease the demand D i by at most 1, -if u ∈ C i and v ∈ C j (i = j, with D i > 0 and D j > 0) then e merges C i , C j into a single component with demand at least

D i + D j -1, -if u ∈ C i and v ∈ C j (i = j, with D i = 0 or D j = 0) then e merges C i , C j into a single component with demand at least D i + D j .
To construct the optimal set E ′ , we use the following algorithm (see Fig. 1):

1:

E ′ = ∅ 2:
first we connect all components: 3: while number of components > 1 do 4: let Ci, Cj be two different components 5:

if Di = 0 then let u be a vertex from the set V + (Ci), otherwise from V (Ci) 6:

if Dj = 0 then let v be a vertex from the set V -(Cj), otherwise from V (Cj) 7:

add to E ′ a single edge (u, v) (with c((u, v)) = 1) 8: from now on we have only one component C in G, we reduce its demand to 0: 9: while V + (C) = ∅ do 10:

let v + ∈ V + (C), v -∈ V -(C) 11:
add to E ′ an edge (v + , v -) with multiplicity min(d(v + ), d(v -)) 12: return E ′ Observe that if a component C i admits D i > 0 it means that both sets V -(C i ) and V + (C i ) are nonempty. In the first phase we add exactly q -1 edges to E ′ . In the second phase we reduce the total demand to 0, each iteration of the while loop reduces the demand of at least one vertex to 0. Hence we add at most O(|V |) different edges in the second phase. If we store E ′ using a compact representation, its size is O(|V | + |E|) and the above algorithm computes it in such time complexity.

⊓ ⊔

Lemma 2. For a given compact representation of a directed Eulerian multigraph G = (V, E), there exists an O(|V | • |E|) time algorithm for computing the representation of an Eulerian cycle in G.

Proof. The Eulerian cycle can be of exponential size, therefore we construct its compressed representation. Such a representation is an expression of the form

π = w p1 1 w p2 2 . . . w p ℓ ℓ ,
E ′ = {(a, d) • 3, (a, c) • 2, (b, c) • 4}
where w i is a path in G, and p i is a non-negative integer. We say that an occurrence of v ∈ w i is free if p i = 1. The algorithm is a slight modification of the standard algorithm for computing Eulerian cycles in graphs, see Fig. (a→d→b)(b→b) 3 (b→a)(a→d→b→a) 4 (a→c→a) 5 (a→d→b→c→a) 5 (a→d→c→a) 10 , which corresponds to a word adb(b) 3 a(dba) 4 (ca) 5 (dbca) 5 (dca) 10

MULTI-SCS(k) problem for k = O(1)

Let us consider a prefix graph G of S = {s 1 , s 2 , . . . , s k }. In order to solve the general MULTI-SCS(k) problem, it suffices to find the shortest path π from 0 to k + 1 in G that passes through each vertex i ∈ V (G), for 1 ≤ i ≤ k, at least m i times. We assume that k = O(1).

Let us treat G as a (deterministic) finite automaton A: 0 is its start state, k + 1 is its accept state, and an edge from i to j in G is identified by a triple (i, j, |pr(s i , s j )|) which represents its starting and ending vertex and its length. Let Γ ⊆ {0, . . . , k+1}×{0, . . . , k+1}×(Z + ∪{0}) be the set of triples identifying all edges of G. Each path from 0 to k + 1 corresponds to a word (from Γ * ) in the language accepted by A.

Let α(A) be a regular expression corresponding to the language accepted by A -its size is O(1) and it can be computed in O(1) time [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF] (recall that k = O(1)). Definition 1. We call two words u, v ∈ Γ * commutatively equivalent (notation: u ≈ v) if for any a ∈ Γ , #occ(a, u) = #occ(a, v). We call two regular languages

L 1 , L 2 commutatively equivalent (notation: L 1 ≈ L 2 ) if for each word u ∈ L 1 (u ∈ L 2 ) there exists a word v ∈ L 2 (v ∈ L 1 ) such that u ≈ v.
Lemma 3. The regular expression α(A) can be transformed in O(1) time into a regular expression β(A) such that:

L(β(A)) ⊆ L(α(A)) and L(β(A)) ≈ L(α(A)) (1)
and β(A) is in the following normal form:

β(A) = B 1 + B 2 + . . . + B k where B i = C i,1 C i,2 . . . C i,li and each C i,j is:
either a ∈ Γ , or (a 1 a 2 . . . a p ) * , where a r ∈ Γ .

Proof. The proof contains an algorithm for computing β(A) in O(1) time.

In the first step we repetively use the following transformations in every possible part of α(A) until all Kleene's stars contain only concatenation of letters from Γ (all letters in the transformations denote regular expressions):

γ(δ + σ)ρ * → (γδρ) * (γσρ) * (2)
(γδ * σ) * → γδ * σ(γσ) * + ε . (3)
Since then, it suffices to repetively use the following transformation to obtain the required normal form:

γ(δ + σ)ρ → (γδρ) + (γσρ) . (4)
It is easy to check that each of the transformations (2)-( 4) changes the regular expression into another regular expression such that the language defined by the latter is a commutatively equivalent sublanguage of the language defined by the former.

⊓ ⊔

Let us notice that, due to the conditions (1), from our point of view β(A) may serve instead of α(A) -for each path generated by the expression α(A) there exists a path generated by β(A) such that the multisets of edges visited in both paths are exactly the same (thus the paths are of the same length).

To compute the result for β(A), we process each B i (see Lemma 3) separately and return the minimum of values computed. When computing the result (the shortest path generated by it that visits each vertex an appropriate number of times) for a given B i , the only choices we might have are in those C i,j 's that are built using Kleene's star. For each of them we introduce a single integer variable x j that is used to denote the number of times we take the given fragment of the expression in the path we are to construct. For a given set of values of variables x j , it is easy to compute, for each vertex y of the graph, how many times it is visited in the word, representing a path, generated by B i :

#(y, B i ) = li j=1 #(y, C i,j )
and what is the total length of the word:

len(B i ) = li j=1 len(C i,j ) . If C i,j = a, for a = (v, w, ℓ) ∈ Γ , then #(y, C i,j ) = δ wy len(C i,j ) = ℓ and if C i,j = (a 1 a 2 . . . a p ) * , where a r ∈ Γ for 1 ≤ r ≤ p, then #(y, C i,j ) = x j • p r=1 #(y, a r ) len(C i,j ) = x j • p r=1
len(a r ) .

Here δ xy denotes the Kronecker delta: δ x,x = 1, and δ x,y = 0 for x = y. If values of the variables are not fixed, we can treat #(y, B i ) and len(B i ) as (linear) expressions over those variables. Our goal is, therefore, to minimize the value of len(B i ) under the following constraints on variables x j ∈ Z:

x j ≥ 0 #(y, B i ) ≥ m y for y = 1, 2, . . . , k .
But this is exactly an integer linear programming problem (see Example 1). For a fixed number of variables and constraints it can be solved in polynomial time in the length of the input, see Lenstra's paper [START_REF] Lenstra | Integer programming with a fixed number of variables[END_REF], and even in linear time in terms of the maximum encoding length of a coefficient, see Eisenbrand's paper [START_REF] Eisenbrand | Fast integer programming in fixed dimension[END_REF].

Example 1. Assume that S = {s 1 , s 2 }, m 1 = 2010, m 2 = 30. Note that the set of symbols in the regular expressions α(A) and β(A) is Γ ⊆ {0, . . . , 3} × {0, . . . , 3} × (Z + ∪ {0}). Let

B i = (0, 1, 0)(1, 1, 7) * (1, 2, 3) (2, 1, 2)(1, 1, 7)(1, 2, 3) * (2, 3 , 5)
be a part of the expression β(A) for which we are to compute the shortest path satisfying the occurrence conditions. Observe that we can interpret our task as a graph problem. We are given a directed graph having a form of a directed path (a backbone) with disjoint cycles attached, in which vertices are labeled with indices from the set {0, . . . , 3} and edges are labeled with lengths, as in Fig. 4. In this graph we need to find the length of the shortest path from the vertex labeled 0 to the vertex labeled k + 1 = 3 visiting at least m 1 = 2010 1-labeled vertices and at least m 2 = 30 2-labeled vertices.

In the integer program we introduce two variables x 1 , x 2 that uniquely determine a word generated by B i :

(0, 1, 0)(1, 1, 7) x1 (1, 2, 3) (2, 1, 2)(1, 1, 7)(1, 2, 3)
x2 (2, 3, 5) . The integer program for this example looks as follows:

x 1 , x 2 ≥ 0 1 + x 1 + 2x 2 = #(1, B i ) ≥ m 1 = 2010 1 + x 2 = #(2, B i ) ≥ m 2 = 30
and we are minimizing the expression len(B i ) = 0 + 7x 1 + 3 + 12x 2 + 5 .

To recompute the actual SCS, we choose the one B i that attains the globally smallest value of len(B i ). Note that solving the integer program gives us the values of variables x j , from which we can restore the corresponding word v generated by the regular expression B i simply by inserting the values of x j instead of Kleene's stars, resulting in a polynomial representation of the shortest common superstring.

SUM-SCS(k) problem

Let G be the prefix graph of S = {s 1 , s 2 , . . . , s k }. We are looking for the shortest word containing m occurrences of words from S. Recall that such a word corresponds to the shortest path in G from the source to the destination, traversing m + 1 edges. Let M be the adjacency matrix of G. The length of the shortest path from the vertex 0 to the vertex k + 1 passing through m + 1 edges equals M m+1 [0, k + 1], where M m+1 is the (m + 1) th power of M w.r.t. the min-plus product. M m+1 can be computed in O(k 3 log m) time by repeated squaring, i.e. using identities:

M 2p = (M p ) 2 M 2p+1 = M ⊕ M 2p .
Having computed the described matrices, we can also construct a representation of SCS of size O(poly(n)) by a context-free grammar. The set of terminals

Theorem 1 .

 1 The MULTI-SCS 2 (k) problem can be solved in O(n 2 ) time. The length of the shortest common superstring can be computed in O(n) time, and its compact representation of size O(n 2 ) can be computed in O(n 2 ) time. (The real size of the output could be exponential.)Proof. Let us construct a multigraph G = (V, E), such that each vertex corresponds to a letter of the alphabet Σ, and each edge corresponds to some word s i -(u, v) ∈ E if the word uv is an element of S. Each word s i has a given multiplicity m i , therefore we equip each edge e ∈ E corresponding to s i with its multiplicity c(e) = m i . Using this representation the graph G has size O(k) (|E| = k, and |V | = O(k) if we remove isolated vertices). We refer to such an encoding as to a compact multigraph representation.

Lemma 1 .

 1 has an Eulerian cycle 3: find an Eulerian cycle C in G ′ 4: if E ′ = ∅ then 5: return path P obtained from C by removing one edge from E ′ 6: else 7: return C As a consequence of the following Lemma 1, the smallest cardinality multiset E ′ can be computed in O(|V | + |E|) time. The compact representation of an Eulerian cycle can be computed, by Lemma 2, in O(|V | • |E|) time. This gives us an O(|V | • |E|) = O(n 2 ) time algorithm for the MULTI-SCS 2 (k) problem. ⊓ ⊔ For a given compact representation of a directed multigraph G = (V, E), there exists an O(|V | + |E|) time algorithm for computing the smallest cardinality multiset of edges E ′ , such that the multigraph G ′ = (V, E ∪ E ′ ) has an Eulerian cycle.

Fig. 1 .

 1 Fig. 1. (a) Multigraph G = (V, E) for a set of words S = {ad, ac, ba, bb, bc, ca, db, dc} with a sequence of multiplicities (mi) 8 i=1 = (17, 3, 5, 3, 1, 20, 10, 10). It consists of a single component C with V + (C) = {a, b} and V -(C) = {c, d}. (b) Eulerian multigraph G ′ = (V, E ∪ E ′ ) obtained from G by adding the following minimal multiset of edges: E ′ = {(a, d) • 3, (a, c) • 2, (b, c) • 4}

2 and 3 .Fig. 2 .Fig. 3 .

 323 Fig. 2. Construction of an Eulerian cycle by algorithm EulerianCycle(G)

Fig. 4 .

 4 Fig. 4. Labeled graph corresponding to Bi from Example 1. The variables x1 and x2 from the integer program correspond to the number of times the loop (1 → 1) and the cycle (2 → 1 → 1 → 2) are traversed in the shortest path

Theorem 2 .

 2 MULTI-SCS(k) can be solved in O(poly(n)) time for k = O(1).

is Σ. For each of the matrices M p that we compute, we create an auxiliary matrix K p containing distinct non-terminals of the grammar. If M p (for p > 1) is computed in the above algorithm using M a and M b then we add the following production from K p [i, j]:

where

The production from K 1 [i, j] is defined as:

The starting symbol of the grammar is

Clearly, this representation uses O(k 2 log m) memory and the only word generated by this grammar is the requested SCS. Hence, we obtain the following theorem: