Allouche, J.-P.; Hajnal, P.; Shallit, J. O. Analysis of an infinite product algorithm. (English) Zbl 0677.68032 SIAM J. Discrete Math. 2, No. 1, 1-15 (1989). 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. Reviewer: Jean-Paul Allouche (Paris) Cited in 1 Document MSC: 68Q25 Analysis of algorithms and problem complexity 11A63 Radix representation; digital problems Keywords:complexity of algorithm; trees; binary words; bifix-free words; infinite products Citations:Zbl 0629.05004; Zbl 0278.94009 PDFBibTeX XMLCite \textit{J. P. Allouche} et al., SIAM J. Discrete Math. 2, No. 1, 1--15 (1989; Zbl 0677.68032) Full Text: DOI