×

Analysis of an infinite product algorithm. (English) Zbl 0677.68032

If \(w\) is a binary word (i.e. an element of \(\{0,1\}^*)\), let \(a_ w(n)\) denote the number of possibly overlapping occurrences of \(w\) in the binary expansion of the integer \(n\). In a recent paper [J. Lond. Math. Soc., II. Ser. 39, 193–204 (1989; Zbl 0629.05004)] J.-P. Allouche and J. Shallit showed that for every \(w\) there exists a rational function \(b_w(n)\), that they explicitly construct such that
\[ \sum_{n\geq 0} \log_2(b_w(n))X^{a_w(n)}=1/(X-1), \]
for all complex values \(X\) with \(| X| \leq 1\) and \(X\neq 1\). This result generalized the classical infinite product \[ \prod^{+\infty}_{n=0}((2n+1)/(2n+2))^{\varepsilon_n}=\sqrt{2}/2, \]
where \(\varepsilon_n=(-1)^{a_1(n)}\), (in other words \(b_1(m)=(2n+1)/(2n+2))\).
In the paper under review the authors develop the study of the algorithm which computes \(b_w\), by associating to each \(w\) a certain tree \(T(w)\). They show that the running time of the algorithm is polynomial in the length of \(w\) (more precisely they obtain \(O(| w|^{11.1})\) and they prove that in bad cases one has a running time in \(\Omega (| w|^3))\).
Note finally that if \(w\) is a “bifix-free” word [P. T. Nielsen, IEEE Trans. Inf. Theory 19, 704–706 (1973; Zbl 0278.94009)], which is the case for more than one word out of four, then the algorithm actually runs in linear time.

MSC:

68Q25 Analysis of algorithms and problem complexity
11A63 Radix representation; digital problems
PDFBibTeX XMLCite
Full Text: DOI