Computing solutions of linear Mahler equations
Computing solutions of linear Mahler equations
复制标题
计算线性马勒方程的解
DOI：
--
复制
发表时间：
2016
影响因子：
2
通讯作者：
M. Mezzarobba
中科院分区：
文献类型：
--
作者：
F. Chyzak;T. Dreyfus;P. Dumas;M. Mezzarobba
马勒方程涉及同一函数f在变量的迭代$B$次幂上的求值。它们特别出现在自动序列的研究和分治算法的复杂性分析中。最近，封闭形式的马勒方程的求解问题与数论问题有关。在操纵马勒方程的一个困难是指数爆破的程度时，适用于一个马勒算子的多项式。在这项工作中，我们提出的算法求解线性马勒方程的级数，多项式和有理函数，并得到多项式时间复杂度下一个温和的假设。顺便说一句，我们开发了一个算法计算的gcrd的一个家庭的线性马勒算子。
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.