Kim S Larsen
email: kslarsen@imada.sdu.dk

Partially persistent search trees with transcript operations

Keywords: Data structures, Search trees, Persistence, Complexity

When dictionaries are persistent, it is natural to introduce a transcript operation which reports the status changes for a given key over time. We discuss when and how a time and space efficient implementation of this operation can be provided.

Introduction

When balanced binary search trees are made partially persistent using the node-copying method [START_REF] Driscoll | Making Data Structures Persistent[END_REF], the possibility of searching efficiently for information in the past is added to the system. The operations of updating the present version and searching in the present as well as in the past are asymptotically as efficient as in the corresponding normal (non-persistent) binary search tree.

In database applications, it is sometimes desirable to produce transcripts of information change over time. If we wish to obtain a transcript of information related to some key k from version number v 1 to v 2 , this can be obtained by independent search operations in all versions in that interval in time O ph✁ , where h is the maximum height of the search tree in that interval, and p ✂ v 2 ✄ v 1 ☎ 1 is the number of versions between v 1 and v 2 . We discuss when and how this can be reduced to O h ☎ p✁ by maintaining one extra pointer with a version number in each node, without changing the asymptotic complexity of any of the existing operations.

In database applications, search trees are usually leaf-oriented, which means that all keys reside in the leaves, and internal nodes contain routers guiding the search to the correct leaf. Leaves are often of another type than the internal nodes, and contain extra pointers or space consuming values associated with their keys. We remain faithful to this model, and the extra pointer which is introduced only appears in internal nodes. Leaves will contain no extra information compared to the single version scenario.

The complexity of the transcript operation turns out to depend on how often leaves can get new parents during rebalancing. We introduce the concept of search trees with limited leaf action as a necessary and sufficient condition for a balanced search tree scheme to be equipped with an efficient transcript operation using the method outlined in this paper.

The most interesting case to consider is the case where O ph✁ is large, i.e., there are a large number of versions. For the case where we change to a new version whenever a fixed constant number of updates has been carried out (or earlier), we show that the transcript operation can be computed in time O h ☎ p✁ , where h is the height of the tree in version v 1 . If updates in the given tree take time O h✁ , they remain O h✁ . As in [START_REF] Driscoll | Making Data Structures Persistent[END_REF], space consumption is linear in the number of changes made to the structure.

Among the balanced search tree schemes which turn out to have limited leaf action are red-black trees [START_REF] Guibas | A Dichromatic Framework for Balanced Trees[END_REF] and treaps [START_REF] Aragon | Randomized Search Trees[END_REF], for instance. So, here updating becomes O log n✁ (for treaps, expected time) and transcripts O log n ☎ p✁ (for treaps, the log n part is expected time). In the next section, we first define leaf-oriented search trees, then we extend them to become partially persistent, and finally, we include the transcript additions. In the following sections, we discuss correctness, complexity, and future work.

Transcript Trees

When search trees are used in database applications, the trees are usually leaf-oriented. This means that only the leaves contain keys. The internal nodes contain routers, which are of the same type as the keys and which direct the searches to the correct location as usual in a search tree. However, routers need not be present as keys in the tree. This means that we do not have to update routers whenever a deletion takes place. For an internal node, the keys in its left subtree are smaller than or equal to its router, and the keys in its right subtree are larger. A leaf-oriented tree is always a full tree, i.e., every internal node has two children. This simplifies the deletion operation.

Searching and Updating

To insert a key k in the tree, search for k as usual. An unsuccessful search ends up in a leaf, say l. A new internal node u is created in place of l, and l and a new leaf l✝ containing the key k are made the children nodes of u. The one containing the smaller key will be the left child. The router of u is a copy of the key contained in its left child. Thus, there are new pointers in the new node, but only one pointer in the existing structure is changed. See Figure 1 on the following page.

To delete a key k from the tree, first search for k as usual in a search tree. If the key is found in the leaf l, its parent is replaced by the sibling node of l. Again, a node and its pointers are deleted, but only one pointer is changed. See Figure 2 on the next page.

The insertion and deletion operations are called update operations. It is easy to prove that while a router r is present in the tree, no new node with the same router can be created. This is important since otherwise rotations could violate the search tree invariant.

We assume that some scheme for maintaining balanced search trees will be used. Thus, the nodes contain additional fields for registering heights, colors, or other balance information. The update operations may manipulate these fields, and there will be a collection of rebalancing operations, which after each update, by manipulating the fields and applying rotations, will make sure that the balance constraints, if violated by the update, are again fulfilled. We discuss this in greater detail later.

Partially Persistent Search Trees with Transcript Operations

However, we require that any rebalancing operation can be expressed as a constant number of single rotations carried out as described now (see Figure 3 on the following page).

The single rotation can be either right (in the direction of the arrow) or left (in the opposite direction of the arrow). We give the requirements for a right rotation; the other is similar. Assume that the parent of v is a node w, and assume without loss of generality that it points to v via its left pointer. Then carry out v✞ left:=u✞ right; u✞ right:=v; w✞ left:=u.

This could be done differently. However, the whole point is that nodes must keep their identity since we introduce new pointers which should aim at the correct nodes, even when these are moved around by rebalancing operations. Balance information can be updated by the rebalancing operations in any way desired.

Note that this requirement is no (real) restriction. This is exactly the way single rotations are always performed, and double rotations are always expressed such that the result of one equals the result of two consecutive single rotations. In fact, any binary search tree can be constructed from any other binary search tree with the same keys by applying a sequence of single rotations. We do not know of any scheme which does not conform to this requirement, except the ones which apply some form of global rebuilding as in [START_REF] Andersson | Improving Partial Rebuilding by Using Simple Balance Criteria[END_REF][START_REF] Galperin | Scapegoat Trees[END_REF].

Partial Persistence

We now make the search tree partially persistent using the node-copying method [START_REF] Driscoll | Making Data Structures Persistent[END_REF]. A partially persistent structure is a structure which supports multiple versions, such that all versions can be accessed, but only the newest version can be modified. We assume that versions are numbered using consecutive integers. All nodes have a field stating under which version they were created. The structure has a number of entry pointers (pointers to roots of different versions) which also have version numbers.

For balanced search trees, the node-copying method can be used in a simplified form [START_REF] Driscoll | Making Data Structures Persistent[END_REF]. We use an extended version of that simplified form. We retain what is referred to as the copy pointer, equip it with a version number, and update it as in the original method. For completeness, and because we build on top of this basic method, we describe it here, but emphasize that a very similar description has been given in [START_REF] Driscoll | Making Data Structures Persistent[END_REF].

There are three types of information in a balanced search tree: keys, pointers, and balance information. As information considered, we are only interested in the keys. Since we can only update the newest version, balance information is not needed for older versions. We always rebalance after an update, so when we switch to a new version, the older versions will remain balanced forever. So, only keys and pointers from old versions must be kept, and it is safe to overwrite old balance information.

When we insert a new key, we create an entirely new node to put it in. So, no key information is being changed. Instead, it is one pointer in one node that is being changed to include the new node. Similarly, when we delete a key, this is done by changing one pointer to cut out the node, in which the key resides. So, we only need to discuss pointer updates; not key updates.

To avoid copying too many nodes every time a pointer must be changed, nodes have one extra field for a pointer update. So, nodes in the tree have fields: key, left, right, vn, extra, and copy, where "vn" is short for "version number". The field extra is composite, and has the following fields: ptr, dir, and vn for recording the new pointer, which pointer it replaces (dir is Left or Right), and in which version it was done ("ptr" is short for "pointer" and "dir" is short for "direction"). The field copy is also composite with fields ptr and vn.

An update in the newest version i is handled as described now. We explain the action which must be taken for one pointer change. If an update (or a rebalancing operation) involves several pointer changes, the procedure is repeated.

If the node u in which the update is made has version number i, the update overwrites the existing pointer. Otherwise, if the extra field has version number i and its direction field indicates the pointer to be updated, the pointer in the extra field is overwritten.

If neither case applies, there are two possibilities depending on whether or not the extra field has already been used. If it has not, the update is made there, also setting the direction field and setting the version number to i.

Otherwise, a new node v must be made. This is the only case, where the procedure does not terminate immediately. The key and the newest left and right pointers from u are copied into v, i.e., the pointer in the extra field of u and the pointer from u which was not overwritten in the extra field. Then v's version number is set to i and its extra and copy fields to nil. Finally, the copy field in u is set to point to v, and its version number is set to i. Thus, copy pointers link together sequences of nodes which are basically the "same" node at different times. Now, the parent of u must be updated to point to v instead. This is done recursively using the method just outlined, i.e., the effects of an update continue up in the tree along the update path for as long as there are nodes where the extra field has already been used by an earlier version, or has been used in the opposite direction of the update path by the current version. If the root is copied, then a new entry pointer to the new root with version number i is created. For an example, see Figure 4. Nodes, extra pointers (in the middle), and copy pointers (dashed) have version numbers. Thick lines indicate parts of the tree which were present before the operation. The current version number is 3. Searching becomes slightly more complicated after these changes. Searching starts by following an entry pointer. There will not necessarily be an entry pointer for each version. Instead, when accessing version j, the entry pointer with the largest version number i, i ✟ j, should be used.

At each node, a decision to continue the search to the left or the right must be made. As usual, this decision is made by comparing the key to be found with the router (key) in the node. However, when the decision has been made to proceed to the left, for instance, then the newest left pointer no newer than j must be followed, i.e., if the left pointer has been updated in the extra field and the version number of the extra field is at most j, then the pointer in the extra field should be followed. Otherwise, the original left pointer is taken.

The following result, or more general ones, are proven in [START_REF] Driscoll | Making Data Structures Persistent[END_REF].

Theorem 1 When the node-copying method is applied to a pointer structure for which there is an upper bound p on the number of pointers that can point to any one node, then if nodes in the persistent version are equipped with at least p extra pointers, the following holds.

✠

The asymptotic complexity of searching in any version in the persistent structure is equal to the asymptotic complexity of searching in the standard structure corresponding to that version.

✠

The persistence actions carried out after one pointer change are performed in amortized constant time.

✠

When searching in the newest version, only the last node in a copy sequence can be accessed.

Note that in connection with the trees we use here, only the parent of a node can point to that node, so one extra field suffices. Also, since we use only a constant amount of new space in each step, space usage per pointer update is also amortized constant.

With the definitions in this section, the structure is no longer a tree, but a directed acyclic graph. However, we will keep referring to it as a tree.

Transcript Facilitating Additions

In this section, we extend the updating and rebalancing procedures even further. We first describe our goal informally and then we give the exact description of the procedures, the properties of which will be used in the correctness proof later.

The general idea is that if we want to keep track of some key k, then we position ourselves at the internal node under which k is found (or would be inserted). When changing version, from v 1 to v 2 say, the internal node with that property may be deleted, or an insertion or rotation may have the effect that it is now another node which has the given property.

Therefore, whenever we make an update or a rotation, we also build a path from the node with the given property in version v 1 to the one with that property in version v 2 , such that later, during a transcript operation, it will be fast to get to that new node. We make sure the path is protected in the sense that no later pointer updates can alter it.

The result is a tree as in [START_REF] Driscoll | Making Data Structures Persistent[END_REF] with extra pointers and copies of nodes creating protected paths which run through the tree (over time) at the levels just above the leaves.

We now turn to the concrete additions. Note first that when an internal node is deleted, no pointer updates can ever be applied to it again. This means that its copy pointer will never be used. In other words, we are free to use it for other purposes (this is safe since the copy pointer is never used in searching). Additionally, when an insertion or a rotation is carried out, we may trigger a copying of a node which would not have been made at that time in the original method. This means that in contrast to [START_REF] Driscoll | Making Data Structures Persistent[END_REF], we can have several copies of a node with the same version number. These are the only changes we are making. Whenever the copy pointer is set, its version number is also set, and it is set to the newest (that is, the current) version. From now on, we will not mention the version number when discussing the setting of the copy pointer.

For deletion, there are two cases. First assume that both of the children of the internal node u to be deleted are leaves. The deletion is performed, and the copy pointer of u is set to point to the newest copy of the parent of u. Now assume that the internal node to be deleted has only one leaf among its two children. After the deletion has been performed, the copy pointer of u is set as follows. If the leaf is its left child, then its copy pointer is set to point to its in-order internal successor (the left-most internal node in its right subtree). This case is illustrated in Figure 5 on the following page. Note that persistence actions will continue above the node with key 7, but this is not shown. Similarly, if the leaf is its right child, then its copy pointer is set to point to its in-order internal predecessor (the right-most internal node in its left subtree). The successor (or predecessor) is found by a search in the newest version of the structure starting at the internal node to be deleted.

For insertion, we do the following. As described earlier, we first search for the correct leaf, and the only pointer in the existing structure which is changed is the one in the internal node v which points to the leaf in question. We make the insertion as usual for leaf-oriented trees, applying the necessary persistence actions, i.e., v may be copied. When this is completed, we trigger a new copy of v, or of the copy of v, if v has already been copied during the insertion. This last case is illustrated in Figure 6. Note that since the node with key 27 is copied, other actions will take place further up in the tree, but this is not shown. The actions taken for a rotation are similar to those for insertions. First, the rotation is carried out, and all the necessary persistence actions are taken. Then if the right child of u (refer to Figure 3 on page 98) before the rotation was a leaf, we trigger a new copy of the newest version of node u. In general, to make a description which covers left as well as right rotations, if the middle subtree is a leaf, we trigger a new copy. An example of this is given in Figure 7. In that example, no extra pointers were in use before the rotation. Note that persistence actions due to the copying will continue up in the part of the tree above u (not shown).

The Transcript Operation

The transcript operation can now be defined. It takes a key k and two version numbers v 1 and v 2 (with v 1 ✟ v 2 ) as parameters and prints the history of k between these two versions. More precisely, a line is printed for every version, stating whether or not k is in the tree. In a practical application, there would most likely be values associated with each key, and those could be printed as well (these might not be the same every time k appears in the tree).

The implementation is given in Figure 8 on page 107. We explain the ingredients below.

We have mostly used standard notation in the algorithms, but we comment on a few points. We have used an enumeration type with the two values Left and Right. Boolean expressions are evaluated C-style, i.e., they are evaluated from left to right and as soon as the final value of the whole expression can be deduced, evaluation is aborted. When we use the expression (b ? e 1 : e 2 ), the boolean expression b is evaluated first. If it evaluates to true, then the result of the whole expression is the result of evaluating e 1 . Otherwise, it is the result of evaluating e 2 . In order to avoid too many details, we assume that the tree is always non-empty.

We assume that we have a function Leaf which decides if a node is a leaf, and a function Entry which given a version number, returns the entry pointer to be used.

The function Find finds the parent of a given key in a given version. This is simply a search, except that we return the parent of the key. The leaf in the direction we would search to find k (or rather, to check whether or not k is in the tree at the time) is referred to as the leaf possibly containing k. Find calls Go which takes one step down in the tree by going left or right as appropriate. Assuming that we are located at the parent of the leaf possibly containing k, Status returns the information as to whether or not k is present.

Transcript works by repeatedly calling Advance. The function Advance is called with a key k, a node u, and a version number i. Except for the first call, the assumption is that the information returned by the previous call to Advance was from u in version i ✄ 1, i.e., u was the internal node which could have a leaf child containing k. Advance finds the next similar node in version i, and returns information on the status of k at that time, as well as the node.

Correctness

The only non-trivial operation is the function Advance. We must argue that it always advances (so termination is guaranteed) and not too much (such that information is overlooked).

When searching through version i by starting at the entry pointer, one will see version i as it appeared when we switched to the next version. However, the current version can keep changing right until we switch. This complicates the search by Advance even after we have switched to a new version because we do not enter via the entry pointer. Thus, we may see parts of version i which were temporary, and which would never be found when entering "correctly". This is the reason for the while loop in function Advance. Whenever we use Find, we are searching in version i as it appeared at some point; not necessarily in its final appearance. For instance, several deletions could be made in the same version so it may be necessary to follow the copy pointer several times.

The reason for triggering a node copying in connection with insertions and rotations is that the parent of the leaf possibly containing k changes. By triggering a copying of the node which used to be the parent, we ensure that no later operations can prevent us from accessing the new parent. Thus, we build a protected path from the parent of the leaf possibly containing k in one version to the (possibly new) parent in the next.

Theorem 2 If we are at the node u equal to Find Entry i ✄ 1✁ ☛✡ k ✡ i ✄ 1✁ , i ☞ 1, then Advance k ✡ u✡ i✁ will bring us to v equal to Find Entry i✁ ✌✡ k✡ i✁ .

Proof Assuming that Advance brings us from u to v, it follows a path in the tree; this is not necessarily a direct path from one node to a descendant since copy pointers can also be followed. We call this the advance path. The proof is by induction. However, we strengthen the induction hypothesis by adding that no pointer changes can be made to nodes on the advance path except the last.

We prove by induction in the number of modifications in the tree by version i or greater that Advance will find the node v. Actually, since nodes are never physically deleted, and pointers are only overwritten if created by the version performing the update, updates in versions greater than i cannot affect the path, so it is sufficient to consider updates by version i.

The base case is when no modifications have taken place. In that case, the start node u and end node v are identical, so Advance will certainly find v (immediately after switching to version i, searching in version i is identical to searching in version i ✄ 1). Additionally, the advance path consists of a single node (which is then last), so the second part of the hypothesis follows trivially.

Assume that some operation changes the advance path. By induction, the change is made by altering or adding a pointer in the last node on the path. We consider the operations in turn.

Assume that an insertion changed the advance path, and assume without loss of generality that the leaf possibly containing k (before the insertion) is to the left. If the insertion is also made to the left, the advance path will continue first by either following the left pointer (if the node in question is from version i), the extra pointer, or, if that was already used, by following the copy pointer and then the left pointer. This brings us to the new internal node which, by the insertion, has become the new parent of the leaf possibly containing k.

Since a new copy is triggered as the last action taken during an insertion, and since updates are always performed in the newest nodes, none of the pointers described in the above can ever be altered. Thus, it is still the case that no pointer changes can be made to nodes on the advance path except the last.

If the insertion is made to the right, then only the copy pointer will be followed (possibly twice) and we are again at the correct location. Now, we assume that a deletion makes a change to the last node u on the advance path. If u is the internal node which is deleted, the copy pointer is set to point to the correct next location (since the location is actually found by a search in the newest version), and since a deleted node can never be accessed by an updating operation again, no changes can be made to nodes on the advance path except the last. If u is the parent of the internal node to be deleted, the advance path is either not changed (if the extra pointer was used for the update), or the copy pointer from u to the newest version of u becomes part of the advance path.

Finally, we must consider rebalancing operations. As required, they consist of a number of single rotation. Thus, we only need to consider one single rotation. Assume that a single rotation (Figures 3 on page 98 and 7 on page 102) makes a change to the last node on the advance path. If v in Figure 3 on page 98 is the last node, since it keeps it leaf (C), the path is either not changed or it is extended with one copy pointer. For the node u, the situation is similar if A is the leaf possibly containing k. So, assume that B is the leaf in question. This is exactly the case where a copy of u is triggered after the rotation as shown in Figure 7 on page 102. Thus, the new pointer in u leading to the new parent of the leaf possibly containing k cannot be altered again. Thus, except for the new last node (v), nodes on the advance path cannot be changed.

✍ ✎ 4 Complexity

The most interesting case to consider is the one where there are many versions, since that is when searching from an entry pointer through each version would be very time consuming. We assume that after a fixed constant number of updates (or earlier) and the rebalancing operations caused by the updates, we change to a new version. We consider the behavior of Advance under that restriction.

Complexity of Transcript

Since a copy pointer which is set up during a deletion points to a node which was in the tree at the time (though it may be from an older version), any additional copy pointers from there must be at least as new. This is also the case for copy pointers created by insertions. Since there are only a constant number of updates, the function Advance can follow such pointers at most a constant number of times to get from one version to the next.

Rebalancing does not necessarily behave that well. In the following, we consider restrictions on the behavior of rebalancing which lead to the best possible complexities.

A rotation as described earlier which triggers a copying of a node, because the middle subtree is a leaf l, is referred to as an expensive rotation, and the rotation is said to be expensive due to the leaf l. Definition 1 A balanced binary search tree scheme is said to have limited leaf action if there exists a constant c such that for any leaf l and any update, the number of expensive rotations due to l, which are carried out in response to the update, is bounded by c.

✍ ✎

If a balanced search tree scheme has limited leaf action, then Advance will find the correct node in constant time, since, referring to the proof of Theorem 2 on the page before, the advance path is extended with only a constant number of edges for each insertion, deletion, and expensive rotation, and we change version after a bounded number of updates. Thus, the complexity of the transcript operation is O log n ☎ p✁ , where n is the number of elements in the start version for the reporting.

It is now interesting to determine which schemes have limited leaf action. Red-black trees [START_REF] Guibas | A Dichromatic Framework for Balanced Trees[END_REF] do, since, as it is pointed out in [START_REF] Driscoll | Making Data Structures Persistent[END_REF], rebalancing after an update consists of at most three rotations (single or double). The remaining rebalancing operations are recolorings.

Also treaps [START_REF] Aragon | Randomized Search Trees[END_REF] have limited leaf action. Only single rotations are used in treaps, and in a sequence of rotations following an insertion, it is always the same node which is the bottom-most node of the two internal nodes in the rotation. It is easy to show that after it has lost at most two leaf children, its children are going to be internal nodes from that point on. Deletions can be viewed as reverse insertions.

AVL-trees [START_REF] Adel'son-Vel | An Algorithm for the Organisation of Information[END_REF] and BB[α]-trees [START_REF] Nievergelt | Binary Search Trees of Bounded Balance[END_REF][START_REF] Blum | On the Average Number of Rebalancing Operations in Weight-Balanced Trees[END_REF][START_REF] Mehlhorn | Sorting and Searching, volume 1 of Data Structures and Algorithms[END_REF] also have limited leaf action. As soon as one gets just some fixed constant distance up towards the root from the place of an update, then the relationship between heights and sizes, respectively, of subtrees implies that none of the involved subtrees can be leaves.

Other Complexity Considerations

Searching in a transcript tree is clearly of the same asymptotic complexity as in [START_REF] Driscoll | Making Data Structures Persistent[END_REF].

For updates, the additions only increase the complexity by a constant factor, since the work carried out in connection with pointer updating and triggering of copies, by Theorem 1 on page 99, is amortized constant per pointer change. Though setting the copy pointer in connection with a deletion requires a search, this action is taken in connection with an update, so the total complexity of updates remains bounded by the height of the tree.

If the transcript operation is implemented using binary search trees without balance constraints, the complexity of the transcript operation becomes O h ☎ p✁ , where h is the height of the first version from which we report, and updates become O h✁ , where h is the height of the tree at the time of the update.

From the discussion above, it also follows that search trees where the number of pointer changes in response to an update is amortized constant will use space only linear in the number of updates. This applies to red-black trees and BB[α]-trees, for instance. The expected number of rotations carried out in response to an update in a treap is two, so space consumption for treaps is expected linear.

Concluding Remarks

The status of a key is not necessarily changed in every version. Thus, when following a copy pointer, we may skip over a large number of versions. This can be exploited to give a running time which can sometimes be significantly better. The algorithm would then only print a line whenever the status of the key had changed. It would be interesting to investigate this behavior more closely; both theoretically, but also empirically under some average use of search trees.

A chronological transcript involving more than one key could be produced by merging separate transcripts. However, Transcript has been expressed via Advance which reports one change at a time. Thus, the total chronological transcript can be produced directly by maintaining a priority queue with an entry for each key and the version number as the priority. This is more "on-line", i.e., it would start printing out the transcript earlier.

If the number of pointers is not a concern, then there is an easier solution: decide that the standard search tree should have all the parents of leaves connected in a doubly linked list. By [START_REF] Driscoll | Making Data Structures Persistent[END_REF], we obtain the optimal asymptotic amortized complexities. However, more pointers are needed. The doubly linked list uses additional pointers, but since nodes can now have more than one predecessor (there are now 3), nodes must be equipped with predecessor pointers (see [START_REF] Driscoll | Making Data Structures Persistent[END_REF]) such that all nodes referring to an updated node can themselves be updated. Additionally, there must be more extra fields corresponding to the number of predecessors (the amortized constant results from [START_REF] Driscoll | Making Data Structures Persistent[END_REF] depend on this). Though the amortized time complexity would be the same, the worst case complexity of an update would be Ω n✁ instead of O logn✁ obtained by a balanced transcript tree. This happens when all the extra fields in all the nodes in the doubly linked list have been used. In that case, every node in the list must be copied.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Insertion of 33 into a leaf-oriented tree.

Fig. 3 :

 3 Fig. 3: Single rotation (to the right).

Fig. 4 :

 4 Fig. 4: Inserting 21.

Fig. 5 :

 5 Fig. 5: Deleting the key 8 from a transcript tree.

Fig. 6 :

 6 Fig. 6: Insertion of key 33 into a transcript tree.

Fig. 7 :

 7 Fig. 7: Right rotation in a transcript tree.

University of Wisconsin at Madison. Supported in part by SNF (Denmark), in part by NSF (U.S.) grant CCR-9510244, and in part by the ESPRIT Long Term Research Programme of the EU under project number 20244 (ALCOM-IT). 1365-8050 c ✆ 1999


Anna Frid
email: frid@math.nsc.ru

Applying a uniform marked morphism to a word †

Keywords: D0L words, HD0L words, subword complexity, functions of a word

We describe the relationship between different parameters of the initial word and its image obtained by application of a uniform marked morphism. The functions described include the subword complexity, frequency of factors, and the recurrence function. The relations obtained for the image of a word can be used also for the image of a factorial language. Using induction, we give a full description of the involved functions of the fixed point of the morphism considered.

Introduction

Different languages and words generated by morphisms play a significant part in the formal language theory. Such languages include D0L languages (and infinite words) which are obtained by iterating a morphism, HD0L languages (and words) which are obtained from a D0L language (respectively, a D0L word) by application of another morphism, and others.

To emphasize the importance of such languages, the theory of avoidable patterns can be mentioned. Examples of infinite words on a given alphabet which avoid a pattern are usually constructed as D0L words or HD0L words. Only recently it has been proved [START_REF] Cassaigne | Unavoidable binary patterns[END_REF] that there exists a pattern which is avoidable on the binary alphabet but is not avoidable in any binary D0L word. However, it is still unknown if every k-avoidable pattern is avoidable by some HD0L word on the k-letter alphabet.

We consider a general case of simple application of a morphism to a word. Imposing some restrictions to the morphism considered (it must be uniform, marked, and circular on the initial word), we find explicit formulas linking the quantitative characteristics of the initial word and its image. This approach is valid also for the application of a morphism to a language (see Subsection 7.1) and allows to give a full description of these characteristics of a D0L word (see Subsection 7.2).

This research can be considered as an extension and generalization of papers [START_REF] Frid | The subword complexity of fixed points of binary uniform morphisms[END_REF][START_REF] Frid | On Uniform DOL words[END_REF] (devoted to the subword complexity) and [START_REF] Frid | On the frequency of factors in a D0L word[END_REF] (devoted to the frequency of factors), where the properties Anna Frid of a D0L word have been considered. However, here a new approach is used based on the direct relations between sets of allowable words of given lengths. This approach can be applied to find many functions of a language; some of them are considered here.

Preliminaries

Uniform marked morphisms

We consider two alphabets Σ 1 = {a 1 , . . . , a q } and Σ 2 and a morphism ϕ : Σ * 1 → Σ * 2 ; clearly, ϕ can be extended to the set Σ ω 1 of all (right) infinite words on Σ 1 . We call images ϕ(a i ) of letters blocks; the length of a finite word u is denoted by |u|. A morphism is called non-erasing if all its blocks are non-empty; i.e., if for all letters a i ∈ Σ 1 we have |ϕ(a i )| > 0. We suppose ϕ to be non-erasing.

The (finite or infinite) word we consider is denoted by w; its image is denoted by ϕ(w). Note, that since ϕ is non-erasing, ϕ(w) is finite if and only if w is finite.

We say that a word u is allowable in a word v if it occurs in v as a factor: v = s 1 us 2 for some words s 1 and s 2 . The set of words allowable in w is denoted by A, and the set of words allowable in ϕ(w) is denoted by B. Our goal is to describe the relationship between A and B.

A morphism ϕ is called uniform if all its blocks are of the same length: |ϕ(a i )| = m for all a i ∈ Σ 1 ; m is called the block length of ϕ. If ϕ is uniform, then the length of the image of a word u depends only on the length of u; so, there exists a direct relationship between lengths of elements of A and of elements of B. That is why in this paper we consider uniform morphisms.

A morphism is called marked if all the images of letters begin with distinct symbols and end with distinct symbols; note that a morphism ϕ : Σ

* 1 → Σ * 2 can be marked only if |Σ 1 | ≤ |Σ 2 |.
If ϕ is marked, then every block together with its inverse image is uniquely determined by its first (or last) symbol.

Circularity on w

For a word u = u 0 u 1 . . . u n+1 ∈ Σ + 1 , where u i ∈ Σ 1 , we define Ψ jk (u) ∈ Σ + 2 as the word obtained from ϕ(u) by erasing j symbols from the left and k symbols from the right. We need only the case when we do not erase full blocks; i.e., when 0 ≤ j < |ϕ(u 0 )| and 0 ≤ k < |ϕ(u n+1 )|.

The triplet s = (u, j, k), where u = u 0 u 1 . . . u n+1 ∈ Σ + 1 , and j and k are integers, is called an

interpretation of a word v ∈ Σ + 2 if 0 ≤ j < |ϕ(u 0 )|, 0 ≤ k < |ϕ(u n+1 )|, and v = Ψ jk (u)
. The word u is called the ancestor of the interpretation s and is denoted by a(s).

If in addition u ∈ A, then s is called an interpretation of v on w. Note, that a word can admit several interpretations, and even several interpretations on w with the same ancestor. The set of all the interpretations of a word v is denoted by I(v), and the set of its interpretations on w is denoted by I w (v).

The notions of an interpretation and its ancestor were introduced by F. Mignosi and P. Séébold in [START_REF] Mignosi | If a D0L language is k-power-free then it is circular[END_REF].

Remark 1 I w (v) = ∅ if and only if v ∈ B. Let u ∈ B. A pair of words (u 1 , u 2 ) is called a synchronization point of u (for ϕ) on w if u = u 1 u 2 and ∀t 1 , t 2 ∈ Σ * 2 ∀v ∈ A ∃v 1 , v 2 ∈ A : [t 1 ut 2 = ϕ(v) =⇒ (v = v 1 v 2 , t 1 u 1 = ϕ(v 1 ), u 2 t 2 = ϕ(v 2 ))].
The notion of synchronization point was introduced by J. Cassaigne in [START_REF] Cassaigne | An algorithm to test if a given circular HD0L-language avoids a pattern[END_REF]. Put very simply, a synchronization point notes the point in u where the demarcation between blocks necessarily takes place in an occurrence of u in ϕ(w).

The word u ∈ B is called circular on w if it has a synchronization point on w.

Remark 2 If ϕ is uniform, then in a circular word all the demarcations between blocks are determined.

Remark 3 If ϕ is marked, then circularity of a word u ∈ B means that it admits a unique interpretation on w: as we know a synchronization point, we can reconstruct every block of this interpretation from its first (or last) symbol. The ancestor of this interpretation is called the ancestor of the word u and is denoted by a(u). We call u a descendant of a(u).

The morphism ϕ is called circular on w with synchronization delay equal to L = L(ϕ, w) if every word allowable in ϕ(w) of length at least L is circular. This notion was inspired by the papers of Mignosi and Séébold [START_REF] Mignosi | If a D0L language is k-power-free then it is circular[END_REF] and Cassaigne [START_REF] Cassaigne | An algorithm to test if a given circular HD0L-language avoids a pattern[END_REF].

Let ϕ be a uniform marked morphism with block length equal to m, and let ϕ be circular on w with synchronization delay equal to L. In addition to L, we use another parameter of circularity called structure ordering number; it is denoted by K = K(ϕ, w) and defined as the least integer satisfying the inequality m(K -1) + 1 ≥ L. In what follows, we mostly use the synchronization delay through the mediation of the structure ordering number.

Example: circularity of the Thue-Morse morphism

Let us consider the famous Thue-Morse morphism ϕ T M on the two-letter alphabet Σ = {a, b}:

ϕ T M (a) = ab ϕ T M (b) = ba
Clearly, ϕ T M is a uniform marked morphism. Our goal is to find the set C T M of words such that ϕ T M is circular on a word w if and only if w ∈ C T M .

Let every power of both symbols occur in w; i. e., let for all n a n ∈ A, b n ∈ A. In this case, the word (ab) n is allowable in ϕ(w) and non-circular for all n. Actually, it admits two interpretations on w: (a n , 0, 0) and (b n+1 , 1, 1). So, there exist arbitrarily long non-circular words in B, and

w ∈ C T M .
Conversely, if a n+1 is not allowable in w for some n, then w ∈ C T M ; more precisely, ϕ is circular on w with synchronization delay L ≤ 2n + 1.

Actually, we shall prove that a word u ∈ B of length 2n + 1 is always circular on w. If two equal symbols occur successively in u, then there is a demarcation between blocks between them; so, two successive equal symbols determine a synchronization point, and u is circular.

If there are no successive equal symbols in u, then u = (ab) n a or u = (ba) n b. In both cases, u admits two interpretations; the ancestor of one of them is a n+1 , and the ancestor of the other is b n+1 . Since a n+1 is not allowable in w, and u is allowable, u admits one interpretation on w (with ancestor b n+1 ) and is circular.

Anna Frid

So, a word u ∈ B of length 2n+1 is always circular, and ϕ is circular on w with synchronization delay L ≤ 2n + 1.

Analogously, ϕ is circular on w if for some n the word b n+1 is not allowable in w. So, we have described the set C T M :

C T M = {w|∃n : (a n ∈ A) ∨ (b n ∈ A)}.
3 Basic relations

On the number of occurrences

For words u and v, we denote the number of occurrences of u in v by L u (v). The following easy lemma is valid for an arbitrary morphism ϕ : Σ * 1 → Σ * 2 and is very useful in the subsequent discussion.

Lemma 1 For all u ∈ Σ * 1 and v ∈ Σ * 2 L v (ϕ(u)) = s∈I(v) L a(s) (u) (1)
Proof. Every occurrence of v in ϕ(u) corresponds to an occurrence of the ancestor of certain its interpretation in u, and vice versa.

Remark 4 As it was noticed in Remark 3, if ϕ is marked, and v is circular, then v admits a unique interpretation with the ancestor which can be denoted by a(v). In this case, Equality (1) can be rewritten as

L v (ϕ(u)) = L a(v) (u). (2)

Sets of allowable words of given lengths

Hence-forward, unless otherwise specified, ϕ is a uniform morphism with block length equal to m, and w is an arbitrary (finite or infinite) word.

In what follows, we obtain some relations linking quantitative characteristics of sets A and B of allowable words. We shall also strengthen these relations by assuming that ϕ is marked and circular on w.

To state the next results, we need to introduce some more notations. First, recall that for a word u = u 0 . . . u n , u i ∈ Σ 1 , the word Ψ jk (u) is obtained from ϕ(u) by erasing j symbols from the left and k symbols from the right; here we need only the case when we do not erase complete blocks, i. e., when 0 ≤ j, k < m.

For a set M ⊂ Σ * 1 and for j, k ∈ {0, . . . , m -1}, we define the set Ψ jk (M ) naturally:

Ψ jk (M ) = {Ψ jk (u)|u ∈ M }.
Clearly, in general case

|Ψ jk (M )| ≤ |M |. The set of words of length n allowable in w (in ϕ(w)) is denoted by A(n) (respectively, by B(n)): A(n) = {u||u| = n, u ∈ A}, B(n) = {u||u| = n, u ∈ B}.
Now we can formulate the main theorem. As its corollaries, we shall obtain a variety of relations among the quantitative characteristics of A and B.

Theorem 1 Let N = m(n -1) + ∆ + 1 for some n > 0 and some ∆ ∈ {0, . . . , m}. Then

B(N ) = m-∆ i=1 Ψ i-1,m-i-∆ (A(n)) ∆ i=1 Ψ m-∆+i-1,m-i (A(n + 1)) . (3)
If in addition ϕ is marked and circular on w with the structure ordering number equal to K, and n ≥ K, then all the maps Ψ jk above are one-to-one on the sets A(n) (and, respectively, A(n + 1)), and all the mentioned sets Ψ jk (A(n + l)), l ∈ {0, 1}, are mutually disjoint.

Proof. Let us consider a word v ∈ B(N ). Since it is allowable in ϕ(w), it occurs as a factor in some word ϕ(u), where u ∈ A. We choose u as short as possible, that is, v must contain parts of the first and the last blocks of ϕ(u). In other terms, we choose such u ∈ A that v = Ψ jk (u) for some j, k ∈ {0, . . . , m -1}. It can be easily seen that the length of u must be equal to n or to n + 1. More exactly, either u ∈ A(n), and then v ∈ Ψ jk (A(n)), where j

+ k = m -∆ -1 (this is possible only if ∆ < m), or u ∈ A(n + 1), and then v ∈ Ψ jk (A(n + 1)), where j + k = 2m -∆ -1 (this is possible only if ∆ > 0). On the other hand, if a word v is an element of Ψ i-1,m-i-∆ (A(n)) for some i ∈ {1, . . . , m -∆} (or an element of Ψ m-∆+i-1,m-i (A(n + 1)) for i ∈ {1, . . . , ∆}), then v is obviously allowable in ϕ(w), and |v| = m(n -1) + ∆ + 1 = N . So, v ∈ B(m(n -1) + ∆ + 1)
, and the equality is proved. Now let ϕ be marked and circular on w with structure ordering number K, and let n ≥ K. Sets Ψ jk (A(n + l)), l ∈ {0, 1}, mentioned in the equation ( 3) can intersect only because of some of their elements having several interpretations; by the same reason, it may happen that a map Ψ jk is not one-to-one on A(n+l). However, since |v| = N = m(n-1)+∆+1 ≥ m(K -1)+1 ≥ L, every word v ∈ B(N ) is circular. Since ϕ is marked, v admits a unique interpretation. Thus, the theorem is proved.

Remark 5 Here and in Theorems 2 and 3 some redundancy exists in the range of values of ∆. It would be sufficient to consider only ∆ ∈ {0, . . . m -1} or ∆ ∈ {1, . . . , m}. The latter version will be more useful for us, but we do not want to loose the case of N = m(K -1) + 1.

In what follows, we derive some corollaries of Equalities (1) and ( 2) and Theorem 1 concerning functions of w and ϕ(w).

Subword complexity

In this section, we study the subword complexity functions of w and ϕ(w). The subword complexity f s (n) of a word s counts the number of distinct words of length n which are allowable in s. This function of infinite words has been studied in numerous papers; see, for instance, the survey [START_REF] Allouche | Sur la complexité des suites infinies[END_REF] by J.-P. Allouche.

In our terms, the subword complexity functions of w and ϕ(w

) are f w (n) = |A(n)| and f ϕ(w) (n) = |B(n)|.
Here we derive a corollary of Theorem 1 which expresses the subword complexity of ϕ(w) in terms of the subword complexity of w.

Anna Frid

Theorem 2 Let ϕ be a uniform morphism with block length equal to m. Let N = m(n-1)+∆+1 for some n > 0 and some ∆ ∈ {0, . . . , m}. Then

f ϕ(w) (N ) ≤ (m -∆)f w (n) + ∆f w (n + 1).
If in addition ϕ is circular on w and marked, and n ≥ K, then equality holds:

f ϕ(w) (N ) = (m -∆)f w (n) + ∆f w (n + 1). ( 4
)
Proof. Using Equality (3), we obtain that

f ϕ(w) (N ) = |B(N )| ≤ m-∆ i=1 |Ψ i-1,m-i-∆ (A(n))| + ∆ i=1 |Ψ m-∆+i-1,m-i (A(n + 1))| ≤ (m -∆)|A(n)| + ∆|A(n + 1)| = (m -∆)f w (n) + ∆f w (n + 1).
Clearly, if the maps Ψ jk above are one-to-one on the respective sets A(n) and A(n + 1), and the images Ψ jk (A(n + l)), l ∈ {0, 1}, are mutually disjoint, then all the inequalities of the latter derivation become equalities. Thus, it follows from Theorem 1 that if ϕ is marked and circular on w with structure ordering number equal to K, and n ≥ K, then Equality (4) holds.

Remark 6 Note that the subword complexity function of ϕ(w) does not depend on ϕ itself or even on the alphabet Σ 2 . The only necessary parameters of ϕ are its block length and the structure ordering number of ϕ on w.

Example: the subword complexity of images of Sturmian words

An infinite word w is called Sturmian if its subword complexity is f w (n) = n + 1; as f w (1) = 2, the alphabet of a Sturmian word is binary: Σ 1 = {a, b}. It can be easily seen that the subword complexity function of Sturmian words is the least possible for a non-ultimately periodic word.

Sturmian words were introduced in the classical paper [START_REF] Morse | Symbolic dynamics II: Sturmian trajectories[END_REF] and have been extensively studied; see, for example, the survey [START_REF] Berstel | Recent results on Sturmian words, Developments in Language Theory II[END_REF]. There exists a variety of equivalent definitions of Sturmian words; however, we are interested just in the subword complexity.

A famous example of a Sturmian word is the Fibonacci word w F = abaababaabaababaababa . . . .

Let w be a Sturmian word and ϕ be a circular on w uniform marked morphism; let its block length be equal to m and the structure ordering number be equal to K(ϕ, w) = K. It follows from Theorem 2 that for every n ≥ K and for every ∆ ∈ {0, . . . , m -1} the following equality holds:

f ϕ(w) (m(n -1) + ∆ + 1) = (m -∆)(n + 1) + ∆(n + 2);
in other terms, for every n ≥ m(K -1) + 1

f ϕ(w) (n) = n + 2m -1.
This equality conforms Proposition 8 in [START_REF] Cassaigne | Sequences with grouped factors, in: Developments in Language Theory III[END_REF] which states that a morphic image of a Sturmian word is quasi-Sturmian, i.e., has subword complexity f (n) = n + c for some c and all n ≥ n 0 .

In particular, let ϕ be the Thue-Morse morphism ϕ T M (see Example 2.3); its block length is m = 2. Without loss of generality we can state that the word bb never occurs in a Sturmian word (since in a non-ultimately periodic binary word ab and ba must occur, and f w (2) = 3). So, it follows from Example 2.3 that the Thue-Morse morphism is circular on a Sturmian word with the synchronization delay L ≤ 3 (in fact, L = 3). Structure ordering number is K + 2, and for n ≥ 3 = m(K -1) + 1 we have

f ϕ(w) (n) = n + 3.
In particular, this is the subword complexity of the word ϕ T M (w F ) = abbaababbaabbaababbaababba . . . .

Frequency of allowable words and frequency tables

In this section, we deal with the frequency of factors in an infinite word s on an alphabet Σ. Let s(n) denote the prefix of length n of s; for every word u ∈ Σ + its frequency µ s (u) in s is denoted as a limit

µ s (u) = lim n→∞ L s(n) (u) n (5)
Of course, this definition is valid only if this limit exists. The set of frequencies µ s determines a probability measure on the Borel subsets of Σ w : the frequency µ s (u) can be considered as the measure of the cylinder set [u] = {s|s = us ′ , s ′ ∈ Σ w }.

Frequency of a word in ϕ(w)

Our goal is to relate the frequencies of words in ϕ(w) to the frequencies of words in w. Here we assume that w is an infinite word on Σ, and ϕ is a uniform morphism with block length equal to m.

Lemma 2 If for every word u ∈ Σ + 1 its frequency µ w (u) exists, then for every v ∈ Σ + 2 its frequency in ϕ(w) exists and is equal to

µ ϕ(w) (v) = 1 m s∈Iw(v) µ w (a(s)). (6)
Proof. Since ancestors s ∈ I(v) \ I w (v) do not occur in w, and ϕ(w(n)) = ϕ(w)(mn), it follows from Lemma 1 that for every n > 0

L ϕ(w)(mn) (v) = s∈Iw(v) L w(n) (a(s)).
Dividing this equality by mn and passing to the limit n → ∞, we obtain that

µ ϕ(w) (v) = lim n→∞ L ϕ(w)(mn) (v) mn = lim n→∞ s∈Iw(v) L w(n) (a(s)) mn = 1 m s∈Iw(v) lim n→∞ L w(n) (a(s)) n = 1 m s∈Iw(v)
µ w (a(s)).

A similar formula for a fixed point of a non-erasing morphism was proved in [START_REF] Frid | On the frequency of factors in a D0L word[END_REF].

Using Formula (6), one can compute the frequency of a word in ϕ(w) from the frequency in w of the ancestors of its interpretations. Note, that if ϕ is marked and circular on w, and the length of v exceeds the synchronization delay, then v has the only ancestor a(v) (see Remark 3), and Formula (6) can be rewritten as

µ ϕ(w) (v) = 1 m µ w (a(v)) (7)
In what follows, we use Theorem 1 and Equation [START_REF] Dekking | On the Thue-Morse measure[END_REF] to describe the set of frequencies of words of given length in ϕ(w) in terms of frequencies of words in w. To do it, we introduce the notion of frequency tables.

Frequency tables

Let s be an infinite word with the subword complexity equal to f (n). A frequency table on s is a table

F = k 1 k 2 . . . k l µ 1 µ 2 . . . µ l ,
where

k i ≥ 0, 0 ≤ µ i ≤ 1, µ i = µ j for i = j,
k i µ i = 1, l i=1 k i = f (n)
, and F describes the frequencies of allowable words of length n in s.

It can be easily seen that adding columns of the kind 0 µ (zero columns) and permuting columns do not change the meaning of a frequency table. We do not distinguish tables which differ by the order of columns or by zero columns. The sum F + F ′ of two frequency tables

F = k 1 k 2 . . . k l µ 1 µ 2 . . . µ l and F ′ = k ′ 1 k ′ 2 . . . k ′ l ′ µ ′ 1 µ ′ 2 . . . µ ′ l ′
is defined as the table obtained from

k 1 k 2 . . . k l k ′ 1 k ′ 2 . . . k ′ l ′ µ 1 µ 2 . . . µ l µ ′ 1 µ ′ 2 . . . µ ′ l ′
by junction of columns corresponding to the same frequency: instead of two columns k i µ and

k ′ j µ , the column k i + k ′ j µ should be written.
For a frequency table

F = k 1 k 2 . . . k l µ 1 µ 2 . . . µ l ,
and for p ≥ 0, r > 0, we define a table T p r (F ) as follows:

T p r (F ) = pk 1 pk 2 . . . pk l 1 r µ 1 1 r µ 2 . . . 1 r µ l .
Theorem 3 Let the frequency µ w be defined for every word on Σ 1 , and let ϕ be a uniform marked morphism circular on w. If n exceeds the structure ordering number of ϕ on w, ∆ ∈ {0, . . . , m}, and N = m(n -1) + ∆ + 1, then

F ϕ(w) (N ) = T m-∆ m (F w (n)) + T ∆ m (F w (n + 1)). ( 8
)
Proof. The statement of the theorem follows immediately from Theorem 1 and Formula ( 7): each word u ′ ∈ A of length n with frequency µ ′ in w is an ancestor of m -∆ words of length N allowable in ϕ with frequency 1 m µ ′ : they are words Ψ i-1,m-i-∆ (u ′ ), where i ∈ {1, . . . , m -∆}.

Analogously, each allowable in w word of length n + 1 and of frequency µ ′′ is an ancestor of ∆ words of length N allowable in ϕ(w); each of them has frequency 1 m µ ′′ . Since every allowable in ϕ(w) word of length N has an ancestor of length n or n + 1 allowable in w, the theorem is proved.

Example: frequency of factors in the Thue-Morse image of the Fibonacci word

Let us compute the set of frequencies of factors in the word ϕ T M (w F ) (see Examples 2.3 and 4.1) using frequency of factors in the Fibonacci word w F described by M. Dekking in [START_REF] Dekking | On the Thue-Morse measure[END_REF].

Let P l denote the lth Fibonacci number: P 0 = 0, P 1 = 1, P k+1 = P k + P k-1 for k ≥ 2; let p = √ 5 -1 2 . Every length n can be uniquely decomposed as n = P l + r + 1, where r ∈ {0, . . . , P l-1 -1}.

In terms of frequency tables, the frequency of factors of length n in w F described in [START_REF] Dekking | On the Thue-Morse measure[END_REF] is

F w F (n) = P l-1 -r P l-2 + r r p l-2 p l-1 p l .
This table means that P l-1r of n + 1 allowable words of length n have frequency p l-2 , P l-2 + r words have frequency p l-1 , and r words have frequency p l . Note, that F w F (n + 1) looks analogously even if r is maximal (r = P l-1 -1):

F w F (n + 1) = P l-1 -r -1 P l-2 + r + 1 r + 1 p l-2 p l-1 p l .
Now, let us apply Theorem 3 to find frequencies of factors in the Thue-Morse image ϕ T M (w F ) of the Fibonacci word. Let N = 2n -1 + ∆ for ∆ ∈ {0, 1}; then N = 2P l + r ′ + 1, where r ′ = 2r + ∆ ∈ {0, . . . , 2P l-1 -1}. Equality (8) applied to N is

F ϕ T M (w F ) (N ) = T 2-∆ 2 (F w(F ) (n)) + T ∆ 2 (F w F (n + 1)) = (2 -∆)(P l-1 -r) (2 -∆)(P l-2 + r) (2 -∆)r 1 2 p l-2 1 2 p l-1 1 2 p l + + ∆(P l-1 -r -1) ∆(P l-2 + r + 1) ∆(r + 1) 1 2 p l-2 1 2 p l-1 1 2 p l = 2P l-1 -r ′ 2P l-2 + r ′ r ′ 1 2 p l-2 1 2 p l-1 1 2 p l .
We have found the set of frequencies of factors of given length in the Thue-Morse image of the Fibonacci word.

The recurrence function and its relatives

Let A s (n) be the set of all words of length n which are allowable in a word s. The recurrence function R s (n) of s can be defined as the least length satisfying the following condition: all the words of A s (n) are allowable in every word u ∈ A s (R s (n)). In other terms, R s (n) is the size of the smallest window which contains all the elements of A s (n) whatever its position in s.

The recurrence function is the classical tool associated with infinite words. Recently, two more functions R ′ s (n) and R ′′ s (n) slightly different from R s (n) have been defined. The function R ′ s (n) introduced by J.-P. Allouche and M. Bousquet-Mélou in [START_REF] Allouche | On the conjectures of Rauzy and Shallit for infinite words[END_REF] is the length of the shortest prefix of s containing all the words of A s (n); and the function R ′′ s (n) introduced by J. Cassaigne in [START_REF] Cassaigne | Sequences with grouped factors, in: Developments in Language Theory III[END_REF] is the length of the shortest allowable word in which every word from A s (n) is allowable.

Clearly,

R ′′ s (n) ≤ R ′ s (n) ≤ R s (n).
The recurrence function is finite only if s is uniformly recurrent, i. e., if for every word u allowable in s the distance between two successive occurrences of u in s is bounded; if it is not for some u of length n, R s (n) is defined to be +∞. The other two functions are defined everywhere. Unlike R ′ s , the functions R s and R ′′ s depend in fact only on the set of words allowable in s. Let the word w be infinite. Here we use Equality [START_REF] Allouche | On the conjectures of Rauzy and Shallit for infinite words[END_REF] and Theorem 1 to relate these functions of ϕ(w) to the corresponding functions of w; we assume here, that ϕ is a uniform marked morphism circular on w.

Theorem 4 Let w be an infinite word, and ϕ be a uniform marked morphism circular on w. Let n exceed the structure ordering number of ϕ on w. Then for every ∆ ∈ {1, . . . , m} and for

N = m(n -1) + ∆ + 1 R ϕ(w) (N ) = mR w (n + 1) -m + ∆.
Proof. Let R w (n + 1) be finite. It can be easily seen that the recurrence function R(n) is directly connected with the maximal distance between two adjacent occurrences of a word of length n. The latter function is equal to R(n)n + 1 and is non-decreasing.

Note that ∆ here is chosen to be larger than 0. Thus, it follows from Theorem 1 that every word of A of length n + 1 has a descendant of B of length N . Since ϕ is uniform, and due to circularity, if the length between two occurrences of a word in w is l, then the length between corresponding occurrences of its descendants in ϕ(w) is ml. In terms of the recurrence function it means that

R ϕ(w) (N ) -N + 1 = m(R w (n + 1) -n).
Substituting to this equality the expression for N , we obtain the statement of the theorem. Now let R w (n + 1) be infinite. It means that there exist as long as is wished words of A in which not all the words of A(n + 1) occur. But due to Theorem 1, their images cannot contain all the words of B(N ); thus, R ϕ(w) (N ) is also infinite.

Theorem 5 Under conditions of Theorem 4,

R ′ ϕ(w) (N ) = mR ′ w (n + 1) -m + ∆.
Proof. Let u be the prefix of w of length R ′ w (n + 1): u = w(R ′ w (n + 1)). By the definition of the function R ′ w , all the elements of A(n + 1) (and, consequently, of A(n)) are allowable in u, and the suffix v 1 of u of length n + 1 does not occur earlier in it. However, since the suffix v 0 of u of length n is the prefix of some allowable word of length n + 1, it occurs somewhere else in u.

Since N is larger than the synchronization delay of ϕ on w, every word allowable in ϕ(w) of length N is a descendant of some word of length n or n + 1. Since ∆ ≥ 1, it follows from Equality (3) that every word allowable in w of length n + 1 (and in particular v 1 ) is an ancestor of some word of length N allowable in ϕ(w).

It follows from Theorem 1 applied to u that ϕ(u) contains as factors all the elements of B(N ); so, R ′ ϕ(w) (N ) ≤ mR ′ w (n + 1). On the other hand, unlike the descendants of v 0 which occur somewhere earlier in ϕ(w), each of the descendants of v 1 (including Ψ m-1,m-∆ (v 1 )) occurs in ϕ(w) only once. Thus, the last word from B(N ) which has a unique occurrence in ϕ(u) is Ψ m-1,m-∆ (v 1 ), and so R ′ ϕ(w) (N ) = mR ′ w (n + 1)m + ∆. As for the function R ′′ , to find the relationship between that of w and of ϕ(w), we need some additional properties of w (or, more generally, of the language A) to be satisfied.

Namely, a language L ⊂ Σ * is called prolongable if for every word u ∈ L there exist symbols a, b ∈ Σ such that au ∈ L, ub ∈ L.

A word u ∈ A is called (right) special if it can be prolonged to the right to an element of A by at least two different letters: ua, ub ∈ A for some a, b ∈ Σ 1 , a = b. Note that a sequence w is non-ultimately periodic if and only if for each n there exists a special word of length n.

Theorem 6 Under conditions of Theorem 4, let the language A be prolongable and w be nonultimately periodic. Then

R ′′ ϕ(w) (N ) = mR ′′ w (n + 1) -2m + 2∆.
Proof. Let us call a word u ∈ A(R ′′ w (n + 1)) trivial if it begins and ends with the same word s ∈ A(n) which does not occur anywhere else in u: u = su ′ = u ′′ s, but u = u 1 su 2 for u 1 , u 2 ∈ Σ + 1 . Lemma 3 There exists a non-trivial word in A(R ′′ w (n + 1)) containing all the words of A(n + 1). Proof. Let us choose a word v ∈ A(R ′′ w (n + 1)) containing all the words of A(n + 1): by the definition of R ′′ w , such a word exists. If it is non-trivial, then the lemma is proved; otherwise, u = su ′ = u ′′ s for some s ∈ A(n). Since s does not occur anywhere in the middle of u, it can be prolonged to the right only by the first letter of u ′ (which is denoted by a). Thus, s is not special, and neither is u: the only word of uΣ 1 ∩ A is ua.

Let s = bs ′ for b ∈ Σ 1 . Consider the word s ′ u ′ a ∈ A(R ′′ w (n + 1)). It contains all the words of A(n+1): all of them except sa are factors of s ′ u ′ , and sa is a suffix of s ′ u ′ a. If s ′ u ′ a is non-trivial, then the lemma is proved; otherwise, it is not special, and we can repeat the procedure and obtain from s ′ u ′ a a new word by erasing the first letter and adding the allowable letter to the right.

However, if we could repeat this procedure infinitely many times, if would mean the existence of an infinite suffix of w not containing special words of length R ′′ w (n + 1). This is possible only if w is ultimately periodic which contradicts with the conditions of the theorem.

Since m > 0, it follows from Theorem 1 that a word cannot contain the elements of B(N ) if its ancestor does not contain all the words of A(n + 1). We must look for shortest words containing all the elements of B(N ) among descendants of words of A(R ′′ w (n+1)) containing all the elements of A(n + 1).

Let a word u 0 ∈ A(R ′′ w (n + 1)) contain all the words of A(n + 1) and be non-trivial. By the definition of R ′′ w , its prefix and suffix of length n + 1 do not occur anywhere else in it, but since A is a prolongable language, the prefix and the suffix of u 0 of length n occur in it somewhere else; since u 0 is non-trivial, each of them occur in the middle of u 0 (even if they are equal). So, to obtain the shortest descendant v 0 of u 0 containing all the words of B(N ), we can erase all the symbols from the left (and from the right) of ϕ(u 0 ) which occur only in the descendants of length N of these prefix and suffix of length n. These symbols are the first and the last m -∆ symbols of ϕ(u 0 ); so, v 0 = Ψ m-∆,m-∆ (u 0 ).

On the other hand, if u 1 ∈ A(R ′′ w (n + 1)) contains all the words of A(n + 1) and is trivial, we must be more cautious with erasing letters from the left and from the right of its ϕ-image, and the descendants of u 1 containing all the words of B(N ) are longer than v 0 . Thus,

R ′′ ϕ(w) (N ) = |v 0 | = mR ′′ w (n + 1) -2m + 2∆.

Example: On words with ultimately grouped factors

In [START_REF] Cassaigne | Sequences with grouped factors, in: Developments in Language Theory III[END_REF], J. Cassaigne introduced a notion of words with ultimately grouped factors: a word w if said to have ultimately grouped factors if R ′′ w (n) = f w (n) + n -1 for all n ≥ n 0 (w). He proved also that every quasi-Sturmian word (i.e., a word whose subword complexity is f w (n) = n + c for some c and for all n ≥ n 1 ) has ultimately grouped factors.

Let w be a non-ultimately periodic word with ultimately grouped factors; let the language of factors of w be prolongable, and a uniform marked morphism ϕ be circular on w. If n exceeds the structure ordering number of ϕ on w and n 0 (w), and N = m(n -1) + ∆ + 1 for ∆ ∈ {1, . . . , m}, then it follows from Theorem 6 and Formula (4) that

R ′′ ϕ(w) (N ) = m(F w (n + 1) + n) -2m + 2∆ = f ϕ(w) (N ) + N -1 + (m -∆)(f w (n + 1) -f w (n) -1).
Thus, ϕ(w) has ultimately grouped factors if and only if f w (n + 1) = f w (n) + 1 for all large enough n; i. e., if and only if w is a quasi-Sturmian word.

7 Some generalizations

A generalization to factorial languages

It can be easily seen that sets of allowable words of given length in fact do not depend on the words w and ϕ(w), but rather on the sets A and B. The same can be said on the subword complexity, the recurrence function, and its relative R ′′ . But the initial language A can be defined not only as the set of words which are allowable in a word w. The only condition it must satisfy is factually closure under taking a factor: if a word u is an element of A, then all its factors are also elements of A. In other terms, A must be a factorial language on Σ 1 .

For a factorial language A, we define its factorial image B ⊂ Σ * 2 as the least factorial language containing the set ϕ(A) = {ϕ(u)|u ∈ A}. Properties of A and B are similar to those of sets of allowable words of w and ϕ(w) respectively.

Replacing everywhere in Subsection 2.2 w by A and ϕ(w) by B, we obtain the necessary definitions concerning circularity on a factorial language A (see also Subsection 3.2 in [START_REF] Cassaigne | An algorithm to test if a given circular HD0L-language avoids a pattern[END_REF]).

The subword complexity function f L (n) of a factorial language L is defined naturally as the number of its distinct elements of length n.

It can be easily seen that after replacing circularity on w by circularity on A, we can extend Theorem 1 to an arbitrary factorial language A. The same can be done with Theorem 2 which is a direct corollary of Theorem 1; in the relations between subword complexity values, f w should be replaced by f A and f ϕ(w) should be replaced by f B .

As it was mentioned in Section 6, the recurrence function R and its relative R ′′ depend in fact not on the words w and ϕ(w) themselves, but on the sets of allowable words. So, similar functions can be defined on an arbitrary factorial language L: R L (n) is the least length such that every element of L of length R L (n) contains as factors all the elements of L of length n, and R ′′ L (n) is the length of the shortest element of L which contains all the words from L of length n. On a factorial language, both these functions can be not everywhere defined; if the length from a definition does not exist, the corresponding function is supposed to be infinite.

Let A be a factorial language and B be its factorial image. After replacing the occurrences of w by those of A, and the occurrences of ϕ(w) by those of B, Theorem 4 can be extended to a factorial language A and its factorial image B. To extend Theorem 6, we must just add the conditions for A to be prolongable and to have infinitely many special elements (the latter condition serves instead of non-periodicity of w).

Anna Frid

A generalization to D0L words

Let the alphabets Σ 1 and Σ 2 be equal; i.e., let ϕ be a morphism ϕ : Σ * → Σ * . If the block ϕ(a) begins with a for some symbol a ∈ Σ, then ϕ admits a fixed point w which can be obtained as a limit w = lim In [START_REF] Queffélec | Substitution dynamical systems -spectral analysis[END_REF], the probability measure defined by the set of frequencies of factors in a D0L word has been studied, and a sufficient condition of the existence of such a measure was given.

A fixed point w of a morphism ϕ is called circular if ϕ is circular on w. An easy-to-check criterion of circularity of a fixed point of a uniform marked morphism was proved in [START_REF] Frid | On Uniform DOL words[END_REF].

If w is a circular fixed point of a uniform marked morphism ϕ, then the formulas obtained above can be applied to w many times, until the length n considered is less than the structure ordering number of ϕ on w.

More precisely, let K be the structure ordering number of ϕ on w; let m be the block length of ϕ. For every n ≥ K there exists a unique triplet of decomposition parameters (p(n), k(n), ∆(n)) such that p(n) ≥ 0 k(n) ∈ {K, . . . , m(K -1)} ∆(n) ∈ {1, . . . , m p(n) }, and n = m p(n) (k(n) -1) + ∆(n).

Theorem 7 For all n ≥ K f w (n + 1) = (m p(n) -∆(n))f w (k(n)) + ∆(n)f w (k(n) + 1),

R w (n + 1) = m p(n) (R w (k(n) + 1) -1) + ∆(n),

R ′ w (n + 1) = m p(n) (R ′ w (k(n) + 1) -1) + ∆(n), (10)
R ′′ w (n + 1) = m p(n) (R ′′ w (k(n) + 1) -2) + 2∆(n); [START_REF] Morse | Symbolic dynamics II: Sturmian trajectories[END_REF] if the frequency is defined for every factor of w, then

F w (n + 1) = T m p(n) -∆(n) m p(n) (F w (k(n))) + T ∆(n) m p(n) (F w (k(n) + 1)). ( 13
)
Proof. The proof is carried out by induction on p(n). If p(n) = 0, then Formulas ( 9)-( 13) are obviously correct. The induction step is given by Theorems 2-6.

As it follows from Lemma 3 of [START_REF] Mignosi | If a D0L language is k-power-free then it is circular[END_REF], a circular fixed point of a uniform morphism cannot be ultimately periodic. On the other hand, it is not difficult to show that the language of factors of a fixed point of marked morphism is prolongable. That is why we do not need any additional conditions for Formula [START_REF] Morse | Symbolic dynamics II: Sturmian trajectories[END_REF].

Equality [START_REF] Frid | On Uniform DOL words[END_REF] was proved in detail in [START_REF] Frid | On Uniform DOL words[END_REF]. Equality [START_REF] Queffélec | Substitution dynamical systems -spectral analysis[END_REF] was proved in [START_REF] Frid | On the frequency of factors in a D0L word[END_REF].

i→∞ ϕ i

 i (a); if ϕ is non-erasing and ϕ(a) = a, then w is an infinite word satisfying the equality w = ϕ(w). Fixed points of morphisms are called also D0L words. They have been studied in numerous papers and contain many famous examples, including the Fibonacci word (which is the fixed point of the morphism ϕ F defined by ϕ F (a) = ab, ϕ F (b) = a) and the Thue-Morse word which is a fixed point of the Thue-Morse morphism ϕ T M (see Example 2.3).

Acknowledgements

I am grateful to the anonymous referee who mentioned flaws in what is now Theorems 4 and 6, and showed the way to correct them.

† Supported in part by RFBR (grant 96-01-01800) and Federal Aim Program "Integration" (grant 473). 1365-8050 c 1999 Maison de l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France