Frédérique Bassino

Marie-Pierre Béal

Dominique Perrin

Fr Ed Erique Bassino

Super-state automata and rational trees

come

Introduction

We introduce in this paper the notion of super-state automata, which can informally be stated as follows. Let A be a nite automaton or a multigraph (we forget the labeling). A super-state automaton, constructed from the automaton A, has states composed of unordered lists of states of A such that the list of followers of all states of a super-state can be partitioned in super-states. Compared to the automaton A, a super-state automaton often appears to be a loss of information. Let us now assume that A has an initial Figure 1: Tree associated to 3z 2 (z 2 ) state i. We consider the tree that is a development of A from the initial state: each node of this tree is associate with one state of A, and the sons of a node are associated to the followers of the state associated to their father, the root being associated to the initial state of A. This tree is rational as it has only a nite number of non-isomorphic subtrees. The tree developed from the super-automaton also appears to be a loss of information compared to the previous one. Nevertheless, it keeps some interesting properties of the ordinary tree like the number of leaves or the number of nodes at each height. As its subtrees are identi ed to super-states, it can moreover have a more compact representation.

We use these notions of super-states to solve an open question about enumerative sequences of integers that can be realized as the enumerative sequences of leaves in a rational tree. We also give an alternative proof to a result proved in 4] about enumerative sequences of integers that can be realized as the enumerative sequences of nodes in a rational tree. These problems are linked with coding and symbolic dynamics. They can be considered as extensions of results of Hu man, Kraft, McMillan and Shannon on source coding.

Let s be an N-rational sequence of nonnegative numbers, that is a sequence s = (s n ) n 1 such that s n is the number of paths of length n going from an initial state to a nal state in a nite multigraph or a nite automaton. We say that s satis es the Kraft inequality for a positive integer k if P n 1 s n k n 1. If s is the enumerative sequence of leaves of a rational k-ary tree, then s satis es Kraft's inequality for the integer k.

In the rst part of this paper, we study the converse of the above property. Consider for example the series s(z) = 3z 2 =(1 z 2 ). We have s(1=2) = 1 and we can obtain s as the enumerative sequence of the tree of Figure 1 associated with the pre x code X = (aa) (ab + ba + bb) on the binary alphabet fa; bg.

Known constructions allow one to obtain a sequence s satisfying Kraft's inequality as the enumerative sequence of leaves of a k-ary tree, or as the enumerative sequence of leaves of a (perhaps not k-ary) rational tree. These two constructions lead in a natural way to the problem of building a tree both rational and k-ary. This question was already considered in 12], where it was conjectured that any N-rational sequence satisfying Kraft's inequality is the enumerative sequence of leaves of a k-ary rational tree. The case of strict inequality was solved in 4]. In this paper, we completly settle the conjecture and the proof which we give works in both cases.

Proofs and algorithms used to establish the results are based on automata theory and on the theory of nonnegative matrices. Unlike in 3], we do not use any symbolic dynamic construction like state-splitting. But we use basic results of the Perron-Frobenius theory, and a very simple lemma, that we call the "weight lemma", due to B. Marcus in 9] (see also 8]), and already used by R. Adler, D. Coppersmith and M. Hassner in 1] to construct some nite-state codes with sliding block decoders for constrained channels.

A variant of the problem consists in replacing the enumerative sequence of leaves by the enumerative sequence of all nodes. Soittola ( 15]) has characterized the series which are the enumerative sequence of nodes in a rational tree. The problem of a similar characterization for rational k-ary trees remains open in the general case. In 3], this question was solved for N-rational series t that satisfy some necessary conditions, two trivial ones: t 0 = 1, 8n 1; t n kt n 1 , and a less trivial one, but proved to be necessary in 3]: the convergence radius of t is strictly greater than 1=k, and another condition: t has a primitive linear representation. In this case there is a k-ary rational tree whose enumerative sequence of nodes by height is t.

In the second part of this paper, we give two new proofs of this result. Again, the proofs are no more based on state-splitting, but on the notion of super-state automata. With this new method, the trees obtained in a lot of examples have smaller representations.

Super-state automata

Let A be a nite state automaton (Q; E), where Q is the set of states and E the set of edges. In this paper, the labeling alphabet will always be reduced to one letter, say z, but some de nitions can be extended to more general automata. So the labeling will not be represented on pictures. Automata can hence be seen as multigraphs, since several edges, (equally labeled), going from a state p to state q, may exist. Some initial or nal states may also be sometimes speci ed. We now give some basic de nitions about trees. A tree T on a set of nodes N with a root r is a function T : N frg ! N which associates to each node distinct from the root its father T(n), in such a way that, for each node n, there is a nonnegative integer h such that T h (n) = r. The integer h is the height of the node n. A tree is k-ary if each node has at most k sons.

A leaf is a node without son. A tree is said to be rational if it admits only a nite number of non-isomorphic subtrees.

Let A be an automaton with one initial state. We say that a tree is the development of the automaton A if it is constructed as follows: its root corresponds to the initial state of the graph. If a node of the tree at height n corresponds to a state i in the graph which has r outgoing edges ending in states j 1 ; j 2 ; : : : ; j r , it admits r sons at height n + 1, each of them corresponding respectively to the states j 1 ; j 2 ; : : : ; j r of the graph. The development of an automaton is a rational tree. We label the nodes with their corresponding state in A. Example Let us consider the 6-state automaton A of Figure 2, with state 1 as initial state. The development T of A is represented in Figure 3. If we now put in 3 boxes, respectively, the unordered sequences of states (1), (2; 5) and (4; 3; 6), we get the tree T 0 represented in Figure 4, that admits only 3 non-isomorphic subtrees.

This example introduces the notion of super-states and super-state automaton. In the previous example, the tree T 0 is a loss of information compared to tree T. But it is possible to keep in it informations like the number of nodes, or leaves at each height, or, more generally, the number of nodes that have a particular property, at each height. The gain can be, like here, a more compact representation, since we have transformed a 6-state automaton into a 3-super-state one. It can also be, as we shall see later, a way to construct rational trees that satisfy some properties. In general, a super-state automaton associated to an automaton A is an automaton B, whose states, called super-states, are chosen among unordered (or commutative) t-uples (t 1) (q 1 ; q 2 ; : : :q t ) of states of A, and where the edges are obtained as follows. If q is a state of A, we denote by u q the unordered uple obtained by concatenation of the ending states of edges of A going out of state q. If (q 1 ; q 2 ; : : :q t ) is a super-state, we denote by u (q 1 ;q 2 ;:::qt) the unordered concatenation of all u q 1 ; u q 2 ; : : : ; u qt . We then par- tition u q 1 ; u q 2 ; : : : ; u qt into unordered uples that are super-states, provided that such a partition exists. After the choice of the partition, we de ne the output edges of state (q 1 ; q 2 ; : : :q t ) in B as the edges of a multigraph ending in the super-states of the partition. If a super-state u appears r times in the decomposition, we have r edges from (q 1 ; q 2 ; : : :q t ) to u in the multigraph.

Note that these edges are de ned up to the choice of the partition.

In order to establish the rst result, we shall use a particular class of super-state automata, constructed from an automaton A whose states have a positive integral valuation. We denote by v(q) the valuation of a state q. We also choose and x a positive integer m.

A super-state automaton, according to the valuation v and the integer m, is an automaton B = (Q 0 ; E 0 ) whose super-states are unordered (or commutative) t-uples (q 1 ; q 2 ; : : :q t ) of states of A, with 1 t m. We extend the de nition of the valuation to the super-states, and, more generally, to any t-uple of states, as being the sum of the valuations of their components:

v((q 1 ; q 2 ; : : : ; q t )) = t X j=1 v(q j ):

Let (q 1 ; q 2 ; : : :q t ) be a super-state. With the previous notations, u (q 1 ;q 2 ;:::qt) denotes the commutative concatenation of u q 1 ; u q 2 ; : : : ; u qt , where u q is the unordered list of all followers of state q. Now we partition u (q 1 ;q 2 ;:::qt) in several unordered t-uples (1 t m), in such a way that all parts, but possibly one, have a valuation divisible by m. Such a partition can be obtained by applying the following simple lemma, which is a key point in the state-splitting process used to construct coding schemes for constrained channels (see 8] and 5]):

Lemma 1 (weight lemma) Let v 1 ; v 2 ; : : : ; v m be positive integers. Then there is a subset S f1; 2; : : : ; mg such that P q2S v q is divisible by m.

Proof: The partial sums v 1 , v 1 +v 2 , v 1 +v 2 +v 3 , : : :, v 1 +v 2 + +v m either are all distinct (mod m), or two are congruent (mod m). In the former case, at least one partial sum must be congruent to 0 (mod m). In the latter, there are 1 p < r m such that v 1 + v 2 + + v p v 1 + v 2 + + v r ( mod m) Hence v p+1 + v p+2 + + v r 0 (mod m).

The partition in super-states can be then obtained as follows: if u (q 1 ;q 2 ;:::qt) has less than or exactly m (unordered) components, there is nothing to do. If not, consider the rst m ones (r 1 ; r 2 ; : : : ; r m ). By the weight lemma, there is a subset S of f1; 2; : : : ; mg such that P i2S v(r i ) is divisible by m. The t-uple composed of the r i , with i 2 S, is a super-state that is the rst part of the partition. The process is iterated with the remaining components of u (q 1 ;q 2 ;:::qt) . We either get a decomposition in super-states whose valuation are all equal to zero modulo m, or a decomposition in super-states whose all but one valuations have this property, the last one being equal to a non-null value modulo m. After the choice of such a partition, we de ne the output edges in B of state (q 1 ; q 2 ; : : :q t ) as the edges of a multigraph ending in the super-states of the partition.

One can here remark that the automaton B is a nite state automaton since there is only a nite number of super-states. The t-uples are always unordered. This means that all components commute. A state of A can also appear several times in a same super-state as di erent components.

Example The super-state automaton B in Figure 6 is associated to the automaton A of Figure 5. (We only represent the part accessible from state 1). The valuation of states are represented in squares and the integer m is equal to the valuation of state 1, that is 3. This section is devoted to basic de nitions about rational sequences. A minimal background about the Perron-Frobenius theory of nonnegative matrices is also given.

De nitions and background

We consider sequences of nonnegative numbers. Such a sequence s = (s n ) n 0 will be said to be N-rational if s n is the number of paths of length n going from a state in I to a state in F in a nite directed graph G, where I and F are two special subsets of states, the initial and nal states respectively. We say that the triple (G; I; F) is a representation of the sequence s. This de nition is usually given for the series P n 0 s n z n instead of the sequence s. Any N-rational sequence s satis es a recurrence relation with integral coe cients. It is however not true that a sequence of nonnegative integers satisfying a linear recurrence relation is N-rational (see 7] page 93).

A well known result in automata theory allows us to use a particular representation of an N-rational sequence s. One can choose a representation (G; i; F) of s with a unique initial state i, such that no edge is entering state i and no edge is going out from any state of F. Such a representation is called a normalized representation. Moreover, it is possible to choose the set of nal states reduced to one state (see for example 13] page 14).

If T is a tree, we denote by l(T) its enumerative sequence of leaves by height, that is, the sequence of numbers s n , where s n is the number of leaves at height n. If T is a rational tree, this sequence is N-rational.

The sequence s = l(T) of a k-ary tree is the length distribution of a pre x code over a k-letter alphabet. The associate series s(z) = P n 0 s n z n satis es then the Kraft inequality: s(1=k) 1. We shall say that the Kraft strict inequality is satis ed when s(1=k) < 1. The equality is reached when each node of the tree has exactly zero or k sons. Conversely, the McMillan construction establishes that for any series s satisfying the Kraft inequality, there is a k-ary tree such that s = l(T). Moreover, if the series satis es the Kraft equality, then the internal nodes will have exactly k sons. But the tree obtained is not rational in general.

It is easy to see that an N-rational sequence s is the enumerative sequence of leaves of a rational tree. This one can be obtained by developing a normalized representation of s (see section 2). The leaves of this tree correspond to the nal states of the normalized representation. The maximal number of sons of a node is then equal to the maximal number of edges going out from any state of the graph of this representation.

Even if the sequence s satis es the Kraft inequality, the above construction does not lead in general to a k-ary rational tree. The aim of the rst result of this paper is to get a k-ary rational tree T such that s = l(T).

This result was conjectured in 12] and proved in 4] in the case of strict inequality. We shall settle it here in all cases by making use of super-state automata. Unlike the construction we gave in 4] and 3] to solve the case of strict inequality, this new method does not use any state splitting process or any symbolic dynamic construction. This proof appears to be better than the previous one for two reasons. First, it allows to solve the case of equality. Second, the rational tree obtained has, in a lot of cases, a more compact rational representation.

Approximate eigenvector

Let s be an N-rational sequence and let (G; i; F) be a normalized representation of s. If we identify the initial state i and all nal states of F in a single state still denoted i, we get a new graph denoted G, which is strongly connected. The sequence s is then the length distribution of the paths of rst returns to state i, that is of nite paths going from i to i without going through state i. Using the terminology of symbolic dynamics, the graph G can be seen as an irreducible shift of nite type (see, for example, 5], 6] or 8]).

We denote by M the adjacency matrix associated to the graph G, that is the matrix M = (m ij ) 1 i;j n , where n is the number of nodes of G and where m ij is the number of edges going from state i to state j. By the Perron-Frobenius theorem (see 8]), the nonnegative matrix M associated to the strongly connected graph G has a positive eigenvalue of maximal modulus denoted by , also called the spectral radius of the matrix. Actually, only depends on the series s, since 1= is the minimal modulus of the poles of 1=(1 s). It is known that the series s satis es Kraft's strict inequality s(1=k) < 1 (resp. equality s(1=k) = 1) if and only if < k (resp. = k).

The dimension of the eigenspace of is equal to one. There is a positive eigenvector (componentwise) associated to . When is an integer, the matrix admits a positive integral eigenvector. When < k, where k is an integer, the matrix admits a k-approximate eigenvector, that is, by de nition, a positive integral vector v with Mv kv.

We shall compute approximate eigenvectors for the irreducible graphs G associated to normalized representations (G; i; T) of sequences. We associate to each node of G a value equal to the corresponding component of the approximate eigenvector of the graph G. The initial and the nal states will have same value since they correspond to the same state of G. The computation of an approximate eigenvector can be obtained by the use of Franaszek algorithm (see for example 4]).

Enumerative sequence of leaves

We now state and prove, by the use of super-state automata, the rst result about the enumerative sequences of leaves of rational trees: Theorem 1 Let s = (s n ) n 1 be an N-rational sequence of nonnegative integers et let k be an integer such that P n 1 s n k n 1. Then there is a k-ary rational tree such that s is the enumerative sequence by height of its leaves.

Proof: We consider an N-rational sequence s and an integer k such that P n 1 s n k n 1. We begin with an automaton A = (G; i; F), which is a normalized representation of s. We denote by M the adjacency matrix of G, and by its spectral radius. Hence k. We compute a k-approximate eigenvector v = (v 1 ; v 2 ; : : : ; v n ) t of the graph G. By de nition, we have Mv kv. We consider v as a valuation, denoted by v, of the states of A. We de ne a super-state automaton B associated to the automaton A, the valuation v, and the integer (used for the congruence) m = v i , where i is the initial state of A. We consider now the part of B accessible from the initial super-state which has, as unique component, the initial state of A.

Let u be a super-state. Recall that v(u) is the sum of the valuations of all components of u. If u is composed of n j states j of A, we have v(u) = P 1 j n n j v j . We associate to each super-state u another integer, denoted by w(u), and de ned by: w(u) = dv(u)=me:

Note that w(i) = 1.

Let us now suppose that u has t outgoing edges ending in the super-states u 1 ; : : : ; u t . The sum of the valuations of u 1 ; : : : ; u t is equal to P 1 j n n j (Mv) j .

As Mv kv, we have (Mv) j kv j ; 8j. We get:

t X j=1 v(u j ) kv(u); t 1 X j=1 v(u j )=m + v(u t )=m kv(u)=m;
By construction of the super-state automaton, v(u j )=m is an integer for 1 j (t 1). Hence we have:

t 1 X j=1
v(u j )=m + dv(u t )=me kdv(u)=me:

Finally, we obtain: t X j=1 w(u i ) kw(u)

We now consider the development of the multigraph B. In order to get a k-ary rational tree, admitting s as enumerative sequence of leaves, we associate to each super-state u, at any height, r = w(u) nodes. Since r nodes at height l have at most kr sons at height l + 1, corresponding to the nodes associated to the super-states followers of u, it is possible to associate to each one k sons at the next height. The initial super-state itself corresponds to one node, the root of the tree. The tree is then k-ary.

The case of equality in the Kraft inequality appears to be just a particular case of the above construction. It means that we can only consider superstates whose valuation is divisible by m. The vector v is then an eigenvector: Mv = kv. If a super-state u has t outgoing edges ending in the super-states u 1 ; : : : ; u t , by construction of the super-state automaton, the valuations v(u 1 ), v(u 2 ); : : : ; v(u t 1 ) of the super-states are equal to zero modulo m.

As Mv = kv, v(u t ) also is divisible by m. Therefore the valuations of all super-states in the tree are divisible by m.

We choose to always leave alone the nal states of A in a super-state. This is possible since their valuation is equal to v(i) = m. The leaves of the tree are then the nodes corresponding to a nal state of A.

As there is only a nite number of super-states, the tree is rational.

Example Let s be the series de ned by: s(z) = z [START_REF] Adler | Algorithms for sliding block codes[END_REF] (1 z 2 ) + z 2 (1 5z 3 ) :

A normalized representation of s is given by the automaton A of Figure 5 (p. 7). In this gure, the valuation v(q) of a state q is given in the square besides the representation of the state. Note that the nal state 4 has same valuation (v(4) = 3) as the initial state 1.

A k-ary rational tree T, whose enumerative sequence of leaves is s, is given in Figure 7. In this gure, the components of the super-states are given inside the states. The number of small black balls above a super-state u is the number w(u) = dv(u)=3e of nodes of the tree represented by u. The nal state 4 corresponds to the leaves of the tree.

Enumerative sequence of nodes

In this section, we give two new proofs of the existence of a k-ary rational tree whose enumerative sequence of nodes by height is an N-rational sequence t that satis es some necessary conditions like t 0 = 1 and 8n 1, t n kt n 1 , its convergence radius strictly greater than 1=k, and another one: t has a primitive linear representation. This result has been obtained in 3] by making use of dynamic operations as an extended notion of statesplitting. The alternative proofs we give here are based on the construction of a super-state automaton. The rst one does not lead, in general, to an easier construction, but it appears to be very e cient in a lot of cases.

The construction which we obtain with the second proof is always simpler than the one obtained with the proof given in 3]. The trees which we have obtained in the examples with this new method have very compact representations.

Let t be an N-rational series. A linear representation of t is a triple (l; M; c), where l is a nonnegative integral row vector, c is a nonnegative integral column vector, and M is a nonnegative integral matrix, with: 8n 0; t n = lM n c: The linear representation is said to be irreducible (resp. primitive) if M is an irreducible (resp. primitive) matrix. Recall that a nonnegative matrix is irreducible if for all indices i; j, there is an integer m such that (M m ) ij > 0.

The matrix is primitive if there is an integer m such that M m > 0. Equivalently, the adjacency matrix of a strongly connected graph G is irreducible, and it is primitive if, moreover, the g.c.d of lengths of cycles in G is 1.

Let M be a n n primitive matrix whose spectral radius is < k, where k is a positive integer. Let a positive real such that < < k. We will denote by S and S k the following sets of nonnegative real vectors: S = fv 2 (R + ) n j Mv vg S k = fv 2 (R + ) n j Mv kvg:

We have S S k . Furthermore, the two sets are two simplex cones. As a consequence, they both satisfy the following properties:

v 2 S ) 8 2 R + ; v 2 S; (1) v; v 0 2 S ) v + v 0 2 S: (2)
Using the above notations, we state and prove the following lemma: Lemma 2 There is a nite subset P of integral vectors of the greater cone S k such that all integral vectors of the smaller one S is the sum of vectors of P.

This means that the integral vectors of the big cone are nitely generated by integral vectors of the small one. The set P constitutes a Petri net for which all integral points of S are accessible (see 14] for these notions).

In the geometrical proof below, we shall denote by v a point of (R + ) n . If v and w are two points, (w v) can be seen either as a point or as the vector going from v to w. Proof: Let r be a positive integer. We denote by H r the hyperplane of points v such that v n = r. As the simplex S and S k are cones, the hyperplanes that limit them are not parallel to H r .

As < k, there is a large enough r such that for each (real) point p in H r \S , one can nd an integral point u in H r \S k , such that u 0 = p+(p u) belongs to H r \ S .

We denote by P the nite set of all integral points v = (v 1 ; : : : ; v n ) of S k located under the hyperplane H 2r , that is such that v n 2r. We are going to show that all integral points of S are nitely generated by P.

Let us assume that the property is false, and denote by w an integral point of S which is not the sum of integral points of P. Suppose that it is one of the closest points to the hyperplane H r that has this property. Then w does not belong to P, and its last component is greater then 2r. Let p be the intersection of H r and the semi-line de ned by the vector w and the origin. Let u and u 0 be de ned as previously. We set w 0 = w u. Then w 0 is an integral point which is closer to H r than w. As p and w are two colinear vectors with jjpjj < jjwjj, and as S satis es the above properties (1) and ( 2), we have that w 0 = w p + (p u) belongs to S . This contradicts the hypothesis, concluding the proof of this lemma. We now prove the result about the enumerative sequences of nodes of rational trees. Let T be a tree. We de ne the enumerative sequence t of nodes by height of the tree T by t = (t n ) n 0 , where t n is the number of nodes of T at height n.

Theorem 2 Let t(z) = P n 0 t n z n be an N-rational series such that: t 0 = 1. 8n 1; t n kt n 1 . the convergence radius of t is strictly greater than 1=k (k 2 N ).

t has a primitive linear representation. Then (t n ) n 0 is the enumerative sequence of nodes by height in a k-ary rational tree.

First proof: We denote by 1= the convergence radius of t. Let i; M; c be matrices with nonnegative integral entries such that (i; M; c) is a primitive linear representation of t, i.e. 8n 0; t n = iM n c: This representation de nes an automaton A with n states, where M is the adjacency matrix of the multigraph.

As the matrix M is primitive with spectral radius , the sequence ((M= ) n ) n 1 tends towards a positive matrix N. Let be a real such that < < k. Let S and S k be the simplex cones de ned as follows: S = fx 2 (R + ) n j xM xg S k = fx 2 (R + ) n j xM kxg: Note for example that S k = fx 2 (R + ) n j M t x t x t g. We obtain by the geometrical lemma a nite set P of integral points of S k generating the integral points of S . Since P is a nite set, there is an integer n 0 such that: 8x 2 P fig; xM n 0 2 S : We de ne a super-state automaton B associated to the automaton A. In order to do that, we identify a nonnegative integral vector x = (x 1 ; : : : ; x n ) to a t-uple composed of x j states j of A, for all 1 j n. We now de ne the super-states of B as the integral points of S n 0 1 j=0 fxM j ; x 2 P figg. Note that there is a nite number of such points. If u is a super-state in S n 0 2 j=0 fxM j ; x 2 P figg, we de ne the list of its followers in B as the unique super-state uM. If u is a super-state in fxM n 0 1 ; x 2 P figg, uM belongs to S . As a consequence of the geometrical lemma, it is a sum of points u 1 ; : : : ; u t 2 P. We de ne the list of the super-states followers of u as u 1 ; : : : ; u t .

If u is a super-state, we claim that either u is one of the points of fiM j ; 0 j (n 0 1)g, or u 2 S k . Actually if u = iM n 0 , it belongs to S S k . And if u 2 S k , uM j 2 S k ; 8j 1.

We de ne a tree rooted by the initial super-state i, by developing the super-state automaton B. We associate to each super-state u an integer w(u) de ned as the weighted number of nal states contained in the superstate u: w(u) = u c; where c is the column vector of the linear representation of t. If u 2 S k , uM ku, and uM c ku c. If u = iM j ; 0 j (n 0 1), w(u) = iM j c = t j . As 8j 1, t j kt j 1 , uM c ku c. Hence we get that for any super-state u whose followers in B are the super-states u 1 ; : : : ; u t : uMc = t X j=1 u j c ku c or equivalently: t X j=1 w(u j ) kw(u):

Thus to each super-state u is associated w(u) nodes. Since r nodes at a height l have at most kr sons at height l + 1, corresponding to the nodes associated to the super-states followers of u, it is possible to associate to each one at most k sons at the next height. The initial super-state itself (i) corresponds to one node, the root of the tree, since i c = t 0 = 1. This de nes a k-ary rational tree T admitting t as enumerative sequence of nodes by height.

Example Let t be the series, which has the automaton of Figure 9 as The simplex cone S k = fx 2 (R + ) n j xM kxg is the set of points x = (x 1 ; x 2 ; x 3 ) with:

x 2

x 1 x 2 2x 3

x 1 + x 3 2x 2 A tree, whose enumerative sequence of nodes is t, is given in the left part of Figure 10. Note that the super-states (1) and (1; 2) are not in S k . Another one is given in the right part of Figure 10. This tree has only 3 superstates and also only 3 non-isomorphic subtrees. We can remark that such a compact representation could not be obtained on this example with the alternative state-splitting proof given in 3].

We now give a second proof, based on super-state automata, for the same result.

Second proof: We denote by 1= the convergence radius of t. Let i; M; c be matrices with nonnegative integral entries such that (i; M; c) is a primitive linear representation of t, i.e. 8n 0; t n = iM n c: As M is primitive, there is an integer n 0 such that M n 0 c belongs to S k = fx 2 (R + ) n j Mx kxg :

MM n 0 c kM n 0 c Let us denote by d = M n 0 c, and by t 0 the sequence obtained from t by n 0 shifts: 8n 0; t 0 n = t n+n 0 = iM n M n 0 c = iM n d: The sequence t 0 admits (i; M; d) as primitive linear representation. We call A the multigraph whose adjacency matrix is M. We have t 0 0 = t n 0 = i d. We de ne a super-state automaton B whose states contain only one occurence of one state of A. Note that the number of super-states is equal to the number of states of A. The followers of a super-state is then the list of its followers in A. We de ne a tree rooted by the initial super-state i, by developing the super-state automaton B. We associate to each super-state u an integer w(u) de ned as the weighted number of nal states contained in the super- We associate to each super-state u w(u) nodes. The initial super-state itself (i) corresponds to t n 0 nodes, since i d = t n 0 . As r nodes at a height l have at most kr sons at height l + 1, corresponding to the nodes associated to the super-states followers of u, we associate to each one at most k sons in such a way that any node at the next height has one father. We nally complete the rst n 0 levels to get a k-ary rational tree T admitting t as enumerative sequence of nodes by height.

Figure 2 :

 2 Figure 2: A 6-state automaton A

Figure 4 :

 4 Figure 3: Development T of A

Figure 5

 5 Figure 5: Automaton A

Figure 6 :

 6 Figure 6: The super-state automaton B 3 Rational sequences of nonnegative numbers

Figure 7 :

 7 Figure 7: Tree T

Figure 8 :

 8 Figure 8: The geometrical lemma

2 1 3 Figure 9 :

 239 Figure 9: Primitive representation of t primitive representation. Its convergence radius is greater than 1=k, where

Figure 10 :

 10 Figure 10: Two trees solution

  state u: w(u) = u d: As Md kd, we get for each super-state u: uMd ku d: Hence we get that for any super-state u whose followers in B are the superstates u 1 ; : : : ; u t :


Frédérique Bassino

Julien Clément

Cyril Nicaud

Lyndon Words with a Fixed Standard Right Factor

{bassino,clementj,nicaud}@univ-mlv.fr Given a totally ordered alphabet A = {a 1 < a 2 < • • • < a q }, a Lyndon word is a word that is strictly smaller, for the lexicographical order, than any of its conjugates (i.e., all words obtained by a circular permutation on the letters). Lyndon words were introduced by Lyndon [START_REF] Lyndon | On Burnside problem I[END_REF] under the name of "standard lexicographic sequences" in order to give a base for the free Lie algebra over A. The set of Lyndon words is denoted by L. For instance, with a binary alphabet A = {a, b}, the first Lyndon words until length five are L = {a, b, ab, aab, abb, aaab, aabb, abbb, aaaab, aaabb, aabab, aabbb, ababb, abbbb, . . . }. Note that a non-empty word is a Lyndon word if and only if it is strictly smaller than any of its proper suffixes.

The standard (suffix) factorization of Lyndon words plays a central role in this framework (see [START_REF] Lothaire | Encyclopedia of mathematics and its applications[END_REF], [START_REF] Reutenauer | Free Lie algebras[END_REF], [START_REF] Ruskey | Generating Lyndon brackets: a basis for the n-th homogeneous component of the free Lie algebra[END_REF]). For w ∈ L \ A a Lyndon word not reduced to a letter, the pair (u, v) of Lyndon words such that w = uv and v of maximal length is called the standard factorization. The words u and v are called the left factor and right factor of the standard factorization. Equivalently, the right factor v of the standard factorization of a Lyndon word w which is not reduced to a letter can be defined as the smallest proper suffix of w. For instance we have the following standard factorizations: aaabaab = aaab • aab, aaababb = a • aababb and aabaabb = aab • aabb.

One can then associate to a Lyndon word w a binary tree T (w) called its Lyndon tree recursively built in the following way:

-if w is a letter, then T (w) is a leaf labeled by w, -otherwise T (w) is an internal node having T (u) and T (v) as children where u • v is the standard factorization of w. This structure encodes a non-associative operation, either a commutator in the free group [START_REF] Chen | Free differential calculus IV: The quotient groups of the lower central series[END_REF], or a Lie bracketing [START_REF] Lothaire | Encyclopedia of mathematics and its applications[END_REF]; both constructions lead to bases of the free Lie algebra.

Our goal is first to get a better insight of the standard factorization of Lyndon words, possibly to design better algorithms for the construction of the Lyndon tree (A naive algorithm has time complexity O(n 2 ) in the worst case). The characterization of the set of Lyndon words with a given right standard factor is also a first step towards the average case analysis of the height of Lyndon trees in order to give a more accurate view of the observed behavior of algorithms using Lyndon trees.

To state our main results, we need to recall first what are regular languages. A language L is a set of words over a fixed alphabet A. The structurally simplest (yet non trivial) languages are the regular languages that can be defined in a variety of ways: by regular expressions and by finite automata. Concatenation of languages is denoted by a product (L

1 • L 2 = {w 1 w 2 | w 1 ∈ L 1 , w 2 ∈ L 2 }).
Union of languages is the ordinary set union. The empty word is denoted by ǫ and the Kleene star operator is understood as

L * = ǫ + L + L • L + • • • .
A regular language over an alphabet A is built by recursively applying concatenation, union and Kleene star operator to the singleton languages {ǫ} and {σ} (∀σ ∈ A). A regular expression is the description of a regular language (most commonly using symbols "•, +, * ").

Our main result can hence be stated as follows: the set of Lyndon words with a fixed standard right factor is a regular language whose regular expression is given in Theorem 1. This result may seem a bit surprising. The fact that the set of Lyndon words is not even context-free [START_REF] Berstel | The set of Lyndon words is not context-free[END_REF] gives indeed an idea of the structural complexity of Lyndon words. Theorem 2 gives the corresponding enumerative generating function.

Let A = {a 1 < • • • < a q = γ} be a totally ordered q-ary alphabet where γ denotes the last symbol of A. We denote A * the set of finite words. We consider the lexicographical order < over all nonempty words of A * defined by the extension of the order over A. Let w be a word of A * \ {γ} * , the successor S(w) of w = vαγ i , where α is a symbol of A \ {γ} and i ≥ 0, is defined by S(w) = vβ with β the immediate next symbol after α in A. For any Lyndon word v, we define the set of words

∀v = γ X v = {v, S(v), S 2 (v), . . . , S k (v) = γ} and X γ = {γ}.
Note that k = 1 + q × |v| -q i=1 i × |v| i where q is the cardinality of the alphabet A, |v| is the length of v and |v| i is the number of occurrences of the ith letter of the alphabet A in v.

Example.

(1) for A = {a, b}, v = aabab: X aabab = {aabab, aabb, ab, b}.

(2) for A = {a, b, c}, v = abb: X abb = {abb, abc, ac, b, c}. By construction, v is the smallest element of X v A * for the lexicographical order.

Denote, for any letter α ∈ A, the set of letters A ≤α = {a ∈ A | a ≤ α}. For a language L, we use the convenient notation

L + = L + L • L + • • • .
One should also know that the class of regular languages is closed under the set difference operator "\".

Theorem 1. Let v be a Lyndon word whose first letter is α and u ∈ A * . Then uv is a Lyndon word with u • v as standard factorization if and only if u ∈ (A ≤α X * v ) \ X + v . Hence the set F v of Lyndon words having v as right standard factor is a regular language.

One of the basic properties of the set of Lyndon words is that every word is uniquely factorizable as a non increasing product of Lyndon words. We remark that when we apply this decomposition to "shifted" Lyndon words (words obtained by deleting the first symbol) the last factor is exactly the right standard factor. Another important fact is that for any two Lyndon words u and v we have u > v if and only if u ∈ X + v . We define the generating functions X v (z) of X v and X * v (z) of X * v where |w| is the length of a word w:

X v (z) = w∈Xv z |w| and X * v (z) = w∈X * v z |w| .
As the set X v is a code, the elements of X * v are (finite) sequences of elements of X v (see [START_REF] Flajolet | Analytic combinatorics-symbolic combinatorics[END_REF]):

X * v (z) = 1 1 -X v (z)
.

Denote by F v (z) = w∈Fv z |w| the generating function of the set

F v = {uv ∈ L | u • v is the standard factorization}.
Theorem 2. Let v be a Lyndon word over a q-ary alphabet. The generating function of the set F v of Lyndon words having a right standard factor v can be written

F v (z) = z |v| 1 + qz -1 1 -X v (z)
.

This generating function can further be used to enumerate or get the asymptotic behavior of the numbers of Lyndon words with fixed right standard factor (see [START_REF] Flajolet | Analytic combinatorics-symbolic combinatorics[END_REF]).


Frédérique Bassino
email: bassino@univ-mlv.fr.

Julien Clément

Gadiel Seroussi
email: gadiel@msri.org.

Alfredo Viola
email: viola@fing.edu.uy.

Optimal prefix codes for some families of two-dimensional geometric distributions

Lossless compression is studied for pairs of independent integer-valued symbols emitted by a source with a geometric probability distribution of parameter q ∈ (0, 1). Optimal prefix codes are described for q = 1/2 k (k > 1) and q = 1/ k √ 2 (k > 0). The codes described differ from previously characterized cases related to the geometric distribution in that their corresponding trees are of unbounded width, and in that an infinite set of distinct optimal codes is required to cover any interval (0, ε), ε > 0, of values of q.

Introduction

In 1966, Golomb [START_REF] Golomb | Run length encodings[END_REF] described optimal prefix codes for some geometric distributions over the nonnegative integers. In [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF], these Golomb codes were shown to be optimal for all geometric distributions, namely, distributions of the form p i = (1 -q)q i i ≥ 0, for some real value of q, 0 < q < 1, where p i represents the probability of the implied random variable assuming the value of i. Geometric distributions arise in practice when encoding run lengths (Golomb's original motivation in [START_REF] Golomb | Run length encodings[END_REF]), and in image compression when encoding prediction residuals, which are well-modeled by two-sided geometric distributions. Optimal prefix codes for the latter were characterized in [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF], based on some (sometimes non-intuitive) variants of Golomb codes. Codes based on the Golomb construction have the practical advantage of allowing the encoding of a symbol i using a simple formula based on the integer value of i, without the need for code tables or other non-trivial memory requirements. This has led to their adoption in many practical applications (see, e.g., [START_REF] Rice | Some practical universal noiseless coding techniques[END_REF], [START_REF] Weinberger | The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS[END_REF]).

When dealing with sequences of independent, identically distributed random variables, however, symbol-by-symbol encodings can incur significant redundancy relative to the entropy of the distribution, especially in the low entropy range. One way to ameliorate this problem, while keeping the simplicity and low latency of the encoding and decoding operations, is to consider short blocks of d symbols, and use a prefix code for the blocks. In this paper, we study optimal prefix codes for pairs (blocks of length d=2) of independent, identically and geometrically distributed random variables, namely, distributions on pairs of nonnegative integers (i, j) with Prob (i, j) = p i p j = (1 -q) 2 q i+j i, j ≥ 0.

(

) 1
We refer to this distribution as a two-dimensional geometric distribution (TDGD), defined on the alphabet of integer pairs A = { (i, j) | i, j ≥ 0 }.

Aside from the mentioned practical motivation, the problem is of intrinsic combinatorial interest. It was proven in [START_REF] Linder | Existence of optimal prefix codes for infinite source alphabets[END_REF] that, if the entropy -i≥0 p i log p i of a distribution over the nonnegative integers is finite, optimal (prefix) codes exist and can be obtained, in the limit, from Huffman codes for truncated versions of the alphabet. However, the proof does not give a way for effectively constructing these optimal codes, and in fact, there are few families of distributions over the integers for which an effective construction is known [START_REF] Abrahams | Code and parse trees for lossless source encoding[END_REF][START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF]. An algorithmic approach to building optimal codes is presented in [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF], which includes geometric distributions and various generalizations. The approach, though, is not applicable to TDGDs, as explicitly noted in [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF]. Some fundamental characteristic properties of the families of codes for the one-dimensional case turn out not to hold in the two-dimensional case. Specifically, the codes described in [START_REF] Golomb | Run length encodings[END_REF] and [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF] satisfy the following: (a) for a fixed value of the parameter q, the width of the code tree (number of codewords of any one length) is bounded, and (b) there is a value q = q 0 > 0 such that all distributions (from the respective family) with q < q 0 admit the same optimal prefix code. As we shall see in the sequel (and was also noted with a different terminology in [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF]), these properties do not hold for TDGDs.

The remainder of this extended summary is structured as follows. In Section 2 we present some background and notation, and we describe the technique of Gallager and Van Voorhis [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF] for constructing optimal prefix codes for infinite alphabets, which we also apply in our constructions. As noted already in [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF], most of the work and ingenuity in applying the technique goes into discovering appropriate "guesses" of the basic components on which the construction iterates, and in describing the structure of the resulting codes. That is indeed where most of our effort will be spent in the subsequent sections. In Section 3, we present a construction of optimal codes for twodimensional geometric distributions with q = 2 -k for any integer k > 1. We compute the Kraft polynomials [START_REF] Laidlaw | The construction of codes for infinite sets[END_REF] of the optimal codes, and use them to find expressions for the average codelength, which we apply to estimate the per-symbol redundancy of the codes relative to the entropy rate of geometric distribution. In Section 4, we briefly describe the construction of optimal codes for distributions with q = 1/ k √ 2 for any positive integer k.

For both of the families of parameters studied in sections 3 and 4, the code trees obtained have only a finite number of non-isomorphic whole subtrees (i.e., subtrees consisting of a node and all of its descendants). However, contrary to the previously known results, the tree widths are not bounded, and, in the case q = 2 -k , there is an infinite sequence of distinct codes as k → ∞, i.e., q → 0, again in contrast with previously characterized cases. We show, however, that there is a limiting code as k → ∞, in the sense that there exists an unbounded function L(k) such that all optimal code trees for k ′ ≥ k are identical in their first L(k) levels. Finally, in Section 5 we present some open problems and directions for further research. We note that in the one-dimensional case, it was proved in [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF] that the family of codes that are optimal for the values q = 1/ k √ 2 studied in Section 4 (the same sequence, dense near q = 1, mentioned by Golomb in [START_REF] Golomb | Run length encodings[END_REF]) contains optimal codes for all values of q. This is not true in the two-dimensional case, even when considering also the values q = 2 -k of Section 3, which are dense near 0. Thus, one of our main open problems is the complete characterization of a family of optimal codes covering all values of q. Another direction for further research is the extension of the results to blocks of d > 2 integer symbols. With a slightly different formalism, presented in [START_REF] Bassino | Optimal prefix codes for two-dimensional geometric distributions[END_REF], the construction of Section 4 extends to arbitrary values of d.

Given the space constraints of this extended summary, most results are presented without proof, and some descriptions are very brief. Complete proofs and descriptions, as well as additional results, will be given in the full version [START_REF] Bassino | Optimal prefix codes for two-dimensional geometric distributions[END_REF].

Preliminaries

We are interested in encoding the alphabet A of integer pairs (i, j), i, j ≥ 0, using a binary prefix code C. As is well known, such a code can be associated with a rooted binary tree, whose leaves correspond, bijectively, to symbols in A, and where each branch is labeled with a binary digit. The binary codeword assigned to a symbol is "read off" the labels of the branches on the path from the root of the tree to the corresponding leaf. We shall not distinguish between the code C and its associated binary tree, or between alphabet symbols and leaves of the tree. Also, two trees will be considered equivalent if for each ℓ ≥ 0, both trees have the same number of leaves at depth ℓ.

We call s(i, j) = i + j the signature of (i, j) ∈ A. For a given signature f = s(i, j), there are f +1 pairs with signature f , all with the same probability, w(f )=(1q) 2 q f , under the distribution (1) on A. Hence, given a prefix code C, symbols of the same signature may be freely permuted without affecting the average code length of C. Thus, for simplicity, we can also regard the correspondence between leaves and symbols as one between leaves and elements of the multiset

A = {0, 1, 1, 2, 2, 2, . . . , f, . . . , f f +1 times , . . . }. (2)
In constructing the tree, we do not distinguish between different occurrences of a signature f ; for actual encoding, the f +1 leaves labeled with f are mapped to the symbols (0, f ), (1, f -1), . . . , (f, 0) in some arbitrary order. Consider a prefix code C. Let T be a subtree of C, and let s(x) denote the signature associated with a leaf x of T . We define the weight, w(T ), and cost, c(T ), of T , respectively, as

w(T ) = x leaf of T w(s(x)),
and c(T ) =

x leaf of T depth(x)w(s(x)), with w(f ) = (1 -q) 2 q f for f ≥ 0. When T = C, we have w(T ) = 1, and c(T ) is the average code length of C. Our goal is to find a prefix code C that minimizes this cost.

In deriving the structure and optimality of our prefix codes, we shall rely on the method outlined below, due to Gallager and Van Voorhis [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF], and adapted here to our terminology and notation.

-Define a countable sequence of reduced alphabets (S f ) ∞ f =-1 , where S f is a multiset containing the signatures 0, 1, . . . , f (with multiplicities as in ( 2)), and where the signatures strictly greater than f are partitioned into a finite number of nonempty classes we shall refer to as virtual symbols, which are also elements of S f . We naturally associate with each virtual symbol a probability equal to the sum of the probabilities of the signatures it contains.

-Verify that the sequence of reduced alphabets (S f ) ∞ f =-1 is compatible with the bottom-up Huffman procedure. This means that after a certain number of merging steps of the Huffman algorithm on the reduced alphabet S f , one gets S f ′ with f ′ < f .1 -Apply the Huffman algorithm to the reduced alphabet S -1 (containing no signatures of the original alphabet, only virtual symbols). -Finally, use a convergence argument that ensures that the sequence of finite codes (C n ) n≥1 obtained converges to an infinite code C. Namely for every i ≥ 1, codewords of C n being sorted by non-decreasing length following the lexicographical order, the ith codeword of C n is eventually constant when n grows, and equal to the ith codeword of C.

This method, utilized also in [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF], produces an optimal prefix code for the given probability distribution on the underlying countable alphabet. The difficult part is to guess the structure of the sequence of reduced alphabets.

Quasi-uniform sources. We say that a finite source with probabilities

σ 0 ≥ σ 1 ≥ • • • ≥ σ N -1 is quasi-uniform if either N ≤ 2 or σ 0 ≤ σ N -2 + σ N -1 .
An optimal prefix code for a quasi-uniform source of N probabilities consists of 2 ⌈log N ⌉ -N codewords of length ⌊log N ⌋, and 2N -2 ⌈log N ⌉ codewords of length ⌈log N ⌉, the shorter codewords being assigned to the symbols with the larger probabilities [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF]. We refer to such a code as a quasi-uniform code, and denote by Q(i, N ) the codeword it assigns to the ith symbol, which has probability σ i , 0≤i<N .

3 Family of parameters q = 2 -k

We introduce some notations for describing the recursive construction of trees with weights associated to their leaves. The notation will be based on grammatical production rules together with scalar multiplication. After assuming that the integer k defining the parameter q = 2 -k is fixed, we slightly abuse notation and regard q as a symbolic indeterminate in the production rules. A leaf associated with weight q f will be denoted q f (in turn, this weight will be associated with the signature f , the normalizing coefficient (1-q) 2 being immaterial to the construction). Given a tree T and a scalar quantity g, gT denotes the tree resulting from multiplying the weights of all the leaves of T by g. The tree C m is defined as the complete tree of depth m, with 2 m leaves labeled q 0 (or, equivalently, 1 ). Its construction can be described by the following production rules:

C m → C m-1 C m-1 , C 0 → 1 .
The infinite tree (and associated multiset of leaf weights) L k q is defined by the following rules, where k is the fixed integer referred to above:

L 0 q → qL k q , L m q → L m-1 q C m-1 , for 0 < m ≤ k.
In words, L k q consists of a complete tree C k with 2 k -1 leaves of weight q 0 , and with the remaining leaf serving as the root of qL k q . Thus, L k q has 2 k -1 leaves of weight q f at depth (f +1)k for all f ≥0, and no other leaves.

The main result of this section is presented in the following proposition that can be seen as describing, at the same time, the optimal tree, and the sequence of reduced alphabets used in the proof of optimality following the method of [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF].

Proposition 1. Let q = 2 -k with k > 1.
Then, signatures f ∈ A are distributed in the optimal prefix tree for the TDGD with parameter q according to the following cases:

1. Assume 0 ≤ f < 2 k-1 , and write f = 2 i + j -1 with 0 ≤ j ≤ 2 i -1. Then all signatures f are distributed on two levels in the following way:

q f • " 1 • • • 1 | {z } 2 k-1 -j -1 times R f 1 1 1 | {z } j times

#

The multiset q f R f represents a tree containing all the signatures strictly greater than f . 2. Let f ≥ 2 k-1 , and write f = 2 k-1 -1 + ℓ(2 k -1) + j. Then the signatures f are distributed in the coding tree according to the five cases below. The trees (and associated multisets) q f R j represent a virtual symbol containing all the signatures not contained in the other virtual symbols of types C k-1 and L k-1 q at the same level.

In the following five cases, (♣) stands for

" qL k-1 q qC k-1 1 • • • 1 | {z } 2 k -1 times # (i) 0 ≤ j < 2 k-1 -2: q f • " (♣) ℓ times 1 • • • 1 | {z } 2 k-1 -j -1times Rj 1 1 1 | {z } j times # (ii) j = 2 k-1 -2: q f • " (♣) ℓ times qC k-1 Rj 1 1 | {z } 2 k-1 -1 times # (iii) 2 k-1 -2 < j < 2 k -3: q f • " (♣) ℓ times 1 • • • 1 | {z } 2 k-1 times 1 • • • 1 | {z } 2 k -2 -j times qC k-1 Rj 1 1 | {z } j -2 k-1 + 1 times # (iv) j = 2 k -3: q f • " (♣) ℓ times 1 • • • 1 | {z } 2 k-1 times 1 qL k-1 q Rj 1 1 | {z } 2 k-1 -2 times # (v) j = 2 k -2: q f • " (♣) ℓ times qL k-1 q qC k-1 1 • • • 1 | {z } 2 k-1 -1 times Rj 1 1 1 | {z } 2 k-1 -1 times #
The proof (which is omitted here) computes the weights of the signatures and virtual symbols in each case, and verifies that the sibling property holds. It also verifies that by applying the Huffman procedure to the reduced alphabet corresponding to each case, one obtains a configuration corresponding to the previous case, in cyclic fashion (i.e., (v)→(iv)→(iii)→(ii)→(i)→(v)), with the value of ℓ decreasing by one with each cycle, until Case 2(i) is reached with ℓ=0 and j=0, in which case the Huffman merging leads to Case 1 of the proposition.

The construction of the optimal prefix tree stemming from Proposition 1 can be outlined as follows.

1. The first level of the tree (descending directly from the root) is composed of two nodes labeled by 1 and R 0 respectively (Case 1 with f = 0). As long as f < 2 k-1 , q f -1 R f -1 is replaced by the subtree associated with the quasi-uniform code for the f + 1 symbols of signature f the virtual symbol q f R f containing all the symbols strictly greater than f . 2. The rest of the tree can be constructed in slices for f ≥ 2 k-1 , where each slice contains all the external nodes with signatures Example. Figure 1 describes the structure of the infinite optimal coding tree when k = 3 (q = 1/8). The cycling structure of Proposition 1 ((i)→(ii)→(iii)→(iv)→(v)→(i) when traversing top-down) is represented by the loop-back edge A → B, which indicates that a copy of the tree rooted at B is inserted as a child of A (with labels appropriately shifted). The subtree rooted at D, with the loop-back edge C → D, describes in a concise manner the infinite tree L 3 q . Each time the edge A → B is traversed, the parameter ℓ (number of patterns (♣) in Proposition 1) increases by one. The first instance of node A occurs for f = 9 (that is, Case 2(v) with j = 6 and ℓ = 0). Then, f = 10 is described by Case 2(i) with j = 0 and ℓ = 1. The 11 leaves with signature f = 10 are obtained as follows. The first four leaves are those shown at the last level of Figure 1, descending from the first recursive occurrence of node B. Three more come from the loop-back edge C → D (the three leaves two levels down from node D). The remaining four leaves come from the back edge A → B, and are the leaves in the first three levels of the subtree rooted at B.

2 k-1 + ℓ(2 k -1) ≤ f < 2 k-1 + (ℓ + 1)(2 k -1) (ℓ ≥ 0). Case 1) j = 0 Case 1) j = 0 Case 1) j = 1 (i) j = 0 (i) j = 1 (ii) j = 2 (iii) j = 3 (iii) j = 4 (iv) j = 5 (v) j = 6 B A D C
Notice that it follows from Proposition 1 that the width of the optimal tree for a given value of q = 2 -k is unbounded (for example, each of the cases in the proposition has parts that grow monotonically with ℓ, which is unbounded). Also, since, clearly, different values of k lead to different trees L k q , it also follows from the proposition that, as k → ∞, we have an infinite sequence of distinct optimal trees. As mentioned in Section 1, the opposite properties hold for the previously characterized cases of distributions derived from the geometric distribution (cf. [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF]). A limit code. The construction of the part of the optimal tree for 1/2 k ′ that contains the symbols 0 ≤ f < 2 k-1 -3 (Case 1 and Case 2 (i) with ℓ = 0) is the same for all k ′ ≥ k. More precisely, one can build this part of the tree, beginning with f = 0 and the quasi-uniform coding tree for f + 2 symbols, by recursively replacing f by f + 1, as long as f < 2 k -3, and the first leaf of the deepest level of the current tree by the quasi-uniform coding tree for f + 2 symbols. For 0 ≤ f ≤ 2 k -4, the quasi-uniform coding tree with f + 2 symbols defines ⌈log 2 (f + 2)⌉ levels in the optimal tree for 2 -k . Collecting these contributions for f from 0 to 2 k -4, we verify that the distribution of nodes in the claimed number of levels remains invariant for k ′ > k. Therefore, the distribution of the number of leaves at each level in the optimal trees for q = 2 -k progressively "stabilizes" as k → ∞. This observation leads to the following proposition.

Proposition 2. When k → ∞, the sequence of optimal coding trees for q = 2 -k converges to a limit tree that can be constructed, up to tree equivalence, as follows: beginning with the quasi-uniform coding tree for n = 2 symbols, recursively replace the first leaf of the last level of the current tree by the quasi-uniform coding tree for n + 1 symbols, and increase n.

Figure 2 shows the first fourteen levels of the limit tree of Proposition 2. Notice that the first eleven levels of the limit tree coincide with those of the tree of Figure 1, up to reordering of nodes at each level. The limit code admits a very simple procedure: given a pair (m, n), with signature f = m+n, we write f = 2 i + j -1, with 0 ≤ j < 2 i and i ≥ 0. We encode (m, n) with a binary codeword xy, where x = 0 (i-1)(f +1)+2j+1 identifies the path to the root of the quasi-uniform tree that contains all the leaves of signature f , and y = Q(m + 1, f + 2) (recall that Q(m, N ) is the code for m in a quasi-uniform code on N symbols). A matching decoding Fig. 3. The redundancy (in bits per symbol) for the optimal prefix code (empirical), the Golomb code and the optimal codes C k . q -2 T 2 q q -2 T 2 q q 3 T 2 q q 3 T 2 q q 3 T 1 q q 3 T 1 q q 3 T 1 q q 3 T 1 q q 3 q 3 q 3 T 1 q q 3 T 1 q q 3 q 3 q 2 q 2 q 3 T 1 q q 3 T 1 q q 3 q 3 q 2 q 2 q 1 q 1 q 3 T 1 q q 3 T 1 q q 3 q q 2 q 2 q 1 q 1 q 0 q 0 Fig. 4. Top of the tree q -2 T 2 q .

The tree q r T 1 q k is easily recognized as that of a unary code (Golomb code of order 1), with leaves appropriately weighted. Moreover, the tree q r T 2 q k can be recognized as a convolution of two such unary trees, i.e., a unary where each leaf becomes the root of another unary tree (see Figure 4). It follows from this observation, and straightforward symbolic manipulations, that w(q r T 2

q k ) = w( q r ) q k 1-q k 2 . It is important to note that if q = 1/ k √ 2 then, w(q r T 2 q k ) = w(q r T 1 q k ) = w(q r T 0 q k ) = w( q r
). This observation is the basis of the construction and proof in Proposition 3.

We observe also that the tree q -2 T 2 q gives an optimal prefix code for k=1, as can be verified by checking that this coding tree satisfies the sibling property of Huffman trees. The top of this tree is shown in Figure 4. This construction is generalized in Proposition 3 for all k > 1. This formalism is explored in [START_REF] Bassino | Optimal prefix codes for two-dimensional geometric distributions[END_REF], and can be generalized to the study of optimal codes on blocks of fixed d > 2 integer symbols. Proposition 3. Let q = 1/ k √ 2 with k ≥ 1. Then, an optimal prefix tree for a TDGD with parameter q can be obtained by the application of the Huffman algorithm to the finite source

S T = {q -2k T 2 q k 1 time , q -2k+1 T 2 q k 2 times , q -2k+2 T 2 q k 3 times . . . , q -k-1 T 2 q k k times } ∪ { q -k T 2 q k k -1 times , . . . , q -3 T 2 q k 2 times , q -2 T 2 q k 1 times }.
It is shown in [START_REF] Bassino | Optimal prefix codes for two-dimensional geometric distributions[END_REF] that a prescribed sequence of pairings of symbols q -i T 2 q k with 2 ≤ i ≤ k -1 leads from the reduced alphabet S T to a quasi-uniform source. Efficient coding and decoding algorithms for the codes of Proposition 3 is also presented in [START_REF] Bassino | Optimal prefix codes for two-dimensional geometric distributions[END_REF].

Example. Let k = 4, i.e., q = 1/ 4 √ 2. The source S T has k 2 = 16 symbols, leading to a reduced alphabet S (corresponding to a quasi-uniform source) with 13 symbols. An optimal coding tree for S T in this example is given in Figure 5. Circled nodes indicate the pairings leading to the quasi-uniform source S.

Conclusion

We characterized optimal prefix codes for two sub-families of two-dimensional geometric distributions, namely, those with parameters q = 2 -k with k>1, or q = 1/ k √ 2 with k > 0. The codes characterized here are in fact optimal for values of q in a set of positive measure containing the above discrete sequences. However, these codes do not cover the full range of values of q in the interval (0, 1). Characterizing optimal prefix codes for TDGDs over the full interval is the subject of ongoing research. Future work will include also further generalizations to higher dimensions, i.e., blocks of d > 2 integer symbols. Of interest also is the derivation of analogous results for blocks of two-sided geometric distributions [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF].

Fig. 1 .

 1 Fig. 1. Optimal prefix code tree for a TDGD with q=1/8.

Fig. 2 .

 2 Fig.2. Top of a limit tree for q = 2 -k when k → ∞ (first fourteen levels).

Fig. 5 . 2 .

 52 Fig. 5. The top of the tree for ST for q = 1/ 4 √ 2. Circled nodes are composite nodes of the source S.

⋆ This research is partially supported by project PDT S/C/IF/54/178 2006-2008.

A way to test Huffman compatibility is to use the sibling property[START_REF] Gallager | Variations on a theme by Huffman[END_REF] that characterizes Huffman trees as the trees whose nodes can be listed in non-increasing order of probability in such way that two sibling nodes are adjacent in the list.

procedure is easily derived. Encoding and decoding procedures for all the codes in this section are presented in [START_REF] Bassino | Optimal prefix codes for two-dimensional geometric distributions[END_REF].

Kraft polynomial Let Σ be an alphabet with a probability distribution (µ i ) i∈Σ and C a prefix code on Σ with codewords lengths (ℓ i ) i∈Σ . The Kraft polynomial [START_REF] Laidlaw | The construction of codes for infinite sets[END_REF] of the code C is the formal series

The average codelength of C is obtained as c(C) = z ∂ ∂z P (z) z=1 . We derive the Kraft polynomial for the optimal codes of Proposition 1. For 0 ≤ j < 2 k -1, and any integer i, define

Then, the Kraft polynomials P 2 -k (z) for the optimal codes (when q = 2 -k ), and P 0 (z) for the limit code, are given by:

q 2 i +j-1 P i,j (z)z 2 i (i-1)+1+j(i+1) .

Redundancy. Figure 3 presents plots of redundancy per integer symbol as a function of q, relative to the entropy rate of the geometric distribution of parameter q, for q ≤ 1 2 . Let C k denote the optimal prefix code for a TDGD with q = 2 -k . Plots are shown for the Golomb code on single integer symbols, the best code C k for each q, and the optimal code for each q. Code lengths for the latter were approximated empirically. It is observed in the figure that the family { C k } provides a good approximation to the optimal codes for arbitrary q over the low entropy range. However, we can also observe that optimal codes for some values of q will be strictly outside of the families characterized in this paper. [START_REF] Rice | Some practical universal noiseless coding techniques[END_REF] The family of parameters q = 1/ k √ 2

We introduce the following grammar to define the trees T d u for d = 0, 1, 2.


Frédérique Bassino
email: bassino@univ-mlv.fr

Julien Clément

Gadiel Seroussi
email: gadiel@msri.org

Alfredo Viola
email: viola@fing.edu.uy

Optimal prefix codes for pairs of geometrically-distributed random variables

I. INTRODUCTION

In 1966, Golomb [START_REF] Golomb | Run length encodings[END_REF] described optimal prefix codes for some geometric distributions over the nonnegative integers. In [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF], these Golomb codes were shown to be optimal for all geometric distributions, namely, distributions of the form Prob(i) = p i = (1 -q)q i , i ≥ 0, for some real-valued parameter q, 0 < q < 1. Geometric distributions arise in practice when encoding run lengths (Golomb's original motivation in [START_REF] Golomb | Run length encodings[END_REF]), and in image compression when encoding prediction residuals, which are well-modeled by twosided geometric distributions. Optimal prefix codes for the latter were characterized in [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF], based on some (sometimes non-intuitive) variants of Golomb codes. Codes based on the Golomb construction have the practical advantage of allowing the encoding of a symbol i using a simple formula based on the integer value of i, without the need for code tables or other non-trivial memory requirements. This has led to their adoption in many practical applications (cf. [START_REF] Rice | Some practical universal noiseless coding techniques[END_REF], [START_REF] Weinberger | The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS[END_REF]). For computational reasons, these applications often use a subfamily of the class of optimal codes as a good approximation for the whole class over the full range of q (e.g., "power-oftwo" Golomb codes in [START_REF] Rice | Some practical universal noiseless coding techniques[END_REF] and [START_REF] Weinberger | The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS[END_REF]; see also [START_REF] Seroussi | On adaptive strategies for an extended family of Golomb-type codes[END_REF]).

When dealing with sequences of independent, identically distributed random variables, however, symbol-by-symbol encodings can incur significant redundancy relative to the entropy of the distribution. One way to mitigate this problem, while keeping the simplicity and low latency of the encoding and decoding operations, is to consider short blocks of d>1 symbols, and use a prefix code for the blocks. In this paper, we study optimal prefix codes for pairs (blocks of length d=2) of independent, identically and geometrically distributed random variables, namely, distributions on pairs of nonnegative integers (i, j) with Prob (i, j) = p i p j = (1 -q) 2 q i+j i, j ≥ 0.

(

) 1
We refer to this distribution as a two-dimensional geometric distribution (TDGD), defined on the alphabet of integer pairs

A = { (i, j) | i, j ≥ 0 }.
Aside from the mentioned practical motivation, the problem is of intrinsic combinatorial interest. It was proven in [START_REF] Linder | Existence of optimal prefix codes for infinite source alphabets[END_REF] (see also [START_REF] Kato | Huffman coding with an infinite alphabet[END_REF]) that, if the entropy -i≥0 p i log p i of a distribution over the nonnegative integers is finite, optimal (prefix) codes exist and can be obtained, in the limit, from Huffman codes for truncated versions of the alphabet. However, the proof does not give a general way for effectively constructing optimal codes, and in fact, there are few families of distributions over countable alphabets for which an effective construction is known [START_REF] Abrahams | Code and parse trees for lossless source encoding[END_REF] [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF]. An algorithmic approach to building optimal codes is presented in [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF], which covers geometric distributions and various generalizations. The approach, though, is not applicable to TDGDs, as explicitly noted in [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF]. Some fundamental characteristic properties of the families of codes for the one-dimensional case turn out not to hold in the two-dimensional case. Specifically, the codes described in [START_REF] Golomb | Run length encodings[END_REF] and [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF] satisfy the following: (a) for a fixed value of q, the width of the code tree (number of codewords of any one length) is bounded, and (b) there is a value q=q 0 >0 such that all distributions (from the respective family) with q < q 0 admit the same optimal prefix code. As we shall see in the sequel, and was also predicted with a different terminology in [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF], optimal codes for TDGDs will not satisfy these properties.

The remainder of this extended summary is structured as follows. In Section II we present some background and notation, and we describe the technique of Gallager and Van Voorhis [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF] for constructing optimal prefix codes for infinite alphabets, which we also apply in our constructions. As noted already in [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF], most of the work and ingenuity in applying the technique goes into discovering appropriate "guesses" of the basic components on which the construction iterates, and in describing the structure of the resulting codes. That is indeed where most of our effort will be spent in the subsequent sections. In Section III, we present a construction of optimal codes for TDGDs with q = 2 -k for any integer k > 1.

We compute the Kraft functions (called Kraft polynomials in [START_REF] Laidlaw | The construction of codes for infinite sets[END_REF]) of the optimal codes, and use them to compute the average code lengths, which we apply to estimate the persymbol redundancy of the codes relative to the entropy rate of the geometric distribution. In Section IV, we describe the construction of optimal codes for distributions with q = 1/ k √ 2 for any positive integer k. We also summarize a study of the redundancy rates for both families of characterized codes over the full interval 0 < q < 1. The study suggests that these codes provide a good approximation to the full class of optimal codes for TDGDs (the full characterization of which remains an open problem) over the entire range of q.

For both families of parameters studied in sections III and IV, the code trees obtained have only a finite number of non-isomorphic whole subtrees (i.e., subtrees consisting of a node and all of its descendants). However, contrary to the previously known results, the tree widths are not bounded, and, in the case q = 2 -k , there is an infinite sequence of distinct codes as k → ∞, i.e., q → 0. We show, however, that there exists a limiting code as k → ∞, in the sense that there exists an unbounded function L(k) such that all optimal code trees for k ≥ k are identical in their first L(k) levels.

Finally, in Section V we present some open problems and directions for further research. Given the space constraints of this extended summary, most results are presented without proof, and some descriptions are very brief. Complete proofs and descriptions, as well as additional results, will be given in the full version [START_REF] Bassino | Optimal prefix codes for pairs of geometrically-distributed random variables[END_REF].

II. PRELIMINARIES

We are interested in encoding the alphabet A of integer pairs (i, j), i, j ≥ 0, using a binary prefix code C. As usual, we associate C with a rooted (infinite) binary tree, whose leaves correspond, bijectively, to symbols in A, and where each branch is labeled with a binary digit. The binary codeword assigned to a symbol is "read off" the labels of the branches on the path from the root of the tree to the corresponding leaf. We shall not distinguish between the code C and its associated binary tree, or between alphabet symbols and leaves of the tree. Also, two trees will be considered equivalent if for each ≥ 0, both trees have the same number of leaves at depth . We call s(i, j) = i + j the signature of (i, j) ∈ A. For a given signature f = s(i, j), there are f +1 pairs with signature f , all with the same probability, w(f )=(1 -q) 2 q f , under the distribution (1) on A. Hence, given a prefix code C, symbols of the same signature may be freely permuted without affecting the average code length of C. Thus, for simplicity, we can also regard the correspondence between leaves and symbols as one between leaves and elements of the multiset

A = {0, 1, 1, 2, 2, 2, . . . , f, . . . , f f +1 times , . . . }. (2)
In constructing the tree, we do not distinguish between different occurrences of a signature f ; for actual encoding, the f +1 leaves labeled with f are mapped to the symbols (0, f ), (1, f -1), . . . , (f, 0) in some fixed order.

Consider a prefix code C. Let T be a subtree of C, and let s(x) denote the signature associated with a leaf x of T . We define the weight, w(T ), and cost, c(T ), of T , respectively, as w(T ) =

x leaf of T w(s(x)), and c(T ) =

x leaf of T depth(x)w(s(x)), with w(f ) = (1 -q) 2 q f for f ≥ 0. When T = C, we have w(T ) = 1, and c(T ) is the average code length of C. Our goal is to find a prefix code C that minimizes this cost.

In deriving the structure and optimality of our prefix codes, we shall rely on the method outlined below, due to Gallager and Van Voorhis [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF], and adapted here to our terminology.

• Define a countable sequence of finite reduced alphabets

(S f ) ∞ f =-1
, where S f is a multiset containing the signatures 0, 1, . . . , f (with multiplicities as in ( 2)), and where the signatures strictly greater than f are partitioned into a finite number of nonempty classes referred to as virtual symbols, which are also elements of S f . We naturally associate with each virtual symbol a probability equal to the sum of the probabilities of the signatures it contains.

• Verify that the sequence of reduced alphabets

(S f ) ∞ f =-1
is compatible with the bottom-up Huffman procedure. This means that after a certain number of merging steps of the Huffman algorithm on the reduced alphabet S f , one gets S f with f < f . 1• Apply the Huffman algorithm to S -1 . While the sequence of reduced alphabets S f can be seen as evolving "bottom-up," the infinite prefix code C constructed results from a "top-down" sequence of corresponding finite prefix codes C f . One shows that the sequence of codes (C f ) f ≥1 converges to the infinite code C, in the sense that for every i ≥ 1, with codewords of C f consistently sorted, the ith codeword of C f is eventually constant when f grows, and equal to the ith codeword of C. A corresponding convergence argument on the sequence of average code lengths then establishes the optimality of C.

This method was successfully applied to characterize infinite optimal prefix codes in [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF] and [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF]. The difficult part is to guess the structure of the sequence of reduced alphabets. Quasi-uniform sources. We say that a finite source with probabilities

σ 0 ≥ σ 1 ≥ • • • ≥ σ N -1 is quasi-uniform if either N ≤2 or σ 0 ≤σ N -2 +σ N -1 .
An optimal prefix code for a quasiuniform source of N probabilities consists of 2 log N -N codewords of length log N , and 2N -2 log N codewords of length log N , the shorter codewords corresponding to the more probable symbols [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF]. We refer to such a code as a quasi-uniform code (or tree), denote it by Q N , and denote by Q(i, N ) the codeword it assigns to the symbol corresponding to probability σ i , 0≤i<N . Tree concatenation. We define the concatenation of two coding trees T 1 and T 2 , denoted T 1 •T 2 , as the tree constructed by taking T 1 , and making each of its leaves the root of a copy of T 2 . For example, the Golomb code of order m ≥ 1 can be seen as the concatenation G m =Q m • G 1 , where G 1 is a unary tree consisting of a root whose children are a leaf (say, on the branch labeled '1'), and, recursively, a copy of G 1 .

III. THE FAMILY OF PARAMETERS q = 2 -k

We introduce some notations, based on grammatical production rules together with scalar multiplication, for describing the recursive construction of trees with weights associated to their leaves. After assuming that the integer k defining q = 2 -k is fixed, we slightly abuse notation and regard q as a symbolic indeterminate in the production rules. A leaf associated with weight q f will be denoted q f (in turn, this weight will be associated with the signature f , the normalizing coefficient (1-q) 2 being immaterial to the construction). Given a tree T and a scalar quantity g, gT denotes the tree resulting from multiplying the weights of all the leaves of T by g.

We denote by C m the complete tree of depth m, with 2 m leaves labeled q 0 (or, equivalently, 1 ). Its construction can be described by the following production rules:

C 0 → 1 , C m → C m-1 C m-1 .
The infinite tree (and associated multiset of leaf weights) L k q is defined by the following rules, where k is the fixed integer referred to above:

L 0 q → qL k q , L m q → L m-1 q C m-1 for 0 < m ≤ k.
In words, L k q consists of a complete tree C k with 2 k -1 leaves of weight q 0 , and with the remaining leaf serving as the root of qL k q . Thus, L k q has 2 k -1 leaves of weight q f at depth (f +1)k for all f ≥0, and no other leaves.

The main result of this section is presented in the following proposition, where we describe the layers of the optimal prefix tree for a TDGD with parameter q = 2 -k , k > 1 (the case k=1 is covered in Section IV). The proposition can be seen as describing, at the same time, the optimal tree, and the sequence of reduced alphabets used in the proof of optimality following the method of [START_REF] Gallager | Optimal source codes for geometrically distributed integer alphabets[END_REF].

Proposition 1: Let q=2 -k with k>1. Then, signatures f ∈A are distributed in an optimal prefix tree for the TDGD with parameter q according to the following cases:

1) Assume 0 ≤ f < 2 k-1 , and write f = 2 i + j -1 with 0 ≤ j ≤ 2 i -1. Then all signatures f are distributed on two levels in the following way:

q f • " 1 • • • 1 | {z } 2 i -j -1 times R f 1 1 1 | {z } j times

#

The multiset q f R f represents a tree containing all the signatures strictly greater than f . 2) Let f ≥ 2 k-1 , and write f = 2 k-1 -1 + (2 k -1) + j.

Then the signatures f are distributed in the optimal coding tree according to the five cases below. The trees (and associated multisets) q f R j represent a virtual symbol containing all the signatures not contained in the other virtual symbols of types C k-1 and L k-1 q at the same level. Also, for succinctness, the symbol (♣) stands for

" qL k q 1 • • • 1 | {z } 2 k -1 times # . (i) 0 ≤ j < 2 k-1 -2: q f • " (♣) times 1 • • • 1 | {z } 2 k-1 -j -1times R j 1 1 1 | {z } j times # (ii) j = 2 k-1 -2: q f • " (♣) times qC k-1 R j 1 1 | {z } 2 k-1 -1 times # (iii) 2 k-1 -2 < j < 2 k -3: q f • " (♣) times 1 • • • 1 | {z } 3•2 k-1 -2-j times qC k-1 R j 1 1 | {z } j-2 k-1 +1 times # (iv)] j = 2 k -3: q f • " (♣) times 1 • • • 1 | {z } 2 k-1 +1 times qL k-1 q R j 1 1 | {z } 2 k-1 -2 times # (v) j = 2 k -2: q f • " (♣) times qL k q 1 • • • 1 | {z } 2 k-1 -1 times R j 1 1 1 | {z } 2 k-1 -1 times #
The proof (which is omitted here) computes the weights of the signatures and virtual symbols in each case, and verifies that the sibling property holds. It also verifies that applying the Huffman procedure to the reduced alphabet corresponding to each case, one obtains a configuration corresponding to the previous case, in cyclic fashion, namely, (v)→(iv)→(iii)→(ii)→(i)→(v) (bottom-up). The value of decreases by one with each cycle, until Case 2(i) is reached with =0 and j = 0, in which case the Huffman merging leads to Case 1 of the proposition.

The construction of the optimal prefix tree derived from Proposition 1 can be outlined as follows (top-down):

1) The first level of the tree (descending directly from the root) is composed of two nodes labeled by 1 and R 0 respectively (Case 1 with f =0). As long as f < 2 k-1 , q f -1 R f -1 is replaced by the subtree associated with the quasi-uniform code for the f +1 symbols of signature f and the virtual symbol q f R f containing all the signatures strictly greater than f . 2) The rest of the tree is constructed in cycles, one for each value of ≥ 0, generating all the leaves with signatures

f , 2 k-1 -1+ (2 k -1) ≤ f < 2 k-1 -1+( + 1)(2 k -1).
Within each cycle, the construction follows the topdown sequence of sub-cases (i)→(ii)→(iii)→(iv)→(v) of Case 2 of Proposition 1. Example. Figure 1 describes the structure of the infinite optimal coding tree for q = 1/8 (k=3). The loop-back edges in the figure indicate that a copy of the tree rooted at the target node is inserted as a child of the originating node (with labels appropriately shifted). The cycling structure of Proposition 1 ((i)→(ii)→(iii)→(iv)→(v)→(i) when traversing top-down) is represented by the outer loop-back edge-each traversal of the edge represents an increase of the parameter of the proposition by one. The inner loop-back edge helps describe in a concise manner the infinite tree L 3 q , which is rooted at the node originating the edge. Signatures 0≤f ≤ 3 are generated by Case 1 of Proposition 1. Signatures 4≤f ≤9 correspond to the subcases of Case 2 indicated in the figure, with =0, and the value of j also indicated. Signature f =10 starts a new cycle, with = 1; four leaves with this signature are shown at the deepest level in the figure, three are picked up after traversing the inner loop-back edge, and the remaining four after traversing the outer loop-back edge.

Notice that it follows from Proposition 1 that the width of the optimal tree for a given value of q = 2 -k is unbounded (for example, each of the cases in the proposition has parts that grow monotonically with , which is unbounded). Also, different values of k lead to different trees L k q , so it also follows from the proposition that there is an infinite sequence of distinct optimal trees as k → ∞. The opposite properties hold for the previously characterized cases related to the geometric distribution (cf. [START_REF] Golin | Algorithms for constructing infinite huffman codes[END_REF]).

The infinite sequence of optimal codes obtained when k→∞ (q→0) stabilizes in the limit, as stated in the following proposition, which follows from Proposition 1 (the fact is also mentioned in [START_REF] Baer | Coding for General Penalties[END_REF]Ch. 5]).

Proposition 2: When k→∞, the sequence of optimal coding trees for q=2 -k converges to a limit tree that can be constructed, up to equivalence, as follows: start with Q n for n=2, recursively replace the first leaf of the deepest level of the current tree by Q n+1 , and increase n.

Figure 2 shows the first fourteen levels of the limit tree of Fig. 2. Top of the limit tree for q = 2 -k when k → ∞.

Proposition 2. Notice that the eleven levels of the limit tree coincide with those of the tree of Figure 1, up to reordering of nodes at each level. The limit code admits a very simple encoding procedure: given a pair (m, n), with signature f = m+n, we write f = 2 i + j -1, with 0 ≤ j < 2 i and i ≥ 0. We encode (m, n) with a binary codeword xy, where x = 0 (i-1)(f +1)+2j+1 identifies the path to the root of the quasiuniform tree that contains all the leaves of signature f , and y = Q(m+1, f +2). A matching decoding procedure is easily derived. Encoding and decoding procedures for all the codes in this section are presented in [START_REF] Bassino | Optimal prefix codes for pairs of geometrically-distributed random variables[END_REF] [START_REF] Baer | Coding for General Penalties[END_REF]. Kraft functions. Let Σ be a countable alphabet, (µ i ) i∈Σ a distribution on Σ, and C a prefix code on Σ with codeword lengths ( i ) i∈Σ . The Kraft function [START_REF] Laidlaw | The construction of codes for infinite sets[END_REF] of C is defined by the the formal series

P (z) = i∈Σ µ i z i .
The average code length of C is then c(C) = z ∂ ∂z P (z) z=1 . Explicit expressions for the Kraft functions of the optimal codes of Proposition 1 can be derived from the proposition using standard generating function tools, and are presented fully in [START_REF] Bassino | Optimal prefix codes for pairs of geometrically-distributed random variables[END_REF]. As an example, the Kraft function of the optimal code for q = 1/4 is given by

P 1 4 (z) = 9 16 " z+ qz 1-q 3 z 6 " 2z 2 +qz 2 " 3z+qz 2 " z+3z 2 + 3qz 3 1-qz 2 ««««
Kraft functions were applied to obtain the average code lengths of the optimal codes of Proposition 1. These lengths were used, in turn, in the redundancy computations summarized in Section IV.

IV. THE FAMILY OF PARAMETERS

q = 1/ k √ 2
Fig. 3. The tree q -2 T 2 q .

The following grammar defines the trees T d u for d = 0, 1, 2, and an indeterminate u.

T 0 q → 1 , T d q → qT d q qT d-1 q (d = 1, 2). (3)
The tree q r T 1 q k is easily recognized as G 1 (unary tree), with leaves appropriately weighted. Moreover, the tree underlying q r T 2 q k is recognized as G 1 • G 1 (see Figure 3). This tree is optimal for the (dyadic) TDGD with q = 1/2, since G 1 has redundancy zero for the corresponding geometric distribution, and, thus, the same is true for G 1 • G 1 on pairs. It follows from the foregoing discussion, and straightforward symbolic manipulations, that w(q r T 2

q k ) = w( q r ) q k 1-q k 2 . It is important to note that if q = 1/ k √ 2
then, w(q r T 2 q k ) = w(q r T 1 q k ) = w(q r T 0 q k ) = w( q r ). This observation is the basis of the construction and proof of Proposition 3 below.

Proposition 3: Let q=1/ k √ 2 with k≥1. Then, an optimal prefix tree D k for a TDGD with parameter q is obtained by applying the Huffman algorithm to the finite source

S T = {q -2k T 2 q k 1 time , q -2k+1 T 2 q k 2 times , q -2k+2 T 2 q k 3 times . . . , q -k-1 T 2 q k k times } ∪ { q -k T 2 q k k -1 times , . . . , q -3 T 2 q k 2 times , q -2 T 2 q k 1 times }.
It is shown in [START_REF] Bassino | Optimal prefix codes for pairs of geometrically-distributed random variables[END_REF] that a prescribed sequence of pairings of symbols q -i T 2 q k with 2 ≤ i ≤ k -1 leads from the reduced alphabet S T to a quasi-uniform source. Efficient coding and decoding algorithms for the codes D k of Proposition 3 is also presented in [START_REF] Bassino | Optimal prefix codes for pairs of geometrically-distributed random variables[END_REF]. Notice that the concatenation G 1 •G 1 plays, for the D k , the role that G 1 plays for Golomb codes (with a more complex structure of k 2 leaves, defined by S T , at the "head" of the tree). This observation is explored further in [START_REF] Bassino | Optimal prefix codes for pairs of geometrically-distributed random variables[END_REF], and generalizes to optimal codes on blocks of d>2 symbols. Redundancy. Figure 4 presents plots of redundancy per integer symbol as a function of q, for (A) 0 < q < 0.5, and (B) 0.5 ≤ q < 1, relative to the entropy rate of the geometric distribution of parameter q. Let C k denote the optimal prefix code for a TDGD with q = 2 -k , and D k the optimal code for q = 1/ k √ 2, k ≥ 1. Plots are shown for the Golomb code on single integer symbols, the best code C k or D k for each q (with C 1 = D 1 ), and the optimal code for each q. Code lengths for the latter were approximated empirically. It is observed in the figure that the families { C k } and {D k } provide good approximations to the optimal codes for all q. However, it is also observed that optimal codes for some values of q will be strictly outside of the families characterized in this paper.

V. CONCLUSION Optimal prefix codes were presented for two sub-families of TDGDs, namely, those with parameters q = 2 -k with k>1, or q = 1/ k √ 2 with k > 0. The two families provide good approximations to, but do not contain, all optimal prefix codes for TDGDs with parameters in the full interval 0<q<1. Characterizing optimal prefix codes for TDGDs over the full interval is the subject of ongoing research. Future work will include also further generalizations to higher dimensions, i.e., blocks of d > 2 integer symbols. Of interest also is the derivation of analogous results for blocks of two-sided geometric distributions [START_REF] Merhav | Optimal prefix codes for sources with two-sided geometric distributions[END_REF].

Fig. 1 .

 1 Fig. 1. Optimal prefix code tree for a TDGD with q=1/8, with leaf signatures noted for f ≤ 9.

Fig. 4 .

 4 Fig. 4. Redundancy (bits/integer symbol) for the optimal code (empirical), the Golomb code, and the best code C k or D k for (A) 0<q< 1 2 , (B) 1 2 ≤q<1.

A way to test Huffman compatibility is to use the sibling property[START_REF] Gallager | Variations on a theme by Huffman[END_REF] that characterizes Huffman trees as the trees whose nodes can be listed in non-increasing order of probability in such way that two sibling nodes are adjacent in the list.