The language complexity of a finite word or infinite sequence is aimed to give a measure of the number of different factors in the given word or sequence. In fact, the definitions in the finite or infinite case coincide.

Let $A$$A$AA$A$ be a finite nonvoid alphabet and $U=u_0{u}_1\dots$$U=u_0{u}_1\dots$U=u_(0)u_(1)dotsU=u_{0} u_{1} \ldots$U=u_0{u}_1\dots$ an infinite sequence with $u_i\in A,i\in \mathbb{N}$$u_i\in A,i\in \mathbb{N}$u_(i)in A,i inNu_{i} \in A, i \in \mathbb{N}$u_i\in A,i\in \mathbb{N}$. The complexity of the sequence will be a function $p_U:{\mathbb{N}}^{\ast }\to \mathbb{N}$$p_U:{\mathbb{N}}^{\ast }\to \mathbb{N}$p_(U):N^(**)rarrNp_{U}: \mathbb{N}^{*} \rightarrow \mathbb{N}$p_U:{\mathbb{N}}^{\ast }\to \mathbb{N}$ given by

$\mathrm{♯}$$\mathrm{♯}$♯\sharp$\mathrm{♯}$ denoting the cardinal of the set $L_n(U)$$L_n(U)$L_(n)(U)L_{n}(U)$L_n(U)$ of the factors of length $n$$n$nn$n$ in $U$$U$UU$U$.
For the finite word $w$$w$ww$w$ of length $q\in {\mathbb{N}}^{\ast }$$q\in {\mathbb{N}}^{\ast }$q inN^(**)q \in \mathbb{N}^{*}$q\in {\mathbb{N}}^{\ast }$, the complexity $p_w$$p_w$p_(w)p_{w}$p_w$ may be conceptually defined in the same way. But, because $\mathrm{♯}{L}_n(w)=0$$\mathrm{♯}{L}_n(w)=0$♯L_(n)(w)=0\sharp L_{n}(w)=0$\mathrm{♯}{L}_n(w)=0$ for $n>q$$n>q$n > qn>q$n>q$, we can consider only the restriction on the set $\{1,\dots ,q\}$$\{1,\dots ,q\}${1,dots,q}\{1, \ldots, q\}$\{1,\dots ,q\}$, so $p_w:\{1,\dots ,q\}\to \mathbb{N}$$p_w:\{1,\dots ,q\}\to \mathbb{N}$p_(w):{1,dots,q}rarrNp_{w}:\{1, \ldots, q\} \rightarrow \mathbb{N}$p_w:\{1,\dots ,q\}\to \mathbb{N}$,

The complexity functions $p_U$$p_U$p_(U)p_{U}$p_U$, respectively $p_w$$p_w$p_(w)p_{w}$p_w$, estimate the richness in factors of length $n$$n$nn$n$ of a sequence or of a word, for every $n\in {\mathbb{N}}^{\ast }$$n\in {\mathbb{N}}^{\ast }$n inN^(**)n \in \mathbb{N}^{*}$n\in {\mathbb{N}}^{\ast }$ or $n\in \{0,\dots ,q\}$$n\in \{0,\dots ,q\}$n in{0,dots,q}n \in\{0, \ldots, q\}$n\in \{0,\dots ,q\}$. It would be of great help to have a global indicator of the complexity.

In the case of finite words there are two known definitions, the first one of total complexity given independently by Iványi [5] and Shallit [6], the second of maximal complexity, suggested by Rauzy.

Definition 1 For the word $w$$w$ww$w$ of length $q\in {\mathbb{N}}^{\ast }$$q\in {\mathbb{N}}^{\ast }$q inN^(**)q \in \mathbb{N}^{*}$q\in {\mathbb{N}}^{\ast }$, the total complexity is given by

and the maximal complexity is

The aim of this paper is to define similar global complexities (not depending on the specific length $n$$n$nn$n$ of the factors) for infinite sequences.

Given a word of length $q$$q$qq$q$, the complexity function $p_w$$p_w$p_(w)p_{w}$p_w$ may be considered as a vector in the space ${\mathbb{R}}^q$${\mathbb{R}}^q$R^(q)\mathbb{R}^{q}${\mathbb{R}}^q$. On this space we have the well-known Minkowski norm $\Vert x{\Vert }_1=\sum _{j=1}^q\left|x_j\right|$$\Vert x{\Vert }_1=\sum _{j=1}^q \left|x_j\right|$||x||_(1)=sum_(j=1)^(q)|x_(j)|\|x\|_{1}=\sum_{j=1}^{q}\left|x_{j}\right|$\Vert x{\Vert }_1=\sum _{j=1}^q\left|x_j\right|$, Chebyshev norm $\Vert x{\Vert }_{\mathrm{\infty }}=\underset{j=1}{\overset{q}{max}}\left|x_j\right|$$\Vert x{\Vert }_{\mathrm{\infty }}=\underset{j=1}{\overset{q}{max}} \left|x_j\right|$||x||_(oo)=max_(j=1)^(q)|x_(j)|\|x\|_{\infty}=\max _{j=1}^{q}\left|x_{j}\right|$\Vert x{\Vert }_{\mathrm{\infty }}=\underset{j=1}{\overset{q}{max}}\left|x_j\right|$, or Euclid norm $\Vert x\Vert ={\left(\sum _{j=1}^q{x}_j^2\right)}^{1/2}$$\Vert x\Vert ={\left(\sum _{j=1}^q x_j^2\right)}^{1/2}$||x||=(sum_(j=1)^(q)x_(j)^(2))^(1//2)\|x\|=\left(\sum_{j=1}^{q} x_{j}^{2}\right)^{1 / 2}$\Vert x\Vert ={\left(\sum _{j=1}^q{x}_j^2\right)}^{1/2}$, which are of course equivalent. It is obvious that if we denote

we shall have for the total complexity

and for the maximal complexity

We can also consider a Euclidian complexity given by $\Vert p_w\Vert$$‖p_w‖$||p_(w)||\left\|p_{w}\right\|$\Vert p_w\Vert$, which has the disadvantage that its values are not in general integer numbers.

The total and maximal complexities were used by Ferenczi and Kasa [4] to define upper and lower complexities for infinite sequences, in the following way:

These two notions, having many interesting properties, are extensively studied in [4]. Being functions of $n\in {\mathbb{N}}^{\ast }$$n\in {\mathbb{N}}^{\ast }$n inN^(**)n \in \mathbb{N}^{*}$n\in {\mathbb{N}}^{\ast }$, the upper and lower total (maximal) finite-word complexity functions are similar to the initial complexity function $p_U$$p_U$p_(U)p_{U}$p_U$. What we intend is to define global complexities for the case of infinite sequences too.

There already exist some notions to estimate the global complexity for infinite sequences, as for example the topological entropy [1]

which satisfies

for every sequence $U$$U$UU$U$.
The definitions we give extend those for finite words to infinite sequences; to this aim it is necessary to "normalize" the values of the complexity function $p_U(n)$$p_U(n)$p_(U)(n)p_{U}(n)$p_U(n)$ by dividing them with $(\mathrm{♯}A{)}^n$$(\mathrm{♯}A{)}^n$(♯A)^(n)(\sharp A)^{n}$(\mathrm{♯}A{)}^n$.

Definition 2 For the infinite sequence $U$$U$UU$U$, the total complexity is given by

and the maximal complexity by

Remark 1 The total complexity in definition 2 is not necessarily finite; for example, for the Champernowne word containing successively all the binary written numbers $011011100101111\dots$$011011100101111\dots$011011100101111 dots011011100101111 \ldots$011011100101111\dots$ we have $p_U(n)=2^n$$p_U(n)=2^n$p_(U)(n)=2^(n)p_{U}(n)=2^{n}$p_U(n)=2^n$ and $K_U=\mathrm{\infty }$$K_U=\mathrm{\infty }$K_(U)=ooK_{U}=\infty$K_U=\mathrm{\infty }$, while $C_U=1$$C_U=1$C_(U)=1C_{U}=1$C_U=1$.

For this reason, instead of definition 2 we propose one for normal complexity, which will have values less than 1 .

Definition 3 For the infinite sequence $U$$U$UU$U$, the normal complexity is given by

Remark 2 In the definitions above, there appears the sequence

Because of the inequality

holding for each complexity function, the sequence $c_n$$c_n$c_(n)c_{n}$c_n$ is non-increasing, so $C_U=c_1=1$$C_U=c_1=1$C_(U)=c_(1)=1C_{U}=c_{1}=1$C_U=c_1=1$. For the Champernowne sequence we have $c_n=1,n\in {\mathbb{N}}^{\ast }$$c_n=1,n\in {\mathbb{N}}^{\ast }$c_(n)=1,n inN^(**)c_{n}=1, n \in \mathbb{N}^{*}$c_n=1,n\in {\mathbb{N}}^{\ast }$.

In the following we consider sequences for which the complexity function is known and try to determine (at least approximately) their global complexities. The alphabet has three symbols in example 4.1, $a+b$$a+b$a+ba+b$a+b$ in 4.2 and two symbols for Sturmian sequences and those in 4.3 and 4.4. The topological entropy is $h_U=0$$h_U=0$h_(U)=0h_{U}=0$h_U=0$, excepting example 4.4.

A sequence generated by the structure of billiard trajectories in the cube, associating to a trajectory starting with totally irrational direction the sequence with values in $\{1,2,3\}$$\{1,2,3\}${1,2,3}\{1,2,3\}$\{1,2,3\}$ given by coding 1 (respectively 2,3 ) any time
the particle rebounds on a frontal (lateral, horizontal) side of the cube, was shown in [2] to have the complexity $p_U(n)=n^2+n+1$$p_U(n)=n^2+n+1$p_(U)(n)=n^(2)+n+1p_{U}(n)=n^{2}+n+1$p_U(n)=n^2+n+1$.

Proposition 1 For a sequence defined by the cubic billiard with totally irrational direction, the total, maximal and normal complexity will be

For an important class of sequences the complexity function is linear.
Proposition 2 Let $U$$U$UU$U$ be a sequence having the complexity function given by $p_U(n)=an+b,n\in {\mathbb{N}}^{\ast }(a\in {\mathbb{N}}^{\ast },b\in \mathbb{N},a+b\ge 2)$$p_U(n)=an+b,n\in {\mathbb{N}}^{\ast }\left(a\in {\mathbb{N}}^{\ast },b\in \mathbb{N},a+b\ge 2\right)$p_(U)(n)=an+b,n inN^(**)(a inN^(**),b inN,a+b >= 2)p_{U}(n)=a n+b, n \in \mathbb{N}^{*}\left(a \in \mathbb{N}^{*}, b \in \mathbb{N}, a+b \geq 2\right)$p_U(n)=an+b,n\in {\mathbb{N}}^{\ast }(a\in {\mathbb{N}}^{\ast },b\in \mathbb{N},a+b\ge 2)$. Its total, maximal and normal complexity will be

where ${}_{\alpha }{F}_{\beta }$${}_{\alpha }{F}_{\beta }$_(alpha)F_(beta){ }_{\alpha} F_{\beta}${}_{\alpha }{F}_{\beta }$ denotes the hypergeometric function.
Remark 3 Well-known sequences of this type are Sturmian sequences (which are not ultimately periodic, but are recurrent), for which $a=b=1$$a=b=1$a=b=1a=b=1$a=b=1$; they have the global complexities given by

Let us consider the words $v_i=0^i,w_i=1^i$$v_i=0^i,w_i=1^i$v_(i)=0^(i),w_(i)=1^(i)v_{i}=0^{i}, w_{i}=1^{i}$v_i=0^i,w_i=1^i$ and $u_i=v_i{w}_i,i\in {\mathbb{N}}^{\ast },u_i$$u_i=v_i{w}_i,i\in {\mathbb{N}}^{\ast },u_i$u_(i)=v_(i)w_(i),i inN^(**),u_(i)u_{i}=v_{i} w_{i}, i \in \mathbb{N}^{*}, u_{i}$u_i=v_i{w}_i,i\in {\mathbb{N}}^{\ast },u_i$ being obtained by concatenation of $v_i$$v_i$v_(i)v_{i}$v_i$ and $w_i$$w_i$w_(i)w_{i}$w_i$. The power sequence $U$$U$UU$U$ is given by

and has the complexity $p_U=n(n+1)/2+1$$p_U=n(n+1)/2+1$p_(U)=n(n+1)//2+1p_{U}=n(n+1) / 2+1$p_U=n(n+1)/2+1$.
Proposition 3 For the power sequence (11), the global complexities are given by

This sequence was mentioned in Section 3 and it is obtained by writing successively all the binary written numbers. Its complexity function is $p_U(n)=2^n$$p_U(n)=2^n$p_(U)(n)=2^(n)p_{U}(n)=2^{n}$p_U(n)=2^n$ and the topological entropy is $h_U=1$$h_U=1$h_(U)=1h_{U}=1$h_U=1$.

Proposition 4 For the Champernowne sequence, the global complexities are given by

Acknowledgements. The author thanks the Ministry of Science and Technology for supporting partially this work (3004GR/1997).

[1] J.-P. Allouche, Sur la complexité des suites infinies, Bull. Belg. Math. Soc. 1(1994), 133-143
[2] P. Arnoux, Ch. Mauduit, I. Shiokawa, Jun-ichi Tamura, Complexity of sequences defined by billiards in the cube, Bull. Soc. Math. France 122(1)(1994), 1-12
[3] S. Ferenczi, Complexity of sequences and dynamical systems, to appear in Discrete Math. 206(1999)
[4] S. Ferenczi, Z. Kása, Complexities for finite factors of infinite sequences, to appear in Theor. Comput. Sci. 218(1)(1999), 177-195
[5] A. Iványi, On the $d$$d$dd$d$-complexity of words, Ann. Univ. Sci. Budapest Sect. Comput. 8(1987), 69-90
[6] J. Shallit, On the maximum number of distinct factors in a binary string, Graphs and Combinatorics 9 (1993), 197-200