@article{Chyzak_Dreyfus_Dumas_Mezzarobba_2018_CSL,
  author = {Chyzak, Fr{\'e}d{\'e}ric and Dreyfus, Thomas and Dumas, Philippe and Mezzarobba, Marc},
  title = {Computing solutions of linear {M}ahler equations},
  journal = {Mathematics of Computation},
  year = {2018},
  volume = {87},
  number = {314},
  pages = {2977--3021},
  doi = {https://doi.org/10.1090/mcom/3359},
  abstract = {Mahler equations relate evaluations of the same function~$f$ at iterated $b$th powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. In this work, we present algorithms for solving linear Mahler equations for series, polynomials, and rational functions, and get polynomial-time complexity under a mild assumption. Incidentally, we develop an algorithm for computing the gcrd of a family of linear Mahler operators with nonzero constant terms.}
}