Polynomial-Time Inverse Computation for Accumulative Functions with Multiple Data Traversals
Polynomial-Time Inverse Computation for Accumulative Functions with Multiple Data Traversals
复制标题
多次数据遍历累加函数的多项式时间逆计算
DOI：
10.1145/2103746.2103752
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Kazuhiro Inaba and Keisuke Nakano
中科院分区：
文献类型：
--
作者：
Kazutaka Matsuda;Kazuhiro Inaba and Keisuke Nakano
逆计算有许多应用，如序列化/反序列化，提供对撤消的支持，以及软件测试的测试用例生成。在这篇文章中，我们提出了一种反计算方法，对于一类称为参数线性宏树换能器的函数，它涉及多次数据遍历和累加的使用。我们方法的关键是观察到类中的函数可以被视为不需要多次数据遍历的非累加上下文生成转换。因此，我们证明了通过对逆计算结果的上下文记忆来实现对类的逆计算的终止是容易的。我们还证明了当我们使用树自动机来表示逆计算结果时，逆计算以原始输出的大小和文本程序的大小的时间多项式运行。
Inverse computation has many applications such as serialization/deserialization, providing support for undo, and test-case generation for software testing. In this paper, we propose an inverse computation method that always terminates for a class of functions known as parameter-linear macro tree transducers, which involve multiple data traversals and the use of accumulations. The key to our method is the observation that a function in the class can be regarded as a non-accumulative context-generating transformation without multiple data traversals. Accordingly, we demonstrate that it is easy to achieve terminating inverse computation for the class by context-wise memoization of the inverse computation results. We also show that when we use a tree automaton to express the inverse computation results, the inverse computation runs in time polynomial to the size of the original output and the textual program size.