Decomposition of ordinary difference polynomials (Q840708)

This article presents an algorithm for decomposition of nonlinear ordinary difference polynomials. It is a generalization of \textit{D. Kozen} and \textit{S. Landau} [J. Symb. Comput. 7, No. 5, 445--456 (1989; Zbl 0691.68030)] to ordinary difference polynomials. The algorithm works in several steps. First, the problem is reduced to decomposition of a homogeneous difference polynomial. Next, this is reduced to decomposing the linear left decomposition factors of another homogeneous difference polynomial. Finally, these are computed using decomposition of linear difference polynomials. This whole procedure computes the right decomposition factors; it is easy to find the left factors corresponding to them. The final algorithm is exponential due to combinatorial selections in the algorithm. The authors point out that the complexity of decomposing linear difference polynomials is also exponential, and that their algorithm for the non-linear case is quite effective practically. Also, this algorithm does not introduce parameters and works in the coefficient field of the input. There exists an algorithm for differential (as opposed to difference) polynomials by the same authors [\textit{X.-S. Gao} and \textit{M. Zhang}, Appl. Algebra Eng. Commun. Comput. 19, No. 1, 1--25 (2008; Zbl 1180.12004)] which, according to them, is quite different from the one presented here, due to the different properties of differential and difference operators.