Name
Title | ||
|---|---|---|
Polynomial-time inverse computation for accumulative functions with multiple data traversals |
Abstract | ||
|---|---|---|
The problem of inverse computation has many potential 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10990-013-9097-8 | partial evaluation and semantic-based program manipulation |
Keywords | Field | DocType |
polynomial time,functional programming,software testing | Inverse,Programming language,Serialization,Program transformation,Polynomial,Computer science,Algorithm,Theoretical computer science,Tree automaton,Time complexity,Memoization,Computation | Journal |
Volume | Issue | ISSN |
25 | 1 | 1573-0557 |
Citations | PageRank | References |
5 | 0.40 | 36 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazutaka Matsuda | 1 | 112 | 10.75 |
| Kazuhiro Inaba | 2 | 102 | 8.07 |
| Keisuke Nakano | 3 | 212 | 24.62 |