Finding fixpoints in finite function spaces using neededness analysis and chaotic iteration
Finding fixpoints in finite function spaces using neededness analysis and chaotic iteration
复制标题
使用需求分析和混沌迭代在有限函数空间中查找不动点
DOI：
10.1007/3-540-58485-4_50
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Niels Jørgensen
中科院分区：
文献类型：
--
作者：
Niels Jørgensen
定义了一种计算有限函数空间上泛函最小不动点的新算法。该算法适用于计算任意形式的泛函方程组的最小不动点（全局不动点或局部不动点）。该算法采用Cousot和Cousot混沌迭代[2]的一种变体，并使用需要（或依赖）信息来指导定点迭代，如Kildall的早期算法[12]。与Muthukumar和Hermenegildo[7]以及Le Charlier等人提出的算法一样，需求分析是动态的，主要区别在于我们的需求分析具有更“浅”的性质，并且我们的方法更具迭代性而更少递归性。复杂度结果表明，每个方程的最坏情况迭代次数与方程系统中方程的总数无关，其中迭代对应于根据给定的函数和基本参数值对方程进行一次评估。
A new and efficient algorithm for computing the least fixpoint of a functional on a finite function space is defined. The algorithm applies to the computation of the least fixpoint (global or local) induced by an arbitrary system of functional equations in a certain formalism. The algorithm employs a variant of Cousot and Cousot's chaotic iteration [2], and uses neededness (or dependency) information to guide the fixpoint iteration, as for instance in Kildall's early algorithm [12]. The neededness analysis is dynamic as in the algorithms proposed by Muthukumar and Hermenegildo [7] and Le Charlier et al. [10], with the main difference being that our neededness analysis is of a more “shallow” nature, and that our approach is more iterative and less recursive. The complexity result implies that the worst-case number of iterations per equation is independent of the total number of equations in the equation system, where an iteration corresponds to evaluating an equation once with respect to given values of the functional and primitive parameters.